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

· · 题解

快要noip了，该写些题解攒攒rp了（逃）

看到题解里那么多线段树啊，树状数组啊，本蒟蒻表示：这都是什么鬼东西？

在所有高级数据结构中，树状数组是码量最小的，跑的也基本是最快的，但理解很难，并且支持的操作很少；线段树的码量，相信写过线段树题的童鞋都亲身体验过这种恐怖（那些3min写完splay的巨佬不要d我），理解虽然简单，但一题调一辈子啊！

所以说到这里，本蒟蒻想表达什么呢？

分块大法吼啊！

有人会说：分块不是n√n的复杂度吗？怎么能跟nlogn的数据结构相提并论呢？或者说，分块在联赛中，有什么优势呢？

首先，虽然他复杂度高，但他能维护的东西多呀！（你看看n²的暴力什么不能维护）

而且，因为有时线段树有巨大的常数，反而比分块跑的慢！（比如洛谷P2801）

再者说，如果联赛一道题，好多方法都能做，你是用调一辈子的线段树呢，还是十分暴力好写的分块呢？

废话了这么多，也是想让大家知道，分块也是一种很好的算法。

那分块是怎么实现的呢？顾名思义，分块就是把一个区间分成好几个小区间，至于是几个呢，因题而异，但大部分题的复杂度都是n√n，所以默认是把区间分成√n块。如果某题用分块复杂度带log，就让块分的更多一些，大概是乘个log（我也不知道为什么）。

哪怎么维护呢？当询问某段区间时，把区间覆盖的整块打上一个tag标记，两边离散的块呢，就暴力就好了。有人会说，这么简单？当然。（不简单本蒟蒻怎么可能会写）

还有要注意的是询问区间如果在一个块里要特判，所以要多大几个if。（虽然有些麻烦，但都是板儿啊）

分块大体差不多说完了，但这个算法十分灵活，准确的说，分块这种思想十分可贵，能用到很多其他题上。

最后，本题其实不难，把分块板子粘过来，把加改成xor就行了。如果想看分块的板子，hzwer大佬博客里有，可以去看一看（巨佬的码风是真好看啊）

下贴代码：

#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<queue>
#define rint register int
#define maxn 200010
using namespace std;
inline int read()
{
    int s=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){ch=getchar();if(ch=='-')f=-1;}
    while(ch>='0'&&ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
    return s*f;
}
inline void write(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
    return ;
}
int n,m,blo,o;
int bl[maxn],v[maxn],t[maxn],atag[maxn],sum[maxn],L[maxn],R[maxn];
inline void change(int l,int r)
{
    if(bl[l]==bl[r])
    {
        for(rint i=l;i<=r;++i)
        {
            if(v[i]) v[i]=0,--sum[bl[l]];
            else v[i]=1,++sum[bl[l]];
        } 
        return ;
    }
    for(rint i=l;i<=R[bl[l]];++i) 
    {
        if(v[i]) v[i]=0,--sum[bl[l]]; 
        else v[i]=1,++sum[bl[l]];
    }
    for(rint i=L[bl[r]];i<=r;++i) 
    {
        if(v[i]) v[i]=0,--sum[bl[r]];
        else v[i]=1,++sum[bl[r]];
    }
    for(rint i=bl[l]+1;i<=bl[r]-1;++i) atag[i]=1-atag[i];
}
inline int query(int l,int r)
{
    int ans=0;
    if(bl[l]==bl[r])
    {
        for(rint i=l;i<=r;++i) 
            if(v[i]^atag[bl[l]]) ++ans;
        return ans;
    }
    for(int i=l;i<=R[bl[l]];++i) 
        if(v[i]^atag[bl[l]]) ++ans;
    for(int i=L[bl[r]];i<=r;++i) 
        if(v[i]^atag[bl[r]]) ++ans;
    for(int i=bl[l]+1;i<=bl[r]-1;++i)
    {
        if(atag[i]) ans+=(R[i]-L[i]+1)-sum[i];
        else ans+=sum[i];
    }        
    return ans;
}
int main()
{
    n=read(),m=read();blo=sqrt(n);
    n%blo ? (o=n/blo+1) : (o=n/blo);
    for(rint i=1;i<=n;++i)
    {
        v[i]=0;
        bl[i]=(i-1)/blo+1;
        if(v[i]) ++sum[bl[i]];
    }
    for(rint i=1;i<=o;++i)
    {
        L[i]=(i-1)*blo+1;
        R[i]=i*blo;
    }
    while(m--)
    {
        int p=read(),l=read(),r=read();
        if(p==0) change(l,r);
        if(p==1) write(query(l,r)),puts(" ");
    }
    return 0;
}

谢谢大家