此时己是凌晨两点，刚刚做了Codeforces的小A掏出了英语试卷。英语作业其实不算多，一个小时刚好可以做完。然后是一个小时可以做完的数学作业，接下来是分别都是一个小时可以做完的化学，物理，语文......小A压力巨大。
这是小A碰见了一道非常恶心的数学题，给定了一个长度为n的数列和若干个询问，每个询问是关于数列的区间表示数列的第1个数到第r个数)，首先你要统计该区间内大于等于a，小于等于b的数的个数，其次是所有大于等于a，小于等于b的，且在该区间中出现过的数值的个数。
小A望着那数万的数据规模几乎绝望，只能向大神您求救，请您帮帮他吧。
输入格式：
第一行n,m
接下来n个数表示数列
接下来m行，每行四个数l,r,a,b
输出格式：
输出m行，分别对应每个询问，输出两个数，分别为在1到i?这段区间中大小在[a,b]中的数的个数，以及大于等于a,小于等于b的，且在该区间中出现过的数值的个数（具体可以参考样例）。
输入样例#1：
3 4
1 2 2
1 2 1 3
1 2 1 1
1 3 1 3
2 3 2 3
N<=100000,M<=100000
暴力做法77分：
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,m,c[100010]; 4 bool p[10000000]; 5 int main() 6 { 7 scanf("%d%d",&n,&m); 8 for(int i=1;i<=n;i++) scanf("%d",&c[i]); 9 int l,r,a,b,ans,aans; 10 while(m--) 11 { 12 ans=0;aans=0; 13 scanf("%d%d%d%d",&l,&r,&a,&b); 14 for(int i=l;i<=r;i++) 15 if(c[i]>=a&&c[i]<=b) 16 { 17 ++ans; 18 if(!p[c[i]]) p[c[i]]=1,++aans; 19 } 20 for(int i=l;i<=r;i++) p[c[i]]=0; 21 printf("%d %d\n",ans,aans); 22 } 23 return 0; 24 }
正解：
做法不唯一，常见做法为莫队+分块或者莫队+树状数组，但是网上也有一些奇奇怪怪的方法。
求任意一段区间内在[a,b]的数字个数，很容易想到分块；但是题目有要求该区间内在[a,b]的数值种数，这又很容易联想到莫队。所以正解就是莫队+分块。例如样例的第一个询问，莫队增加在这个区间内每个数字出现的次数、该数字所在的块的元素个数（包括重复的数字）、该数所在块的不重复元素个数。然后分块询问[a,b]之间在规定区间的答案。
正解很巧妙地一点在于分块分的不仅仅是有多少个数（即n），还是数值（即color[ ]）。这也就存在一个问题，假设n很小，但是color[ ]很大又要另做处理。
如果不能理解代码的建议自行模拟样例。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=100010; 4 int n,m,L,R,block,num,posi[N],lll[N],rrr[N],sum[N],skuai[N],change[N],color[N],ans1[N],ans2[N],anss1,anss2; 5 struct node{ 6 int l,r,x,y,id; 7 }a[N]; 8 bool cmp(node aa,node bb) 9 { 10 if(posi[aa.l]==posi[bb.l]) return aa.r<bb.r; 11 else return aa.l<bb.l; 12 } 13 void build()//预处理出每个块的边界 14 { 15 block=sqrt(n);num=n/block; 16 if(n%block) num++; 17 for(int i=1;i<=num;i++) 18 lll[i]=(i-1)*block+1,rrr[i]=i*block; 19 rrr[num]=n; 20 for(int i=1;i<=n;i++) posi[i]=(i-1)/block+1; 21 } 22 void add(int col) 23 { 24 sum[col]++;skuai[posi[col]]++; 25 if(sum[col]==1) change[posi[col]]++; 26 } 27 void del(int col) 28 { 29 sum[col]--;skuai[posi[col]]--; 30 if(!sum[col]) change[posi[col]]--; 31 } 32 void find(int l,int r,int id) 33 { 34 if(posi[l]==posi[r]) 35 { 36 for(int i=l;i<=r;i++) if(sum[i]) ans1[id]+=sum[i],ans2[id]++; 37 return; 38 } 39 for(int i=l;i<=rrr[posi[l]];i++) if(sum[i]) ans1[id]+=sum[i],ans2[id]++; 40 for(int i=lll[posi[r]];i<=r;i++) if(sum[i]) ans1[id]+=sum[i],ans2[id]++; 41 for(int i=posi[l]+1;i<posi[r];i++) ans1[id]+=skuai[i],ans2[id]+=change[i]; 42 } 43 int main() 44 { 45 scanf("%d%d",&n,&m); 46 for(int i=1;i<=n;i++) scanf("%d",&color[i]); 47 build(); 48 for(int i=1;i<=m;i++) 49 { 50 scanf("%d%d%d%d",&a[i].l,&a[i].r,&a[i].x,&a[i].y); 51 a[i].id=i; 52 } 53 L=1,R=0; 54 sort(a+1,a+1+m,cmp); 55 for(int i=1;i<=m;i++) 56 { 57 while(R<a[i].r) add(color[++R]); 58 while(R>a[i].r) del(color[R--]); 59 while(L<a[i].l) del(color[L++]); 60 while(L>a[i].l) add(color[--L]); 61 find(a[i].x,a[i].y,a[i].id); 62 } 63 for(int i=1;i<=m;i++) 64 printf("%d %d\n",ans1[i],ans2[i]); 65 return 0; 66 }
原文：https://www.cnblogs.com/drurry/p/9094548.html