（CodeForces - 220B）Little Elephant and Array（莫队）

题目链接：Little Elephant and Array - CodeForces 220B - Virtual Judge (ppsucxtt.cn)

问题是先给我们n个数字，然后给我们m个问题，每个问题包括两个数字l和r，让我们找出区间[ l , r ]x出现x次有多少次内满足？

这显然是莫队要求的。他满足了莫队的主题要求。莫队的主题模板相对固定。我不多说模板。我主要谈谈他的add函数和sub函数以及一些注意事项。

首先说一下add函数，我们每次增加一个值x，就用cnt记录一下，如果这个值增加后在当前范围内出现x次，说明原来出现了x-一次，我们可以添加答案1，如果我们在当前范围内增加这个值x 一次，说明这个值之前在当前范围内出现过x次，这个时候我们要减少答案。

让我们谈谈sub函数，我们每次减少一个值，也使用它cnt记录一下，如果这个值减少后在当前范围内出现x次，说明原来出现了x 一次，我们可以添加答案1，如果我们在当前范围内降低这个值x-一次，说明这个值之前在当前范围内出现过x次，这个时候我们要减少答案。

以下是注意事项，a数组的值很大，但是如果稍微分析一下题目要求的数量，就可以知道满足题目要求的数量必须小于等于n，所以x大于n的时候可以直接不处理。

以下是代码：

#include #include #include #include #include #include using namespace std; const int N=1e5 10; int a[N],cnt[N],ans,sum[N]; struct node{  int id,pl,l,r; }p[N]; bool cmp(node a,node b) {  if(a.pl!=b.pl) return a.pl100000) return ;//当x>100000时，x不可能出现x  cnt[x]  ;  if(cnt[x]==x) ans  ;  if(cnt[x]==x 1) ans--; } void sub(int x) {  if(x>100000) return ;//当x>100000时，x不可能出现x  cnt[x]--;  if(cnt[x]==x) ans  ;  if(cnt[x]==x-1) ans--; } int main() {  int n,m;  scanf("%d%d",&n,&m);  int pl=sqrt(n);  for(int i=1;i<=n;i  )   scanf("%d",&a[i]);  for(int i=1;i<=m;i  )  {   scanf("%d%d",&p[i].l,&p[i].r);   p[i].id=i;   p[i].pl=(p[i].l-1)/pl 1;  }  sort(p 1,p m 1,cmp);  int l=1,r=0;  for(int i=1;i<=m;i  )  {   while(lp[i].l)   {    l--;    add(a[l]);   }   while(rp[i].r)   {    sub(a[r]);    r--;   }   sum[p[i].id]=ans;  }  for(int i=1;i<=m;i  )   printf("%d\n",sum[i]);  return 0; }