题目

loj题目链接

思路

研究代码发现，她的树状数组实际上询问的是\([l-1,r-1]\)的抑或和，所以题目的询问实际上就可以转化为\(l-1\)上的元素与\(r\)上的元素相同的概率。

一开始想的是，线段树维护每一个元素是\(1\)的概率是多少，然后进行数学运算，得到答案，然后发现，两点之间的概率不是相互独立的。

比如说修改了\([l,r]\)的区间，那么如果这次修改的结果是\(l\)，那么\(r\)在此次收到的影响就必然是\(0\)，但是如果按照上文的思路，我们实际上对于这两个数都施加了影响，这显然是不对的。

所以对于查询的点对而言，暴力的写法就是循环一遍每一个询问，然后具体问题具体分析。

具体问题具体分析是马克思主义活的灵魂。 ------列宁《共产主义》

struct P50{
    struct node{
        int l,r;
    }A[3005];
    int acnt;   
    void solve(){
        acnt=0;
        for(int i=1,op,l,r;i<=m;i++){
            scanf("%d%d%d",&op,&l,&r);
            if(op==1){A[++acnt]=(node){l,r};}
            else {
                LL sa=1;
                int ql,qr;
                if(l!=1){
                    ql=l-1,qr=r;
                    for(int j=1;j<=acnt;j++){
                        L=A[j].l,R=A[j].r;
                        if(cont(ql)&&cont(qr)){
                            sa=((sa*calc(R-L-1,R-L+1))%mod+(1-sa+mod)*calc(2,R-L+1)%mod)%mod;
                        }
                        else if(cont(ql)||cont(qr)){
                            sa=((sa*calc(R-L,R-L+1))%mod+(1-sa+mod)*calc(1,R-L+1)%mod)%mod;
                        }
                    }
                }
                else {
                    for(int j=1;j<=acnt;j++){
                        L=A[j].l,R=A[j].r;
                        if(cont(r)){
                            sa=((sa*calc(1,R-L+1))%mod+(1-sa+mod)*calc(R-L,R-L+1)%mod)%mod;
                        }
                        else sa=(1-sa+mod)%mod;
                    }
                }
                printf("%lld\n",sa);
            }
        }
    }
}p50;

然后怼上数据结构进行优化，不难发现，这是一个二维的模型，所以树套树，CDQ+线段树，二维线段树

这里以二维线段树为例。

这里维护的是点对之间的关系，

对于二维上的一个矩形，下标\([l,r]\)所对应的点的权值就表示的是\(l\)与\(r\)不同的概率。

然后此处仍然延续50分的分类，对于矩形上的点用线段树施加影响就行了。

然后对于\(l=1\)的点，存在一组特判。

\(sum[r]-sum[l-1]\)在错误的代码中,\(sum[l-1]\)会被直接特判为0。

所以她的询问合法的情况就变成了：
\[ 正确： [l,r]\\ 错误： [r,n]\\ sum[n]-sum[r-1]=sum[r]-sum[l-1](l=1)\\ sum[n]=val[r]\\ \]
只需要知道\(val[r]\)的值，然后根据询问的次数（每次询问\(sum[n]\)必定改变）判断二者是否相等就行了。

代码

#include<bits/stdc++.h>
#define LL long long
#define M 100005
using namespace std;
const LL mod=998244353;
int n,m;
LL qkpow(LL a,LL b){
    LL res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
LL calc(LL x,LL y){
    return x*qkpow(y,mod-2)%mod;
}
LL add(LL a,LL b){
    return (a*(mod+1-b)+b*(mod+1-a))%mod;
}
int now;
int Lson[M*400],Rson[M*400],sum[M*400],ver[M<<2],tt;
void AddY(int &p,int l,int r,int L,int R){
    if(!p)p=++tt;
    if(l==L&&r==R){sum[p]=add(sum[p],now);return;}
    int mid=(l+r)>>1;
    if(R<=mid)AddY(Lson[p],l,mid,L,R);
    else if(L>mid)AddY(Rson[p],mid+1,r,L,R);
    else {
        AddY(Lson[p],l,mid,L,mid);
        AddY(Rson[p],mid+1,r,mid+1,R);
    }
}
void AddX(int p,int l,int r,int lX,int rX,int lY,int rY){
//  cout<<l<<' '<<r<<' '<<lX<<' '<<rX<<endl;
    if(l==lX&&r==rX){
        AddY(ver[p],0,n,lY,rY);
        return;
    }
    int mid=(l+r)>>1;
    if(rX<=mid)AddX(p<<1,l,mid,lX,rX,lY,rY);
    else if(lX>mid)AddX(p<<1|1,mid+1,r,lX,rX,lY,rY);
    else {
        AddX(p<<1,l,mid,lX,mid,lY,rY);
        AddX(p<<1|1,mid+1,r,mid+1,rX,lY,rY);
    }
}
int queryY(int x,int l,int r,int Y) {
    if(l==r) return sum[x];
    int mid=(l+r)>>1,res=sum[x];
    if(Y<=mid) res=add(res,queryY(Lson[x],l,mid,Y));
    else res=add(res,queryY(Rson[x],mid+1,r,Y));
    return res;
}
int queryX(int x,int l,int r,int X,int Y) {
    if(l==r) return queryY(ver[x],0,n,Y);
    int mid=(l+r)>>1,res=queryY(ver[x],0,n,Y);
    if(X<=mid)res=add(res,queryX(x<<1,l,mid,X,Y));
    else res=add(res,queryX(x<<1|1,mid+1,r,X,Y));
    return res;
}
int main(){
//  freopen("bit.in","r",stdin);
//  freopen("bit.out","w",stdout); 
    scanf("%d%d",&n,&m);
    int ct=0;
    while(m--){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            now=calc(2,r-l+1);
            AddX(1,0,n,l,r,l,r);
            now=calc(1,r-l+1);
            if(r<n)AddX(1,0,n,l,r,r+1,n);
            AddX(1,0,n,0,l-1,l,r);
            ct=!ct;
        }
        else {
            int res=(mod+1-queryX(1,0,n,l-1,r))%mod;
            if(l==1&&ct)res=(1-res+mod)%mod;
            printf("%d\n",res); 
        }
    }
    return 0;
}