这题就是一道很裸的主席模板题，注意加上离散化就好了。
#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;}新闻热点
疑难解答
