omeed(yali 18.8.6)(期望,线段树)(*)

Posted on | In ,

Description

Solution

基础分很好搞，关键是连击分 设fif_i表示combo(i)combo(i)的期望值 显然有Ans(combo)=B×∑i=lrpi×(fi−1+1)Ans(combo) = B \times \sum_{i = l}^{r} p_i \times (f_{i-1} + 1) 而fif_i也很好求 fi=p×(fi−1+1)+(1−pi)×fi−1×tf_i = p \times (f_{i-1} + 1) + (1-p_i)\times f_{i-1} \times t 于是fif_i能够写成x×fi+yx\times f_i + y的形式，同理一直搞下去就能把[l,r][l,r]这段区间所有的fif_i都写成x×fl−1+yx\times f_{l-1} + y的形式 显然直接只用维护系数就行了 那么用线段树来维护一段区间的和(在这里就是和的fl−1f_{l-1}的系数,与yy)，以及frf_r中的系数(用来合并)。合并时[l1,r1][l_1,r_1]与[l2,r2][l_2,r_2]时(l2=r1+1l_2 = r_1 + 1)，只要把fl2−1f_{l_2 - 1} 往回带就可以了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<bits/stdc++.h>
using namespace std;
const int mod = 998244353;
const int maxn = 5e5 + 10;
typedef long long LL;
int read()
{
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = (x << 3) + (x << 1) + (c ^ 48); c = getchar(); }
	return x * f;
}
struct tree
{
	int x1, x2, y1, y2;
}t[maxn << 2], ans;
int fg;
int n, ta, tb, T, q, A, B;
int p[maxn];
int Pow(int x, int P)
{
	int r = 1;
	while(P)
	{
		if(P & 1) r = 1LL * x * r % mod;
		x = 1LL * x * x % mod; P >>= 1;
	}
	return r;
}
tree merge(const tree &a, const tree &b)
{
	int x1, x2, y1, y2;
	x2 = 1LL * b.x2 * a.x2 % mod;
	y2 = (1LL * b.x2 * a.y2 % mod + b.y2) % mod;
	x1 = 1LL * b.x1 * a.x2 % mod;
	y1 = (b.y1 + 1LL * a.y2 * b.x1 % mod) % mod;
	x1 += a.x1; y1 += a.y1;
	x1 %= mod; y1 %= mod;
	return (tree){x1, x2, y1, y2};
}
void build(int o, int l, int r)
{
	if(l == r)
	{
		t[o].x2 = ((p[l] - 1LL * p[l] * T % mod + T) % mod + mod) % mod; t[o].y2 = p[l];
		t[o].x1 = p[l]; t[o].y1 = p[l];
		return ;
	}
	int mid = (l + r) >> 1;
	build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
	t[o] = merge(t[o << 1], t[o << 1 | 1]);
}	
void upt(int o, int l, int r, int pos)
{
	if(l == r)
	{
		t[o].x2 = ((p[l] - 1LL * p[l] * T % mod + T) % mod + mod) % mod; t[o].y2 = p[l];
		t[o].x1 = p[l]; t[o].y1 = p[l];
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) upt(o << 1, l, mid, pos);
	else upt(o << 1 | 1, mid + 1, r, pos);
	t[o] = merge(t[o << 1], t[o << 1 | 1]);
}
void que(int o, int l, int r, int x, int y)
{
	if(x <= l && r <= y)
	{
		if(fg) ans = t[o], fg = 0;
		else ans = merge(ans, t[o]);
		return ;
	}
	int mid = (l + r) >> 1;
	if(x <= mid) que(o << 1, l, mid, x, y);
	if(y > mid) que(o << 1 | 1, mid + 1, r, x, y);
}
namespace BIT
{
	int c[maxn];
	int lowbit(int x) { return x & (-x); }
	void upt(int x, int v)
	{
		while(x <= n)
		{
			c[x] = (c[x] + v) % mod; x += lowbit(x);
		}
	}
	int que(int x)
	{
		int ret = 0;
		while(x)
		{
			ret = (ret + c[x]) % mod; x -= lowbit(x);
		}
		return ret;
	}
}
int main()
{
	freopen("omeed.in", "r", stdin);
	freopen("omeed.out", "w", stdout);
	int xz_ak_IOI = read();
	n = read(); q = read(); ta = read(); tb = read(); A = read(); B = read();
	T = 1LL * ta * Pow(tb, mod - 2) % mod;
	for(int i = 1; i <= n; ++i)
	{
		int x = read(), y = read();
		p[i] = 1LL * x * Pow(y, mod - 2) % mod;
		BIT::upt(i, p[i]);
	}
	build(1, 1, n);
	for(int i = 1; i <= q; ++i)
	{
		int opt = read();
		if(opt == 0)
		{
			int x = read(), y = read(), z = read();
/**/		BIT::upt(x, (-p[x] + mod) % mod);
			p[x] = 1LL * y * Pow(z, mod - 2) % mod;
			upt(1, 1, n, x); BIT::upt(x, p[x]);
		}
		else 
		{
			int x = read(), y = read();
			fg = 1;
			que(1, 1, n, x, y);
			printf("%lld\n", (1LL * A * ((BIT::que(y) - BIT::que(x - 1) + mod) % mod) % mod + 1LL * B * ans.y1 % mod) % mod);
		}
	}
	return 0;
}

debug

119行，忘记加modmod模modmod