属于可怜出的小清新数据结构题呢
题目链接 https://loj.ac/problem/2251
解析
因为全部都在模 \(2\) 意义下, 因此相当于单点异或, 查询区间异或和.
如果你对树状数组足够熟悉, 那么你会发现可怜写了一个单点加求后缀和的程序.
因此 \([l,r]\) 正确的概率就要使 \(a_{l-1}\oplus a_l\oplus a_{l+1}\oplus ...\oplus a_n=a_r\oplus a_{r+1}\oplus...\oplus a_n\)
即 \(a_{l-1}=a_r\)
于是我们用线段树维护这个问题好像就做完了
当然不对.
假如我们在 \([2,3]\) 中等概率取反, 然后查询 \(a_2\) 与 \(a_3\) 相等的概率, 江道理应该是 \(0\), 但是我们的线段树会得到 \(\frac{1}{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<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- #include<cmath>
- #include<vector>
- #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<class T>
- 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<class T>
- 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;
- }
来源: http://www.bubuko.com/infodetail-2908624.html