洛谷 P3688 - [ZJOI2017]树状数组（二维线段树+标记永久化）

题面传送门

首先学过树状数组的应该都知道，将树状数组方向写反等价于前缀和 \(\to\) 后缀和，因此题目中伪代码的区间求和实质上是 \(sum[l-1...n]-sum[r...n]=sum[l-1...r-1]\)，我们要求 \(sum[l...r]=sum[l-1...r-1]\) 的概率，等价于求 \(a_{l-1}=a_r\) 的概率。

因此我们可将题目转化为，每次从 \([l,r]\) 中随机选择一个数将其状态翻转，并询问 \(a_x=a_y\) 的概率。

这个可以通过二维线段树解决。建一棵二维线段树，第 \(x\) 行第 \(y\) 个位置上的值 \(p_{x,y}\) 表示 \(a_x=a_y\) 的概率。考虑一次修改 \([l,r]\) 对 \(p_{i,j}\) 的影响，分三种情况：

\(i\in [1,l-1],j\in[l,r]\)，\(a_i\) 不会发生变化，\(a_j\) 有 \(p_1=\dfrac{1}{r-l+1}\) 的概率发生变化，故 \(p_{i,j}=(1-p_{i,j})\times p_1+p_{i,j}\times(1-p_1)\)。
\(i\in [l,r],j\in[l,r]\)，\(a_i,a_j\) 各有 \(\dfrac{1}{r-l+1}\) 的概率发生变化，发生变化的总概率 \(p_2=\dfrac{2}{r-l+1}\)，故 \(p_{i,j}=(1-p_{i,j})\times p_2+p_{i,j}\times(1-p_2)\)。
\(i\in [l,r],j\in[r+1,n]\)，\(a_j\) 不会发生变化，\(a_i\) 有 \(p_3=\dfrac{1}{r-l+1}\) 的概率发生变化，故 \(p_{i,j}=(1-p_{i,j})\times p_3+p_{i,j}\times(1-p_3)\)。

对于这三种情况，相当于是对二维线段树上一个矩形执行 \(p_{i,j}\leftarrow (1-p_{i,j})\times P+p_{i,j}\times (1-P)\)，这就直接在内层线段树上的区间上打一个 \(P\) 的标记。当合并两个标记 \(P,Q\) 时候，令新的标记 \(R=(1-P)\times Q+(1-Q)\times P\)。由于标记不能下放，因此需要标记永久化，时间复杂度线性二次对数。

当然你可能会有疑惑，上面三种情况中没有考虑 \(i\in [r+1,n],j\in[l,r]\) 的情况，当 \(i=j\) 时候 \(p_{i,j}\) 发生的变化的概率应当为 \(0\)，也不是所谓的 \(\dfrac{2}{r-l+1}\)，为什么算出来的概率还是正确的呢？事实上，我们查询的时候一定有 \(l-1<r\)，因此我们只需维护 \(i<j\) 的 \(p_{i,j}\) 的值即可， 上述写法只不过更方便我们执行二维线段树上的矩形加罢了，不会对算法正确性产生影响。

最后特判 \(l=1\) 的情况，当执行的操作次数为奇数的时候，\(sum[l-1...n]\) 的真实值应当为 \(1\)，而伪代码为了确保不卡入死循环直接返回了 \(0\)，因此若执行的操作次数为奇数，我们要求的实质上是 \(a_{l-1}\ne a_r\) 的概率。

#include <bits/stdc++.h>

using namespace std;

#define fi first

#define se second

#define fill0(a) memset(a,0,sizeof(a))

#define fill1(a) memset(a,-1,sizeof(a))

#define fillbig(a) memset(a,63,sizeof(a))

#define pb push_back

#define ppb pop_back

#define mp make_pair

template<typename T1,typename T2> void chkmin(T1 &x,T2 y){if(x>y) x=y;}

template<typename T1,typename T2> void chkmax(T1 &x,T2 y){if(x<y) x=y;}

typedef pair<int,int> pii;

typedef long long ll;

typedef unsigned int u32;

typedef unsigned long long u64;

namespace fastio{

	#define FILE_SIZE 1<<23

	char rbuf[FILE_SIZE],*p1=rbuf,*p2=rbuf,wbuf[FILE_SIZE],*p3=wbuf;

