?pid=2665
Problem Description
Give you a sequence and ask you the kth big number of a inteval.
Input
The first line is the number of the test cases.For each test case, the first line contain two integer n and m (n, m <= 100000), indicates the number of integers in the sequence and the number of the quaere.The second line contains n integers, describe the sequence.Each of following m lines contains three integers s, t, k.[s, t] indicates the interval and k indicates the kth big number in interval [s, t]
Output
For each test case, output m lines. Each line contains the kth big number.
Sample Input
1 10 1 1 4 2 3 5 6 7 8 9 0 1 3 2
Sample Output
2
/**hdu 2665 可持久化线段树求区间第K大值（函数式线段树||主席树）题目大意；给定一个区间，m个询问：指定区间的第k大的数解题思路：所谓主席树，，就是可持久化线段树，也就是说我们每插入了一个新的元素，就创造了一个新的结点，这样下去，线段树所有的历史版本我们就都能保存下来。然后考虑一下线段树相减，两棵线段树相减就是每一个结点相减，那么我们每一个结点更新一次，那么序列中每一个元素都对应了一个版本的线段树，也就是序列中所有的前缀的权值线段树，那么对于一个区间，通过前缀相减很快就能搞出来这个区间对应的线段树，然后询问这棵线段树的第K大值注：如果求区间第k小值转化为第（l-r-k+1）大值就可以了*/#include <stdio.h>#include <string.h>#include <algorithm>#include <iostream>using namespace std;const int N=100010;int T[N];int num[N];int san[N];int ls[N*20];int rs[N*20];int sum[N*20];int tot,rt;int n,m;void build(int l,int r,int &rt){rt=++tot;sum[rt]=0;if(l==r)return;int m=(l+r)/2;build(l,m,ls[rt]);build(m+1,r,rs[rt]);}void update(int last,int p,int l,int r,int &rt){rt=++tot;ls[rt]=ls[last];rs[rt]=rs[last];sum[rt]=sum[last]+1;if(l==r)return;int m=(l+r)>>1;if(p<=m)update(ls[last],p,l,m,ls[rt]);elseupdate(rs[last],p,m+1,r,rs[rt]);}int query(int ss,int tt,int l,int r,int k){if(l==r)return l;int m=(l+r)>>1;int cnt=sum[ls[tt]]-sum[ls[ss]];if(k<=cnt)return query(ls[ss],ls[tt],l,m,k);elsereturn query(rs[ss],rs[tt],m+1,r,k-cnt);}int main(){int tt;scanf("%d",&tt);while(tt–){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){scanf("%d",&num[i]);san[i]=num[i];}tot=0;sort(san+1,san+n+1);int cnt=unique(san+1,san+n+1)-san-1;build(1,cnt,T[0]);for(int i=1; i<=n; i++){num[i]=lower_bound(san+1,san+1+cnt,num[i])-san;}for(int i=1; i<=n; i++)update(T[i-1],num[i],1,cnt,T[i]);while(m–){int l,r,k;scanf("%d%d%d",&l,&r,&k);int id=query(T[l-1],T[r],1,cnt,k);printf("%d\n",san[id]);}}return 0;}
为你的难过而快乐的是敌人，
