题解：P3688 [ZJOI2017] 树状数组

妙妙数据结构题！

Solution

1

树状数组倒过来变成什么？求后缀和哇！

那么

qry(r)-qry(l-1)= suf_r - suf_{l-1}

，而

suf_r-suf_{l-1}\equiv \sum_{i=l-1}^{r-1}a_i \bmod 2

。其中

suf_i

表示后缀和。

所以其实还是对区间求和。由此发现本题转化为：

给定参数 l r，随机给 $i\in [l,r]$ 的 $a_i$ 切换 $0/1$ 状态。
给定参数 l r，求此时 $a_l=a_r$ 成立的概率。

2

题目让

a_i

对

2

取模，实在是大有用处哇。

对于操作 1 给出的

[L,R]

，它们对操作 2 的

l,r

贡献大致分为三种情况：（记

len=R-L+1

，

P

为

a_l=a_r

成立的概率）

完全包含 $l,r$ ，那么有 $\dfrac{len-2}{len}$ 的概率，使得经过此修改操作后 $P$ 保持不变；
只包含 $l$ 或 $r$ ，那么有 $\dfrac{len-1}{len}$ 的概率，使得经过此修改操作后 $P$ 保持不变；
不包含 $l$ 或 $r$ ，那么有 $1$ 的概率，使得经过此修改操作后 $P$ 保持不变。

记上述“不变概率”为

Q

。

显然有

P'=PQ+(1-P)(1-Q)

。

3

挖掘上式性质。

P''=P'K+(1-P')(1-K)\\=(PQ+(1-P)(1-Q))K+(1-(PQ+(1-P)(1-Q)))(1-K)\\=4PQK-2PK-2QK-2PQ+P+Q+K

在最终化简的式子中，

P,Q,K

是轮换对称的。

也即是说，上述变换满足结合律。也即是说，

P

先和

Q

变换还是先和

K

变换，得到的结果都是一样的。

4

结合律的性质说明可以做标记永久化。而且又是区间修改单点查询，很符合线段树套线段树的使用场景。

外层线段树维护

l

，内层维护对应的

r

，线段树套线段树，标记永久化。~~然后就是板子了~~。

Code

实现细节：非常非常卡空间。不能开 long long，所以在快速幂等运算中要注意乘上 1ll。

感觉放在树套树中，是写得蛮清新了。

CPP

#include<bits/stdc++.h>
using namespace std;

//#define int long long
#define ll int
#define LL long long

#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define per(i, a, b) for(int i = (a); i >= (b); --i)
bool Mst;

const int maxn = 1e5 + 5;
const ll mod = 998244353;

int n, m;

inline ll pw(ll x, int p = mod - 2){
	ll res = 1ll; x %= mod;
	while(p){ if(p & 1) res = (LL)1ll * res * x % mod; p >>= 1; x = (LL)1ll * x * x % mod; }
	return res;
}

inline void Mop(ll &p, ll q){
	int tmp = (LL)1ll * p % mod * q % mod;
	int P = (LL)1ll * (1ll - p + mod) % mod, Q = (LL)1ll * (1ll - q + mod) % mod;
	p = (LL)1ll * (1ll * tmp + 1ll * P * Q % mod) % mod;
}

struct tree{
	int ch[2]; ll p;
	tree(){ p = 1ll; }
}t[maxn * 400]; int tot;

#define ls t[x].ch[0]
#define rs t[x].ch[1]

inline void updtr(int &x, int l, int r, int L, int R, ll p){
	if(L > R) return;
	if(!x) x = ++tot;
	if(l >= L and r <= R) return Mop(t[x].p, p), void();
	int mid = l + r >> 1; 
	if(L <= mid) updtr(ls, l, mid, L, R, p);
	if(R > mid) updtr(rs, mid + 1, r, L, R, p);
}
inline void qryp(int x, int l, int r, int p, ll &val){
	if(!x) return; Mop(val, t[x].p);
	if(l == r) return;
	int mid = l + r >> 1;
	if(p <= mid) qryp(ls, l, mid, p, val);
	else qryp(rs, mid + 1, r, p, val);
}

#undef ls
#undef rs

int tr[maxn << 2];

#define ls (x << 1)
#define rs (x << 1 | 1)

inline void updtr(int x, int l, int r, int L, int R, int ql, int qr, ll p){
	if(L > R) return;
	if(l >= L and r <= R) return updtr(tr[x], 1, n, ql, qr, p), void();
	int mid = l + r >> 1;
	if(L <= mid) updtr(ls, l, mid, L, R, ql, qr, p);
	if(R > mid) updtr(rs, mid + 1, r, L, R, ql, qr, p);
}
inline void qryp(int x, int l, int r, int L, int R, ll &val){
	qryp(tr[x], 1, n, R, val);
	if(l == r) return;
	int mid = l + r >> 1; 
	if(L <= mid) qryp(ls, l, mid, L, R, val);
	else qryp(rs, mid + 1, r, L, R, val);
}

#undef ls
#undef rs

bool Med;
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(NULL);
	
	fprintf(stderr, "%.2lfMB\n", abs(&Mst - &Med) / 1024. / 1024.);
	
	cin >> n >> m; int T0 = ++tot;
	
	while(m--){
		int op, l, r; cin >> op >> l >> r;
		int len = r - l + 1;
		if(op == 1){
			updtr(1, 1, n, l, r, l, r, (LL)1ll * (len - 2) * pw(len) % mod);
			updtr(1, 1, n, l, r, r + 1, n, (LL)1ll * (len - 1) * pw(len) % mod);
			updtr(1, 1, n, 1, l - 1, l, r, (LL)1ll * (len - 1) * pw(len) % mod);
			
			updtr(T0, 1, n, l, r, pw(len));
			updtr(T0, 1, n, 1, l - 1, 0);
			updtr(T0, 1, n, r + 1, n, 0);
		} else{
			if(l == 1){
				ll ans = 1ll; qryp(T0, 1, n, r, ans);
				cout << ans << '\n';
			} else{
				ll ans = 1ll; qryp(1, 1, n, l - 1, r, ans);
				cout << ans << '\n';
			}
		}
	}
	return 0;
}

题解：P3688 [ZJOI2017] 树状数组

文章操作

Solution

1

2

3

4

Code

相关推荐

评论

题解：P3688 [ZJOI2017] 树状数组