| 123456 |
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- struct Node{int l=0,r=0,sum=0;};
- int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int n,q;cin>>n>>q;vector<int>a(n),v;for(int&x:a)cin>>x;v=a;sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end());vector<Node>tr(1);tr.reserve((n+1)*20);auto upd=[&](auto&&self,int old,int l,int r,int p)->int{int cur=tr.size();tr.push_back(tr[old]);++tr[cur].sum;if(l<r){int m=(l+r)/2;if(p<=m)tr[cur].l=self(self,tr[old].l,l,m,p);else tr[cur].r=self(self,tr[old].r,m+1,r,p);}return cur;};vector<int>root(n+1);for(int i=1;i<=n;++i)root[i]=upd(upd,root[i-1],0,v.size()-1,lower_bound(v.begin(),v.end(),a[i-1])-v.begin());auto kth=[&](auto&&self,int L,int R,int l,int r,int k)->int{if(l==r)return l;int cnt=tr[tr[R].l].sum-tr[tr[L].l].sum,m=(l+r)/2;return k<=cnt?self(self,tr[L].l,tr[R].l,l,m,k):self(self,tr[L].r,tr[R].r,m+1,r,k-cnt);};while(q--){int l,r,k;cin>>l>>r>>k;cout<<v[kth(kth,root[l-1],root[r],0,v.size()-1,k)]<<'\n';}}
|
