题解 P2846 【[USACO08NOV]光开关Light Switching】

· · 题解

线段树这方面……线段树是不可能写的，这辈子不可能写线段树的。

题意就是让你处理一个01数组的 区间异或1 和 区间求和。

显然本题可以分块。

不熟悉分块的同学可以去看「分块」数列分块入门1 – 9 by hzwer。

我们把d个元素分为一块，共有n/d块。对于每次操作，我们处理区间包含的每个整块和两个不完整的块。

在本题中，对于每个整块，我们记录整个块被异或的次数(mod 2)和块内的答案；对于每个元素，记录它被单个异或的次数(mod 2)。

实现时需要注意代码中一些+1，-1的玩意，并且分清楚块的下标和数组的下标。

显然，当d=\sqrt n时,时间复杂度最优秀。

时间复杂度O(n\sqrt n)。

//巨丑无比的代码
#include<cstdio>
#include<cmath>
inline int read(){
    int a=0;char c=getchar();
    for(;c<48||c>57;c=getchar());for(;c>47&&c<58;a=a*10+c-48,c=getchar());
    return a;
}
inline int min(int a,int b){return a<b?a:b;}
const int N=1e5+1,D=322;
int n,m,d,a[N],da[D],ds[D],p[N];
//n,m,块的大小，元素被单个异或的次数(mod 2)，整个块被异或的次数(mod 2)，块内的答案，元素所在块的编号
inline int Xor(int l,int r){
    for(int i=l;i<=min(p[l]*d,r);i++)ds[p[i]]+=a[i]^da[p[i]]?-1:1,a[i]^=1;
    if(p[l]!=p[r])for(int i=r;i>p[r]*d-d;i--)ds[p[i]]+=a[i]^da[p[i]]?-1:1,a[i]^=1;
    for(int j=p[l]+1;j<p[r];j++)da[j]^=1,ds[j]=d-ds[j];
}
inline int Sum(int l,int r){
    int s=0;
    for(int i=l;i<=min(p[l]*d,r);i++)s+=a[i]^da[p[i]];
    if(p[l]!=p[r])for(int i=r;i>p[r]*d-d;i--)s+=a[i]^da[p[i]];
    for(int j=p[l]+1;j<p[r];j++)s+=ds[j];
    return s;
}
int main(){
    d=sqrt(n=read());m=read();
    for(int i=1;i<=n;i++)p[i]=(i-1)/d+1;
    for(int o,l,r;m--;)
      o=read(),l=read(),r=read(),
      o?printf("%d\n",Sum(l,r)):Xor(l,r);
    return 0;
}