题目链接:HDU2665
【题意】求区间第k大的数
【分析】主席树模版题,开始看不懂主席树,看了这篇后直接秒懂 点击进入;
【AC CODE】889ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) /*主席树-求区间第k大*/ const int INF = 0x3f3f3f3f, MAXN = 100000+10, M = MAXN*30;//M = 2*N*log(N) int l[M],r[M],sum[M], cnt; void bulid(int &u, int x, int y)//建空树0 { sum[cnt] = 0;u = cnt++; if(x == y) return; int m = (x+y)>>1; bulid(l[u],x,m); bulid(r[u],m+1,y); } void insert(int &u, int x, int y, int p) { l[cnt] = l[u],r[cnt] = r[u],sum[cnt] = sum[u];//复制老版本信息 sum[u=cnt++]++;//新版本计数+1 if(x == y) return; int m = (x+y)>>1; if(p <= m) insert(l[u],x,m,p); else insert(r[u],m+1,y,p); } int a[MAXN],sot[MAXN],n, root[MAXN];//a[]原序列,sot[]排序后离散化,root[i]表示[1,i]每个数出现的次数的线段树 void init() { cnt = 1; //bulid(root[0],1,n);//第0颗空树 sort(sot+1,sot+1+n); repe(i,1,n) { root[i] = root[i-1];//借用第i-1颗树 insert(root[i],1,n,lower_bound(sot+1,sot+1+n,a[i])-sot); } } int query(int a, int b, int x, int y, int k)//查询区间[a+1,b]的第k大数 { if(x == y) return x; int d = sum[l[b]]-sum[l[a]]; int m = (x+y)>>1; if(d >= k) return query(l[a],l[b],x,m,k); return query(r[a],r[b],m+1,y,k-d); } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int t; scanf("%d", &t); while(t--) { int q; scanf("%d %d", &n, &q); repe(i,1,n) scanf("%d",&a[i]), sot[i] = a[i]; init(); while(q--) { int x,y,k; scanf("%d%d%d",&x,&y,&k); printf("%d\n", sot[query(root[x-1],root[y],1,n,k)]); } } return 0; }