属于可怜出的小清新数据结构题呢
题目解析
因为全部都在模\(2\)意义下,因此相当于单点异或,查询区间异或和.
因此我们用一个二维点\(f(x,y)\)表示\(a_x\)和\(a_y\)相等的概率.
修改
假设我们操作\([l,r]\),那么它会对多少点造成影响呢?
假如有一个点\((x,y)\),满足\(l\leq x\leq y\leq r\),那么会有\(\frac{2}{r-l+1}\)的概率使\((x,y)\)的相同性取反(即相同变不同,不同变相同). 那么操作过一次之后\(f(x,y)=f(x,y)*(1-\frac{2}{r-l+1})+(1-f(x,y))*\frac{2}{r-l+1}\). 这个式子还是比较显然的.假如有一个点\((x,y)\),满足\(x\leq l\leq y\leq r\),那么会有\(\frac{1}{r-l+1}\)的概率使\((x,y)\)的相同性取反(即相同变不同,不同变相同).
那么操作过一次之后\(f(x,y)=f(x,y)*(1-\frac{1}{r-l+1})+(1-f(x,y))*\frac{1}{r-l+1}\). 这个式子也是比较显然的.对于\(l\leq x\leq r\leq y\)同理.
询问
直接输出\(f(x,y)\)即可.
实现
现在思路已经比较明显了.
对于每次修改,我们相当于修改\(3\)个矩形. 对于每次询问,我们相当于询问一个点的值. 树套树实现即可. 因为是单点询问,标记永久化.坑点
注意到当查询为\(0\)时,会直接返回\(0\).这种情况相当于前缀异或等于后缀异或的概率,注意特判.
代码如下
#include#include #include #include #include #include #define N (100010)#define P (998244353)#define inf (0x7f7f7f7f)#define rg register int#define Label puts("NAIVE")#define spa print(' ')#define ent print('\n')#define rand() (((rand())<<(15))^(rand()))typedef long double ld;typedef long long LL;typedef unsigned long long ull;using namespace std;inline char read(){ static const int IN_LEN=1000000; static char buf[IN_LEN],*s,*t; return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);}template inline void read(T &x){ static bool iosig; static char c; for(iosig=false,c=read();!isdigit(c);c=read()){ if(c=='-')iosig=true; if(c==-1)return; } for(x=0;isdigit(c);c=read())x=((x+(x<<2))<<1)+(c^'0'); if(iosig)x=-x;}inline char readchar(){ static char c; for(c=read();!isalpha(c)&&!isdigit(c);c=read()) if(c==-1)return 0; return c;}const int OUT_LEN = 10000000;char obuf[OUT_LEN],*ooh=obuf;inline void print(char c) { if(ooh==obuf+OUT_LEN)fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf; *ooh++=c;}template inline void print(T x){ static int buf[30],cnt; if(x==0)print('0'); else{ if(x<0)print('-'),x=-x; for(cnt=0;x;x/=10)buf[++cnt]=x%10+48; while(cnt)print((char)buf[cnt--]); }}inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}struct xds{ int ls,rs,w;}a[35000010];int rt,n,m,ind,ind2,ans,inv[N],T[N<<2];int ksm(int a,int p){ int res=1; while(p){ if(p&1)res=1ll*res*a%P; a=1ll*a*a%P,p>>=1; } return res;}void merge(int &x,int y){x=((2ll*x*y%P-x-y+1)%P+P)%P;}void Modify(int &x,int L,int R,int l,int r,int w){ if(!x)x=++ind2,a[x].w=1; if(L==l&&R==r)return merge(a[x].w,w); int mid=(L+R)>>1; if(r<=mid)Modify(a[x].ls,L,mid,l,r,w); else if(l>mid)Modify(a[x].rs,mid+1,R,l,r,w); else Modify(a[x].ls,L,mid,l,mid,w),Modify(a[x].rs,mid+1,R,mid+1,r,w);}void modify(int &x,int L,int R,int lx,int ly,int rx,int ry,int w){ if(!x)x=++ind; if(L==lx&&R==ly)return Modify(T[x],1,n,rx,ry,w); int mid=(L+R)>>1; if(ly<=mid)modify(a[x].ls,L,mid,lx,ly,rx,ry,w); else if(lx>mid)modify(a[x].rs,mid+1,R,lx,ly,rx,ry,w); else modify(a[x].ls,L,mid,lx,mid,rx,ry,w),modify(a[x].rs,mid+1,R,mid+1,ly,rx,ry,w); }void Query(int x,int L,int R,int p){ if(!x)return;merge(ans,a[x].w); if(L==R)return;int mid=(L+R)>>1; if(p<=mid)Query(a[x].ls,L,mid,p); else Query(a[x].rs,mid+1,R,p);}void query(int x,int L,int R,int px,int py){ if(!x)return;if(T[x])Query(T[x],1,n,py); if(L==R)return;int mid=(L+R)>>1; if(px<=mid)query(a[x].ls,L,mid,px,py); else query(a[x].rs,mid+1,R,px,py);}int main(){ read(n),read(m),ind2=400000; for(int i=0;i<=n;i++)inv[i]=ksm(i,P-2); for(int t=0,op,l,r;m;m--){ read(op),read(l),read(r); if(op==1){ int len=r-l+1; t++; modify(rt,0,n,l,r,l,r,(1-2*inv[len]%P+P)%P); modify(rt,0,n,0,l-1,l,r,(1-inv[len]+P)%P); if(r+1<=n)modify(rt,0,n,l,r,r+1,n,(1-inv[len]+P)%P); } else{ ans=1,query(rt,0,n,l-1,r); if(l==1&&(t&1))ans=(1-ans+P)%P; print(ans),ent; } } return flush(),0;}