	inline char getc(){return p1==p2&&(p2=(p1=rbuf)+fread(rbuf,1,FILE_SIZE,stdin),p1==p2)?-1:*p1++;}

	inline void putc(char x){(*p3++=x);}

	template<typename T> void read(T &x){

		x=0;char c=getchar();T neg=0;

		while(!isdigit(c)) neg|=!(c^'-'),c=getchar();

		while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();

		if(neg) x=(~x)+1;

	}

	template<typename T> void recursive_print(T x){if(!x) return;recursive_print(x/10);putc(x%10^48);}

	template<typename T> void print(T x){if(!x) putc('0');if(x<0) putc('-'),x=~x+1;recursive_print(x);}

	void print_final(){fwrite(wbuf,1,p3-wbuf,stdout);}

}

const int MAXN=1e5;

const int MOD=998244353;

int qpow(int x,int e){

	int ret=1;

	for(;e;e>>=1,x=1ll*x*x%MOD) if(e&1) ret=1ll*ret*x%MOD;

	return ret;

}

int n,qu,ncnt=0;

struct node{int ch[2],tag;} s[MAXN*500+5];

int rt[MAXN*4+5];

void modify_in(int &k,int l,int r,int ql,int qr,int p){

	if(!k){k=++ncnt;s[k].tag=1;}

	if(ql<=l&&r<=qr){

		s[k].tag=(1ll*p*s[k].tag+1ll*(1+MOD-p)*(1+MOD-s[k].tag))%MOD;

		return;

	} int mid=l+r>>1;

	if(qr<=mid) modify_in(s[k].ch[0],l,mid,ql,qr,p);

	else if(ql>mid) modify_in(s[k].ch[1],mid+1,r,ql,qr,p);

	else modify_in(s[k].ch[0],l,mid,ql,mid,p),modify_in(s[k].ch[1],mid+1,r,mid+1,qr,p);

}

void modify_out(int k,int l,int r,int ql,int qr,int qx,int qy,int p){

	if(ql<=l&&r<=qr){modify_in(rt[k],1,n,qx,qy,p);return;}

	int mid=l+r>>1;

	if(qr<=mid) modify_out(k<<1,l,mid,ql,qr,qx,qy,p);

	else if(ql>mid) modify_out(k<<1|1,mid+1,r,ql,qr,qx,qy,p);

	else modify_out(k<<1,l,mid,ql,mid,qx,qy,p),modify_out(k<<1|1,mid+1,r,mid+1,qr,qx,qy,p);

}

int query_in(int k,int l,int r,int p){

	if(!k) return 1;if(l==r) return s[k].tag;

	int mid=l+r>>1,pp=(p<=mid)?query_in(s[k].ch[0],l,mid,p):query_in(s[k].ch[1],mid+1,r,p);

	return (1ll*pp*s[k].tag+1ll*(MOD+1-pp)*(MOD+1-s[k].tag))%MOD;

}

int query_out(int k,int l,int r,int p,int q){

	if(l==r) return query_in(rt[k],1,n,q);

	int mid=l+r>>1;

	int p1=(p<=mid)?query_out(k<<1,l,mid,p,q):query_out(k<<1|1,mid+1,r,p,q);

	int p2=query_in(rt[k],1,n,q);

	return (1ll*p1*p2+1ll*(MOD+1-p1)*(MOD+1-p2))%MOD;

}

int main(){

	scanf("%d%d",&n,&qu);int cnt=0;

	while(qu--){

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

		if(opt==1){

			int p=qpow(r-l+1,MOD-2);cnt^=1;

			modify_out(1,0,n,0,l-1,l,r,(MOD+1-p)%MOD);

			if(r^n) modify_out(1,0,n,l,r,r+1,n,(MOD+1-p)%MOD);

			modify_out(1,0,n,l,r,l,r,(MOD+1-2*p%MOD)%MOD);

		} else {

			int ret=query_out(1,0,n,l-1,r);

			if(!(l^1)&&cnt) ret=(MOD+1-ret)%MOD;

			printf("%d\n",ret);

		}

	}

	return 0;

}

洛谷 P3688 - [ZJOI2017]树状数组（二维线段树+标记永久化）的相关教程结束。