莫队卡常

yukuai26 · 2018-05-10 22:22:09 · 题解

听说加强数据狂魔chen_zhe加强了数据

我当然选择继续用莫队写啊

正常莫队80分，这边加一些优化即可

当a与b的块相同时，如果是奇数块按r从小到大，否则从大到小

极限长度/2

另外，因为后面的数据可能是特意卡莫队

所以可以调整块大小为常数（这个我没试

要善于运用register inline等数据

善于合并语句 如 ans+=(++tong[num[x]]==1)

这样开上o2即可用莫队有几率干掉加强的数据

https://www.luogu.org/recordnew/show/7220178

此为ac情况。

不过我机房的人尝试用我的程序似乎有些人tle了。

可能这看脸的吧（逃

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#define ll long long
#define N 500005
#define inf 1000000005
#define mod 1000000007
#include <map>
#define put putchar('\n')
#define re register 
using namespace std;
inline int read(){char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
inline void wr(int x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(int x){wr(x);put;}inline void wri(int x){wr(x);putchar(' ');}
int c[N],tong[1000005],n,m,s,l,r;
int t,num;
struct xx{
    int l1,l,r,i;
    int ans1;
}z[N];
bool cmp(xx a,xx b){
    return a.l1==b.l1?(a.l1&1)?a.r<b.r:a.r>b.r:a.l1<b.l1;
}
inline void add(int x){
    num+=(++tong[c[x]]==1);
}
inline void dec(int x){
    num-=(--tong[c[x]]==0);
}
bool cmp2(xx a,xx b){
    return a.i<b.i;
}
int main(){
    //freopen(".in","r",stdin);freopen(".out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++) c[i]=read();
    s=sqrt(n);m=read();
    for (int i=1;i<=m;i++){
        z[i].l=read();z[i].r=read();z[i].l1=z[i].l/s;z[i].i=i;
    }
    sort(z+1,z+m+1,cmp);
    re int l=0,r=0;
    for (int i=1;i<=m;i++){
        while (r<z[i].r) add(++r);
        while (r>z[i].r) dec(r--);
        while (l>z[i].l) add(--l);
        while (l<z[i].l) dec(l++);
        z[i].ans1=num;
    }
    sort(z+1,z+m+1,cmp2);
    for (int i=1;i<=m;i++){
        wrn(z[i].ans1);
    }
    return 0;
}