cf221 D. Little Elephant and Array

题解真的是太神奇了2333

用离线和树状数组（为什么感觉和HH的项链是的，什么鬼），比较巧妙的是他把整个数列分成几段。用一个vector来记录每个数出现的位置。一共就是data[a[i]][sz]—data[a[i]][sz-a[i]],data[a[i]][sz-a[i]]—-data[a[i]][sz-a[i]-1],0—-data[a[i]][sz-a[i]-1]，第一个区间的数是1，第二个区间是-1，第三个是0，这样区间加减的话就直接出来了是不是成立一共有a[i]个a[i]而且，还可以往后递推，太神奇了2333

 #include<bits/stdc++.h>
 #define lowbit(x) x&(-x)
 #define LL long long
 #define N 200005
 #define M 1000005
 #define mod 1000000007LL
 #define inf 0x7ffffffff
 using namespace std;
 inline int ra()
 {
     int x=,f=; char ch=getchar();
     while (ch<'' || ch>''){if (ch=='-') f=-; ch=getchar();}
     while (ch>='' && ch<=''){x=x*+ch-''; ch=getchar();}
     return x*f;
 }
 int c[N],ans[N],a[N],n,m;
 struct node{
     int l,r,id;
     bool operator < (const node t) {return r<t.r;}
 }q[N];
 void add(int i, int v)
 {
     while (i<=n)
     {
         c[i]+=v;
         i+=lowbit(i);
     }
 }
 int ask(int x)
 {
     int sum=;
     while (x>)
     {
         sum+=c[x];
         x-=lowbit(x);
     }
     return sum;
 }
 vector<int> data[N];
 int main()
 {
     int sz;  n=ra();m=ra();
     for (int i=; i<=n; i++) a[i]=ra();
     for (int i=; i<=m; i++)
     {
         q[i].l=ra(),q[i].r=ra();
         q[i].id=i;
     }
     sort(q+,q+m+);
     for (int i=,k=; i<=n; i++)
     {
         if (a[i]<=n)
         {
             data[a[i]].push_back(i);
             sz=data[a[i]].size();
             if (sz>=a[i])
             {
                 add(data[a[i]][sz-a[i]],);
                 if (sz>a[i]) add(data[a[i]][sz-a[i]-],-);
                 if (sz>a[i]+) add(data[a[i]][sz-a[i]-],);
             }
         }
         while (q[k].r==i && k<=m)
         {
             ans[q[k].id]=ask(q[k].r)-ask(q[k].l-);
             k++;
          }
     for (int j=; j<=n; j++)
         printf("%d  ",ask(j));
         cout<<endl;
     }
     for (int i=; i<=m; i++)
         printf("%d\n",ans[i]);
     return ;
 }