P3688 [ZJOI2017] 树状数组 题解

Link

P3688 [ZJOI2017] 树状数组

Solve

显然，这道题他求成了后缀和

所以我们发现，对于一个询问，其实是在询问 ((l-1,r))这两个点相同的概率

考虑用二维线段树来维护

设二元组(x,y)的值表示位置为x的点和位置为y的点相同的概率

那么我们发现，对于一个操作(l,r)，设这次操作的区间长度为len

他会对三种类型的二元组产生影响

1.左端点在(l,r)内且右端点不在(l,r)的二元组

2.右端点在(l,r)内且左端点不在(l,r)的二元组

3.左右端点同时在(l,r)内的二元组

对于第一种和第二种二元组，这次修改有1/len的概率取反它们，对于第3种二元组这次修改有2/len的概率取反它们

然后就变成一个矩阵修改，点查问题

这道题可以用标记永久化来处理，会好些很多

我再写树套树就是。。。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int TT=998244353,maxn=100010;

struct IO{
    static const int S=1<<21;
    char buf[S],*p1,*p2;int st[105],Top;
    ~IO(){clear();}
    inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
    inline void pc(const char c){Top==S&&(clear(),0);buf[Top++]=c;}
    inline char gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}
    inline IO&operator >> (char&x){while(x=gc(),x==' '||x=='
'||x=='r');return *this;}
    template<typename T>inline IO&operator >> (T&x){
        x=0;bool f=0;char ch=gc();
        while(ch<'0'||ch>'9'){if(ch=='-') f^=1;ch=gc();}
        while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=gc();
        f?x=-x:0;return *this;
    }
    inline IO&operator << (const char c){pc(c);return *this;}
    template<typename T>inline IO&operator << (T x){
        if(x<0) pc('-'),x=-x;
        do{st[++st[0]]=x%10,x/=10;}while(x);
        while(st[0]) pc('0'+st[st[0]--]);
		return *this;
    }
}fin,fout;
int N,M,cnt;
int rt[maxn*4+1000];
struct node{int ls,rs,v;}tr[maxn*400];
inline LL inv(LL a){LL r=1;for(LL p=TT-2;p;p>>=1,a=(a*a)%TT)(p&1)&&(r=(r*a)%TT,0);return r;}
LL calc(LL p,LL q){LL res = p * q % TT; res = (res + (1 - p) * (1 - q) % TT) % TT; return (res + TT) % TT;}
void changey(int &k,int l,int r,int x,int y,LL p){
	if(!k){k=++cnt;tr[k].v=1;}
	if(x<=l&&r<=y){tr[k].v=calc(tr[k].v,p);return ;}
	int mid=(r-l>>1)+l;
	if(x<=mid) changey(tr[k].ls,l,mid,x,y,p);
	if(y>mid)  changey(tr[k].rs,mid+1,r,x,y,p);
}

void changex(int k,int l,int r,int lx,int rx,int ly,int ry,LL p){
	if(lx<=l&&rx>=r){changey(rt[k],1,N,ly,ry,p);return ;}
	int mid=(r-l>>1)+l;
	if(lx<=mid) changex(k<<1,l,mid,lx,rx,ly,ry,p);
	if(rx>mid)  changex(k<<1|1,mid+1,r,lx,rx,ly,ry,p);
}

LL asky(int k,int l,int r,int pos){
	if(!k) return 1;
	if(l==r) return tr[k].v;
	int mid=(r-l>>1)+l;
	if(pos<=mid) return calc(tr[k].v,asky(tr[k].ls,l,mid,pos));
	else return calc(tr[k].v,asky(tr[k].rs,mid+1,r,pos));
}

LL askx(int k,int l,int r,int posx,int posy){
	if(l==r)return asky(rt[k],1,N,posy);
	int mid=(r-l>>1)+l;
	if(posx<=mid)return calc(askx(k<<1,l,mid,posx,posy),asky(rt[k],1,N,posy));
	else  return calc(askx(k<<1|1,mid+1,r,posx,posy),asky(rt[k],1,N,posy));
}

int main(){
	freopen("P3688.in","r",stdin);
	freopen("P3688.out","w",stdout);
	fin>>N>>M;
	LL p;int opt,l,r;
	while(M--){
		fin>>opt>>l>>r;
		if(opt==1){
			p=inv(r-l+1);
			if(l>1)changex(1,0,N,1,l-1,l,r,(1-p+TT)%TT),
			changex(1,0,N,0,0,1,l-1,0);
			if(r<N)changex(1,0,N,l,r,r+1,N,(1-p+TT)%TT),changex(1,0,N,0,0,r+1,N,0);
			changex(1,0,N,l,r,l,r,(1-2ll*p+TT)%TT);changex(1,0,N,0,0,l,r,p);
		}
		else fout<<askx(1,0,N,l-1,r)<<'
';
	}
	return 0;
}