BZOJ-3236: [Ahoi2013]作业

Desription

N=100000,M<=1000000

发现不满足区间减法，所以不能用主席树。
莫队+树状数组的话发现区间变动的时间复杂度为m√nlogn，会TLE。然而发现查询次数只有m次，可以使用O(1)修改，√n查询的分块。莫队+分块:复杂度O(m√n)
讲一下bug的心得：
1.lz1[w[l]/blo]+=(s[w[l++]]==0)=>lz1[w[++l]/blo]+=(s[w[l]]等号是先处理右侧的。。。嗯。。。没事还是零基础的写法比较稳。。。
2.分块一定要先判断是否在一个块内！！！分块一定要先判断是否在一个块内！！！分块一定要先判断是否在一个块内！！！最好写成函数！！！函数！！！函数！！！

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,blo,w[101000],s[101000],lz1[1100],lz2[1100],bl[101000],ans1[1001000],ans2[1001000];
inline void read(int &x)
{
    x=0; char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
}
struct node {int l,r,a,b,bl,id;}a[1001000];
bool cmp1(node x,node y){return x.bl==y.bl?x.r<y.r:x.bl<y.bl;}
void work(int l,int r,int &x,int &y)
{
    int j;
    if(bl[l]==bl[r])
    {
        for(j=l;j<=r;++j) x+=s[j],y+=(s[j]>0);
        return ;
    }
    for(j=l;j<bl[l]*blo+blo;++j) x+=s[j],y+=(s[j]>0);
    for(j=bl[r]*blo;j<=r;++j) x+=s[j],y+=(s[j]>0);
    l=bl[l]+1; r=bl[r]-1;
    for(j=l;j<=r;++j) x+=lz1[j],y+=lz2[j];
}
int main()
{
    scanf("%d%d",&n,&m); blo=sqrt(1.0*n); int i,j;
    for(i=0;i!=n;++i) read(w[i]);
    for(i=1;i<=n;++i) bl[i]=i/blo;
    for(i=1;i<=m;++i)
    {
        read(a[i].l); read(a[i].r);
        a[i].l--; a[i].r--;
        read(a[i].a); read(a[i].b);
        a[i].bl=a[i].l/blo; a[i].id=i;
    }
    sort(a+1,a+m+1,cmp1);
    int l=1,r=0,id;
    for(i=1;i<=m;++i)
    {
        id=a[i].id;
        while(r<a[i].r) {r++; lz2[bl[w[r]]]+=(s[w[r]]==0); s[w[r]]++; lz1[bl[w[r]]]++;}
        while(l>a[i].l) {l--; lz2[bl[w[l]]]+=(s[w[l]]==0); s[w[l]]++; lz1[bl[w[l]]]++;}
        while(r>a[i].r) {s[w[r]]--; lz2[bl[w[r]]]-=(s[w[r]]==0); lz1[bl[w[r]]]--; r--;}
        while(l<a[i].l) {s[w[l]]--; lz2[bl[w[l]]]-=(s[w[l]]==0); lz1[bl[w[l]]]--; l++;}
        work(a[i].a,a[i].b,ans1[id],ans2[id]);
    }
    for(i=1;i<=m;++i) printf("%d %d\n",ans1[i],ans2[i]);
    return 0;
}