https://www.luogu.org/problem/show?pid=3730
题目背景
will在曼哈顿开了一家交易所，每天，前来买卖股票的人络绎不绝。
现在，will想要了解持股的情况。由于来交♂易的人实在是太多了，需要你写一个程序来帮他完成这个任务。
题目描述
-
前来交易的N个人排成了一行，为了简便起见，每个人都只持有一种股票。
-
不同的的人可能会持有相同的股票。
-
定义一种股票的热度为持有该股票的人数。
- 每次，will会给出这样的询问：在一段连续区间的人之中，热度第k小的股票的热度是多少？
输入输出格式
输入格式：
-
第一行两个正整数N，M，分别表示人数和询问的次数；
-
接下来一行N个正整数，表示每个人所持的股票
。
- 接下来M行，每行三个正整数l，r，k，表示询问区间
中的第k小的热度，保证
。
输出格式：
-
对于每个询问，输出一行一个数，表示区间[l, r]中的第k小的热度值。
- 如果k大于区间里股票的种类数，输出-1。
输入输出样例
输入样例#1：
4 4 2 3 3 3 1 4 1 1 4 2 1 3 2 1 3 3
输出样例#1：
1 3 2 -1
说明
对于20%的数据，；
对于另外10%的数据，所有的；
对于100%的数据，；
莫队
离散化
维护每种股票的出现次数sum
维护出现次数（热度）为i的有几种股票，即出现次数的出现次数cnt
同时，对cnt分块查询
#include<cmath> #include<cstdio> #include<algorithm> #define N 100001 using namespace std; int n,m,siz; int key[N],hashh[N]; int bl[N],ans[N]; int sum[N],cnt[N],block[N],num; struct node { int l,r,id,k; bool operator < (node p)const { if(bl[l]!=bl[p.l]) return bl[l]<bl[p.l]; if(r!=p.r) return r<p.r; return k<p.k; } }e[N]; void read(int &x) { x=0; char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } } inline void update(int pos,int w) { block[bl[sum[hashh[pos]]]]--; cnt[sum[hashh[pos]]]--; if(w) sum[hashh[pos]]++; else sum[hashh[pos]]--; block[bl[sum[hashh[pos]]]]++; cnt[sum[hashh[pos]]]++; } inline int query(int w) { int i; for(i=1;i<=siz;i++) if(w-block[i]>0) w-=block[i]; else break; for(int j=(i-1)*siz+1;j<=i*siz;j++) { w-=cnt[j]; if(w<=0) return j; } return -1; } int main() { read(n); read(m); siz=sqrt(n); for(int i=1;i<=n;i++) bl[i]=(i-1)/siz+1; for(int i=1;i<=n;i++) read(key[i]),hashh[i]=key[i]; sort(key+1,key+n+1); key[0]=unique(key+1,key+n+1)-(key+1); for(int i=1;i<=n;i++) hashh[i]=lower_bound(key+1,key+key[0]+1,hashh[i])-key; int l,r,w; for(int i=1;i<=m;i++) { scanf("%d%d%d",&e[i].l,&e[i].r,&e[i].k); e[i].id=i; } sort(e+1,e+m+1); int L=1,R=0; for(int i=1;i<=m;i++) { while(L<e[i].l) update(L++,false); while(L>e[i].l) update(--L,true); while(R>e[i].r) update(R--,false); while(R<e[i].r) update(++R,true); ans[e[i].id]=query(e[i].k); } for(int i=1;i<=m;i++) printf("%d ",ans[i]); }