题解：P3688 [ZJOI2017] 树状数组

观察或打表得，题目给出的 FIND 函数返回的是后缀和。于是我们要求出的就是

a_{l-1}=a_r

的概率。特别的，若

l=0

则求的是

S_{[1,r]} = S_{[r,n]}

的概率。后者容易维护，下面考虑如何维护前者。

思考操作对答案的影响。我们建一个二维矩阵

P_{i,j}

，表示

a_i=a_j

的概率。修改区间

[l,r]

内的一个数，会使：

$i \in [1,l), j \in [l,r]$ 的相等或不等关系有 $\frac{1}{r-l+1}$ 概率反转。
$i \in [l,r], j \in (r,n]$ 的相等或不等关系有 $\frac{1}{r-l+1}$ 概率反转。
$i \in [1,r], j \in [l,r]$ 的相等或不等关系有 $\frac{2}{r-l+1}$ 概率反转。

不难发现我们要维护矩阵修改（概率计算式满足交换律和结合律，所以可以当作乘法），单点查询操作。于是使用二维线段树，树上区间完全落在修改区间内时，进入第二维进行类似操作。查询时要统计所有包含该点的矩阵。

第一次写二维线段树，代码很丑，但是思路是清晰的。

CPP


/*

       2025.11.17

 * Happy Zenith Noises *

*/
#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int MAXN=100005,mod=998244353;
int n,m,cnt,t;
struct node{int l,r,w,son;}tree[MAXN*405];
int neo(){tree[++cnt]=node{0,0,0,0};return cnt;}
int gt(ll x){return (x%mod+mod)%mod;}
int merge(int x,int y){return gt(1ll*x*(1-y)+1ll*(1-x)*y);}
void add2(int x,int l,int r,int ll,int rr,int t){
	if(l>=ll&&r<=rr){
		tree[x].w=merge(tree[x].w,t);
		return ;
	}
	int mid=(l+r)>>1;
	if(ll<=mid){
		if(!tree[x].l)tree[x].l=neo();
		add2(tree[x].l,l,mid,ll,rr,t);
	}
	if(rr>mid){
		if(!tree[x].r)tree[x].r=neo();
		add2(tree[x].r,mid+1,r,ll,rr,t);
	}
}
void add(int x,int l,int r,int ll,int rr,int _l,int _r,int t){
	if(ll>rr||_l>_r)return ;
	if(l>=ll&&r<=rr){
		if(!tree[x].son)tree[x].son=neo();
		add2(tree[x].son,l,n,_l,_r,t);
		return ;
	}
	int mid=(l+r)>>1;
	if(ll<=mid){
		if(!tree[x].l)tree[x].l=neo();
		add(tree[x].l,l,mid,ll,rr,_l,_r,t);
	}
	if(rr>mid){
		if(!tree[x].r)tree[x].r=neo();
		add(tree[x].r,mid+1,r,ll,rr,_l,_r,t);
	}
}
int ask2(int x,int l,int r){
	if(x==0)return 0;
	if(l==r)return tree[x].w;
	int mid=(l+r)>>1;
	if(t<=mid)return merge(tree[x].w,ask2(tree[x].l,l,mid));
	return merge(tree[x].w,ask2(tree[x].r,mid+1,r));
}
int ask(int x,int l,int r,int tt){
	if(x==0)return 0;
	int ans=ask2(tree[x].son,l,n);
	if(l==r)return ans;
	int mid=(l+r)>>1;
	if(tt<=mid)return merge(ans,ask(tree[x].l,l,mid,tt));
	else return merge(ans,ask(tree[x].r,mid+1,r,tt));
}
int pw(ll base,int t){
	ll ans=1;
	while(t){
		if(t&1)ans=ans*base%mod;
		base=base*base%mod,t>>=1;
	}
	return ans;
}
struct FS{
	struct FFS{int l,r,w,d;}tree[MAXN*4];
	void build(int x,int l,int r){
		tree[x].l=l,tree[x].r=r;tree[x].w=0,tree[x].d=0;
		if(tree[x].l==tree[x].r)return ;
		int mid=(l+r)>>1;
		build(x*2,l,mid);build(x*2+1,mid+1,r);
	}
	void down(int x){
		tree[x*2].w=merge(tree[x*2].w,tree[x].d);
		tree[x*2+1].w=merge(tree[x*2+1].w,tree[x].d);
		tree[x*2].d=merge(tree[x*2].d,tree[x].d);
		tree[x*2+1].d=merge(tree[x*2+1].d,tree[x].d);
		tree[x].d=0;
	}
	void add(int x,int l,int r,int t){
		if(l>r)return ;
		if(tree[x].l>=l&&tree[x].r<=r){tree[x].w=merge(tree[x].w,t),tree[x].d=merge(tree[x].d,t);return ;}
		if(tree[x].d)down(x);
		int mid=(tree[x].l+tree[x].r)>>1;
		if(l<=mid)add(x*2,l,r,t);
		if(r>mid)add(x*2+1,l,r,t);
	}
	int ask(int x,int l){
		if(tree[x].l==tree[x].r)return tree[x].w;
		if(tree[x].d)down(x);
		int mid=(tree[x].l+tree[x].r)>>1;
		if(l<=mid)return ask(x*2,l);
		return ask(x*2+1,l);
	}
}tr;
signed main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m;neo();tr.build(1,1,n);
    for(int i=1;i<=m;i++){
    	int op,l,r;cin>>op>>l>>r;
    	if(op==1){
    		add(1,1,n,1,l-1,l,r,pw(r-l+1,mod-2));
    		if(l!=r)add(1,1,n,l,r,l,r,2ll*pw(r-l+1,mod-2)%mod);
    		add(1,1,n,l,r,r+1,n,pw(r-l+1,mod-2));
    		tr.add(1,l,r,1ll*(r-l)*pw(r-l+1,mod-2)%mod);
    		tr.add(1,1,l-1,1);tr.add(1,r+1,n,1);
		}
		else{
			if(l==1)cout<<gt(1-tr.ask(1,r))<<"\n";
			else t=r,cout<<gt(1-ask(1,1,n,l-1))<<"\n";
		}
	}
    return 0;
}

题解：P3688 [ZJOI2017] 树状数组

文章操作

相关推荐

评论

题解：P3688 [ZJOI2017] 树状数组