题解 P2574 【XOR的艺术】

zhenglier · 2018-09-09 19:58:53 · 题解

看题解中好像没有分块的，于是本蒟蒻就写了个分块

对于这种数据比较水的题目，分块甚至会比线段树更方便。 因为线段树代码非常长，且点一下，调一年。

分块的思想非常简单，就是大块维护，小块暴力。把长度为n的数列分到sqrt(n)块，预处理每一个块的和，每个块存一个懒标记。

对于每一个询问，在区间内的块直接把和加到答案里，两头的数暴力加入。

对于每一个查询，在区间内的块直接修改懒标记，两头的数暴力修改。

#include<bits/stdc++.h>
using namespace std;
int n,T,len;
int k=1,a[200010],bk[200010],bl[500][500],sum[500],lan[500];
inline int read()
{//快读？
    char c=getchar();
    for(;c!='0' && c!='1';c=getchar());
    return (int)(c-'0');
 } 
 inline int query(int l,int r)
 {//求和
    int i,ret=0;
    for(i=l;bk[i]==bk[l] && i<=r;++i){
        if(lan[bk[i]]){
            ret+=(a[i]^1);
         }else ret+=a[i];
     }//处理前半部分
     for(;i+len<=r;i+=len){
        if(lan[bk[i]]){
            ret+=(bl[bk[i]][0]-sum[bk[i]]);
         }else ret+=sum[bk[i]];

     }//处理块
     for(;i<=r;++i){
        if(lan[bk[i]]){
            ret+=a[i]^1;
         }
         else ret+=a[i];
     }//处理后半部分
     return ret;
 }
 inline void add(int l,int r)
 {
    int i;
    for(i=l;bk[i]==bk[l] && i<=r;++i){
        if(lan[bk[i]]){
            if(a[i]){
                sum[bk[i]]--;
             }
             else sum[bk[i]]++;
         }
         else if(a[i]){
         sum[bk[i]]--;
         } else sum[bk[i]]++;
        a[i]^=1;
     }//处理前半部分
     for(;i+len<=r;i+=len){
        lan[bk[i]]^=1;
     }//处理块
     for(;i<=r;++i){
         if(lan[bk[i]]){
            if(a[i]){
                sum[bk[i]]--;
             }
             else sum[bk[i]]++;
         }
         else if(a[i]){
         sum[bk[i]]--;
         } else sum[bk[i]]++;
        a[i]^=1;
     }//处理后半部分
 }
int main()
{
    cin>>n>>T;
    len=(int)sqrt(n);
    for(int i=1;i<=n;++k){
        int j=1;
        for(;j<=len && i<=n;++j,++i){
            a[i]=bl[k][j]=read();
            bk[i]=k;
            sum[k]+=bl[k][j];
        }
        bl[k][0]=j-1;
    }
//  for(int i=1;i<=n;++i)cout<<a[i];puts("");
    int _a,_b,_c;
    while(T--){
        scanf("%d%d%d",&_a,&_b,&_c);
        if(_a==0){
            add(_b,_c);
        }
        if(_a==1){
            printf("%d\n",query(_b,_c));
        }
//       for(int i=1;i<=n;++i)
//           if(lan[bk[i]]){
//              cout<<(a[i]^1);
//           }else cout<<a[i];
//      puts("");
    }
}