Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int arr[MAX],pk[MAX];
- struct node{
- node *left,*right;
- int sum;
- node(){
- sum = 0;
- left = right = NULL;
- }
- }*root[MAX];
- node* Build(int b,int e){
- if(b==e){
- node *ret = new node();
- ret->sum = 0;
- return ret;
- }
- int mid = (b+e)>>1;
- node *ret = new node();
- ret->left = Build(b,mid);
- ret->right = Build(mid+1,e);
- ret->sum = ret->left->sum + ret->right->sum;
- return ret;
- }
- node *update(node *ptr,int b,int e,int indx,int val){
- if(b>indx||indx>e)return ptr;
- if(b==e){
- node *ret = new node();
- ret->sum = val;
- return ret;
- }
- int mid = (b+e)>>1;
- node *ret = new node();
- ret->left = update(ptr->left,b,mid,indx,val);
- ret->right = update(ptr->right,mid+1,e,indx,val);
- ret->sum = ret->left->sum + ret->right->sum;
- return ret;
- }
- int query(node *l,node *r,int b,int e,int k){
- if(b==e)return b;
- int mid = (b+e)>>1;
- ///cout<<b<<" "<<e<<" "<< r->left->sum<<" "<<l->left->sum<<endl;
- int cnt = r->left->sum - l->left->sum;
- if(cnt>=k)return query(l->left,r->left,b,mid,k);
- else return query(l->right,r->right,mid+1,e,k-cnt);
- }
- int main()
- {
- ///booster()
- ///read("input.txt");
- int n,q;
- scani(n);
- scani(q);
- vi v;
- map<int,int>m;
- for(int i = 0;i<n;i++){
- scani(arr[i]);
- v.pb(arr[i]);
- }
- sort(all(v));
- for(int i = 0;i<v.size();i++){
- m[v[i]] = i+1;
- pk[i+1] = v[i];
- }
- root[0] = Build(1,n);
- for(int i = 0;i<n;i++){
- root[i+1] = update(root[i],1,n,m[arr[i]],1);
- }
- while(q--){
- int l,r,k;
- scani3(l,r,k);
- OUT(pk[query(root[l-1],root[r],1,n,k)]);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement