蒟蒻分块10分求助QwQ
查看原帖
蒟蒻分块10分求助QwQ
332022
ChthollyMeow楼主2020/5/27 17:54
  • 大概思想是分块
  • 样例过了
  • 曾经把题解复制下来随便造数据测输出,完全一样
  • 内部中途变量也完全一样
  • 然鹅偏偏就是W ⁣A\color{red}\text{W\!A}
  • 代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,m,sq;
int a[100005],f[100005];
int tag[100005],ans[100005];
/*
void print(int x[],int k){
    for(int i=1;i<=k;i++){
        cout<<x[i]<<" ";
    }
    cout<<endl;
}
*/
//调试用
void change(int x,int y){
    for(int i=x;i<=min(y,f[x]*sq);i++){
        ans[f[x]]-=a[i]^tag[f[x]];
        a[i]^=1;
        ans[f[x]]+=a[i]^tag[f[x]];
    }//散块暴力
    for(int i=f[x]+1;i<=f[y]-1;i++){
        ans[i]=sq-ans[i];
        tag[i]^=1;
    }//整块直接改
    if(f[x]!=f[y]){
        for(int i=(f[y]-1)*sq+1;i<=y;i++){
            ans[f[y]]-=tag[f[y]]^a[i];
            a[i]^=1;
            ans[f[y]]+=tag[f[y]]^a[i];
        }
    }
}
int query(int x,int y){
    int sum=0;
    for(int i=x;i<=min(y,f[x]*sq);i++){
        sum+=a[i]^tag[f[x]];
    }//散块暴力
    for(int i=f[x]+1;i<=f[y]-1;i++){
        sum+=ans[i];
    }//整块直接查
    for(int i=(f[y]-1)*sq+1;i<=y;i++){
        sum+=a[i]^tag[f[y]];
    }
    return sum;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    sq=sqrt(n);
    for(int i=1;i<=n;i++){
        f[i]=(i-1)/sq+1;
    }//分块
    while(m--){
        int cmd,r,s;
        cin>>cmd>>r>>s;
        if(cmd==0){
            change(r,s);
        }
        else{
            int tmp=query(r,s);
            cout<<tmp<<endl;
        }
//        print(a,n);
//        print(f,n);
//        print(tag,n);
//        print(ans,n);
//        cout<<"\n\n\n";
//调试用
    }
    return 0;
}
2020/5/27 17:54
加载中...