P3688 [ZJOI2017] 树状数组【二维线段树】

题目描述：这里有一个写挂的树状数组：

有两种共\(m\)个操作：

输入\(l,r\)，在\([l,r]\)中随机选择一个整数\(x\)执行\(\text{Add}(x)\)
输入\(l,r\)，询问执行\(\text{Query}(l,r)\)的答案正确的概率\(\text{mod} \ 998244353\)。

数据范围：\(n,m\leq 100000\)

首先，根据这个代码，我们知道这就是一个单点修改求后缀和的数据结构。所以\(\text{Query}(l,r)\)求的是\([l-1,r-1]\)的和。所以正确当且仅当\(a_{l-1}=a_r\)。

注意，如果你直接维护每个数为\(0,1\)的概率，就会出现可能多次修改的问题。所以要\((x,y)\)维护\(a_x\neq a_y\)的概率。我们知道\(a_x\neq a_y\)的概率为\(p\)，并以\(q\)的概率修改，则之后的概率为\(p(1-q)+q(1-p)\)，这个标记是可合并的。所以：

若\(x\in [1,l-1],y\in [l,r]\)或\(x\in [l,r],y\in [r+1,n]\)，则以\(\frac{1}{r-l+1}\)的概率修改。
若\(x,y\in [l,r]\)，则以\(\frac{2}{r-l+1}\)的概率修改。

注意，上面\(\text{Find}(x)\)特判了\(x=0\)的情况，所以若\(l=1\)则计算的是\(r\)的后缀和，所以用\((0,x)\)维护\(x\)的前缀和是否等于\(x\)的后缀和的概率。

若\(x\notin [l,r]\)，则以1的概率修改。
若\(x\in [l,r]\)，则以\(\frac{r-l}{r-l+1}\)的概率修改。

而且询问是单点询问，所以我们可以使用二维线段树维护并标记永久化。

如果你不想卡常并最大点使用时限\(-0.01s\)通过Luogu评测，而且不能在UOJ通过，可以使用cdq分治，但是我不会。。。

#include<bits/stdc++.h>

#define Rint register int

using namespace std;

typedef long long LL;

const int N = 100003, mod = 998244353;

inline int kasumi(int a, int b){

	int res = 1;

	while(b){

		if(b & 1) res = (LL) res * a % mod;

		a = (LL) a * a % mod; b >>= 1;

	}

	return res;

}

int n, m, inv[N], root[N << 2], val[N * 350], ls[N * 350], rs[N * 350], cnt;

inline int Add(int a, int b){return (a + b >= mod) ? (a + b - mod) : (a + b);}

inline int Sub(int a, int b){return (a < b) ? (a + mod - b) : (a - b);}

inline int add(int a, int b){return Add((LL) a * Sub(1, b) % mod, (LL) b * Sub(1, a) % mod);}

inline void change(int &x, int L, int R, int l, int r, int v){

	if(!x) x = ++ cnt;

	if(l <= L && R <= r){val[x] = add(val[x], v); return;}

	int mid = L + R >> 1;

	if(l <= mid) change(ls[x], L, mid, l, r, v);

	if(mid < r) change(rs[x], mid + 1, R, l, r, v);

}

inline int query(int x, int L, int R, int p){

	if(!x) return 0;

	if(L == R) return val[x];

	int mid = L + R >> 1;

	if(p <= mid) return add(val[x], query(ls[x], L, mid, p));

	else return add(val[x], query(rs[x], mid + 1, R, p));

}

inline void change(int x, int L, int R, int l1, int r1, int l2, int r2, int v){

	if(l1 <= L && R <= r1){change(root[x], 1, n, l2, r2, v); return;}

	int mid = L + R >> 1;

	if(l1 <= mid) change(x << 1, L, mid, l1, r1, l2, r2, v);

	if(mid < r1) change(x << 1 | 1, mid + 1, R, l1, r1, l2, r2, v);

}

inline int query(int x, int L, int R, int p1, int p2){

	if(L == R) return query(root[x], 1, n, p2);

	int mid = L + R >> 1;

	if(p1 <= mid) return add(query(root[x], 1, n, p2), query(x << 1, L, mid, p1, p2));

	else return add(query(root[x], 1, n, p2), query(x << 1 | 1, mid + 1, R, p1, p2));

}

int main(){

	scanf("%d%d", &n, &m);

	for(Rint i = 1;i <= n;i ++) inv[i] = kasumi(i, mod - 2);

	while(m --){

		int opt, l, r;

		scanf("%d%d%d", &opt, &l, &r);

		if(opt == 1){

			if(l > 1){

				change(root[0], 1, n, 1, l - 1, 1);

				change(1, 1, n, 1, l - 1, l, r, inv[r - l + 1]);

			}

			if(r < n){

				change(root[0], 1, n, r + 1, n, 1);

				change(1, 1, n, l, r, r + 1, n, inv[r - l + 1]);

			}

			if(l < r) change(1, 1, n, l, r, l, r, 2ll * inv[r - l + 1] % mod);

			change(root[0], 1, n, l, r, Sub(1, inv[r - l + 1]));

		} else if(l == 1) printf("%d\n", Sub(1, query(root[0], 1, n, r)));

		else printf("%d\n", Sub(1, query(1, 1, n, l - 1, r)));

	}

}

巴特西

P3688 [ZJOI2017] 树状数组【二维线段树】

最新文章

热门文章

巴特西

P3688 [ZJOI2017] 树状数组 【二维线段树】

最新文章

热门文章

P3688 [ZJOI2017] 树状数组【二维线段树】