题意：区间第k大
题解：主席树模板
// #pragma comment(linker, "/STACK:1024000000,1024000000") #include<iostream> #include<algorithm> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<vector> #include<set> #include<map> #include<stack> #include<queue> #include<time.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define ms(s) memset(s, 0, sizeof(s)) const int INF = 0x3f3f3f3f; const int maxn = 1e5+5; struct node { int l,r; int sum; }T[maxn*20]; int rt[maxn],a[maxn]; vector<int>v; int n,m,tot; int getid(int k){ return lower_bound(v.begin(),v.end(),k)-v.begin()+1; } void build(int &p,int l,int r){ p=++tot; T[p].sum=0; if(l==r)return ; int mid=(l+r)/2; build(T[p].l,l,mid); build(T[p].r,mid+1,r); } void update(int l,int r,int &now,int last,int k){ T[++tot]=T[last]; now=tot; T[tot].sum++; if(l==r)return; int mid=(l+r)/2; if(k<=mid){ update(l,mid,T[now].l,T[last].l,k); }else update(mid+1,r,T[now].r,T[last].r,k); } int query(int l,int r,int x,int y,int k){ if(l==r)return l; int mid=(l+r)/2; int cnt=T[T[y].l].sum-T[T[x].l].sum; if(cnt>=k)return query(l,mid,T[x].l,T[y].l,k); else return query(mid+1,r,T[x].r,T[y].r,k-cnt); } int main() { tot=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); v.push_back(a[i]); } sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end()); build(rt[0],1,n); for(int i=1;i<=n;i++){ update(1,n,rt[i],rt[i-1],getid(a[i])); } while(m--){ int x,y,k; scanf("%d%d%d",&x,&y,&k); int ans=v[query(1,n,rt[x-1],rt[y],k)-1]; printf("%d\n",ans); } }
