救救蒟蒻
查看原帖
救救蒟蒻
996255
ikun_god楼主2024/1/21 16:34

rt,连样例都没过

#include<bits/stdc++.h>
using namespace std;
bool a[500010],tree[400010],mark[400010];
long long n,m;
void jian(int l,int r,int p){
    if (l==r){
        tree[p]=0;
    }else{
        int mid=(l+r)/2;
        jian(l,mid,p*2);
        jian(mid+1,r,p*2+1);
        tree[p]=tree[p*2]+tree[p*2+1];
    }
}
void push(int p,int l,int r){
    if (mark[p]==0){
        return ;
    }
    mark[p*2]^=1;
    mark[p*2+1]^=1;
    tree[p*2]+=(((l+r)/2)-l+1)-tree[p*2];
    tree[p*2+1]+=(r-((l+r)/2))-tree[p*2+1];
    mark[p]=0;
}
void xiu(int l,int r,int p,int cl,int cr){
    if (cl<=l && r<=cr){
        tree[p]=(r-l+1)-tree[p];
        mark[p]^=1;
        return ;
    }
    push(p,l,r);
    int mid=(l+r)/2;
    if (cl<=mid){
        xiu(l,mid,p*2,cl,cr);
    }
    if (mid<cr){
        xiu(mid+1,r,p*2+1,cl,cr);
    }
    tree[p]=tree[p*2]+tree[p*2+1];
}
long long shu(int l,int r,int p,int cl,int cr){
    if (cl>r || cr<l){
        return 0;
    }else if (cl>=l && cr<=r){
        return tree[p];
    }else{
        int mid=(cl+cr)/2;
        push(p,l,r);
        return shu(l,r,p*2,cl,mid)+shu(l,r,p*2+1,mid+1,cr);
    }
}
int main(){
    cin>>n>>m;
    jian(1,n,1);
    for (int i=1;i<=m;++i){
        int op,l,r;
        cin>>op;
        if (op==0){
            cin>>l>>r;
            xiu(1,n,1,l,r);
        }else{
            cin>>l>>r;
            cout<<shu(l,r,1,1,n)<<endl;
        }
        /*
        cout<<"trees"<<endl<<"----------"<<endl;
        for (int j=1;j<=2*n;++j){
            cout<<tree[j]<<" ";
        }
        cout<<endl<<"----------"<<endl;
        */
    }
}
2024/1/21 16:34
加载中...