ZJOI 2019 线段树题解

First Post:

2023-11-28

Last Update:

2023-11-29

记录一下广义线段树区间定位的“五类点”套路，这玩意不记下来很容易忘。

首先考虑对一棵线段树做题中的 modify 操作时，标记状况会如何变化，再考虑把很多棵线段树的结果叠加起来。

在线段树上，对区间进行定位时，可以根据标记变化状况将树上的点分为五类：

(图源 @ix35)

在进行区间的区间定位，并给定位点打上标记，下传沿途标记这一过程中，五种颜色的点分别这样变化：

红点：此时一定没标记
橙点：此时一定有标记
黄点：标记不变化
蓝点：标记不变化
绿点：如果祖先节点（包括自己）在操作前有标记，那么当前就有标记，否则无标记。

在上述五类点中，绿点的维护最麻烦，如果只记录表示当前点有没有标记，是无法封闭转移的。

所以还要多设一个变量，表示号点及祖先有没有标记。令为操作前的状态，那么五类点的变化如下：

红点：。
橙点：。
黄点：。
蓝点：。
绿点：。

这样每个点的变化情况就与其它点没有关系，只与自己所属的类别有关。

那么回到这道题，因为有很多棵线段树，我们考虑变通一下与的定义，设表示在这些树中选出一个号点，自身有标记/祖先有标记的概率（为何不设个数？因为如果设为个数，大部分的都要乘，所以不妨设为概率，相当于把这个留到最后再乘）。

那么红、绿、橙点单次操作只有个，可以暴力修改。蓝点不用管。

对于黄点，其个数可以有很多，但注意到对黄点的修改只是让变为。所以在线段树上维护一个标记，表示这个子树内的做了几次这种操作，在 modify 时下传即可。

这样本题就做完了，时间复杂度。

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5,P = 998244353,inv2 = (P + 1) / 2;
inline void Plus(int &x,const int &y) { x += y;if(x >= P) x -= P;}
inline int qpow(int a,int b) { int res = 1;while(b) { if(b&1) res = 1ll * res * a % P;a = 1ll * a * a % P;b >>= 1;} return res;}
int n,m;
int Pow2[N],Powi2[N];
int f[N],g[N],tim[N];
inline void Giv(int x,int v) { g[x] = (1ll * (g[x] - 1 + P) * Powi2[v] % P + 1) % P;tim[x] += v;}
inline void pushdown(int x) {
	if(tim[x]) Giv(x << 1,tim[x]),Giv(x << 1 | 1,tim[x]),tim[x] = 0;
}
int Sum;
inline void modify(int k,int l,int r,int x,int y) {
	if(x <= l && r <= y) {
		Plus(Sum,P - f[k]);
		f[k] = 1ll * (f[k] + 1) * inv2 % P;
		g[k] = 1ll * (g[k] + 1) * inv2 % P;
		Plus(Sum,f[k]);
		if(l != r) {
			Giv(k << 1,1);Giv(k << 1 | 1,1);
		}
		return;
	}	pushdown(k);

	int mid = l + r >> 1;
	Plus(Sum,P - f[k]);
	f[k] = 1ll * f[k] * inv2 % P;
	g[k] = 1ll * g[k] * inv2 % P;
	Plus(Sum,f[k]);
	if(x <= mid) modify(k << 1,l,mid,x,y);
	else {
		Plus(Sum,P - f[k << 1]);
		// (Sum += P - f[k << 1]) %= P;
		f[k << 1] = 1ll * (f[k << 1] + g[k << 1]) * inv2 % P;
		Plus(Sum,f[k << 1]);
	} 
	if(mid < y) modify(k << 1 | 1,mid + 1,r,x,y);
	else {
		Plus(Sum,P - f[k << 1 | 1]);
		f[k << 1 | 1] = 1ll * (f[k << 1 | 1] + g[k << 1 | 1]) * inv2 % P;
		Plus(Sum,f[k << 1 | 1]);
	} 
}
int main() {
	cin >> n >> m;
	Pow2[0] = Powi2[0] = 1;
	for(int i = 1;i <= m;i++)
		Pow2[i] = 2ll * Pow2[i - 1] % P,Powi2[i] = 1ll * inv2 * Powi2[i - 1] % P;
	Sum = 0;
	for(int i = 1,ct = 0;i <= m;i++) {
		int op,l,r;
		cin >> op;
		// printf("Sum:%d\n",Sum);
		if(op == 2) cout << 1ll * Sum * Pow2[ct] % P << endl;
		else cin >> l >> r,++ct,modify(1,1,n,l,r);

	}
	return 0;
}

≡

ZJOI 2019 线段树 题解

ZJOI 2019 线段树题解