大半年没用过主席树了，手敲回顾下，15min手敲1A主席树模板。。
我感觉我线段树这一块拿捏的死死的！！
很easy
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int M = 2e5+7; int a[M],li[M],cnt=0; int rt[M*20],ls[M*20],rs[M*20],tr[M*20]; void up(int pre,int &o,int l,int r,int x){ o=++cnt;//当前节点需要修改，要再开一个节点 ls[o]=ls[pre]; rs[o]=rs[pre]; tr[o]=tr[pre]+1; if(l==r)return ; int m=(l+r)/2; if(x<=m)up(ls[pre],ls[o],l,m,x); else up(rs[pre],rs[o],m+1,r,x); } int qu(int p,int o,int l,int r,int k){ if(l==r){ return l; } int m=(l+r)/2; int sm=tr[ls[o]]-tr[ls[p]]; if(sm>=k)return qu(ls[p],ls[o],l,m,k); return qu(rs[p],rs[o],m+1,r,k-sm); } int main() { int n,m,sz=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); li[++sz]=a[i]; } sort(li+1,li+1+sz); sz=unique(li+1,li+1+sz)-(li+1); for(int i=1;i<=n;i++){ a[i]=lower_bound(li+1,li+1+sz,a[i])-li; up(rt[i-1],rt[i],1,sz,a[i]); } while(m--){ int l,r,k; scanf("%d%d%d",&l,&r,&k); int id=qu(rt[l-1],rt[r],1,sz,k); printf("%d\n",li[id]); } return 0; }
