题目描述

给你一个不同整数组成的数组a[1…n]，你必须回答一系列Q(i,j,k)的问题：在区间[i,j]中的第k大值。 例如：数组a={1,5,2,6,3,7,4}，询问 Q(2, 5, 3)，在区间[2,5]中有{5,2,6,3},第三小值是5，我们应该回答这个询问为5。

输入描述

第一行包含两个整数n和m (1 <= n <= 100 000, 1 <= m <= 5 000)，表示n个数，m次询问。 第二行包含n个不同的整数，绝对值不超过10^9。 以下m行，每行一个询问包含三个整数i,j,k (1 <= i <= j <= n, 1 <= k <= j - i + 1)，表示询问Q(i,j,k)。

输出描述

对于每个询问输出一行，一个整数表示询问的结果。

样例输入

7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3

样例输出

5 6 3

这题就是一道很裸的主席模板题，注意加上离散化就好了。

#include <cstdio> #include <iostream> #include <cstdlib> #include <algorithm> using namespace std ; const int maxn=100001; int a[maxn],into[maxn],b[maxn]; struct Node{ int ls,rs; int cnt; }tr[maxn*20]; int cur,rt[maxn]; int n,m,ln; void init(){ cur=0; cin >>n >>m; int i; for (i=1;i<=n;i++){ scanf ("%d",&a[i]); b[i]=a[i]; } } inline void push_up(int o){ tr[o].cnt=tr[tr[o].ls].cnt+tr[tr[o].rs].cnt; } int build(int l,int r){//构造模板树 int k=cur++; if (l==r) { tr[k].cnt=0; return k; } int mid=(l+r)>>1; tr[k].ls=build(l,mid); tr[k].rs=build(mid+1,r); push_up(k); return k; } int update(int o,int l,int r,int pos,int val){//更新 int k=cur++; tr[k]=tr[o]; if (l==pos&&r==pos){ tr[k].cnt+=val; return k; } int mid=(l+r)>>1; if (pos<=mid) tr[k].ls=update(tr[o].ls,l,mid,pos,val); else tr[k].rs=update(tr[o].rs,mid+1,r,pos,val); push_up(k); return k; } int query(int l,int r,int o,int v,int kth){//查找第k小 if (l==r) return l; int mid=(l+r)>>1; int res=tr[tr[v].ls].cnt-tr[tr[o].ls].cnt; if (kth<=res) return query(l,mid,tr[o].ls,tr[v].ls,kth); else return query(mid+1,r,tr[o].rs,tr[v].rs,kth-res); } int cmp (const void *a,const void *b){ return *(int *) a > *(int *)b ? 1 : -1; } int binary_search (int x){//二分查找 int s=1,t=ln,mid; while (s<t) { mid=(s+t)>>1; if (b[mid] >= x) t=mid; else s=mid+1; } return t; } void findit (){//离散化 ln=(unique (b+1,b+n+1))-(b+1); int i; for (i=1;i<=n;i++){ into[i]=binary_search (a[i]); } } int main (){ init (); qsort (b+1,n,sizeof(b[1]),cmp); findit (); int i,j,k,l; build (1,ln); for (i=1;i<=n;i++){ rt[i]=update (rt[i-1],1,ln,into[i],1); } for (i=1;i<=m;i++){ scanf ("%d %d %d",&j,&k,&l); PRintf ("%d\n",b[query (1,ln,rt[j-1],rt[k],l)]); } return 0; }