#include #include #include #include #define MAX 100010 #define _MAX 50010 using namespace std; struct ComplexAsk{ int l,r,k; int from; bool operator <(const ComplexAsk& a)const{ return lsize; if(son[1]!=NULL) size+=son[1]->size; } inline int Compare(int x){ if(x==val) return -1; return x>val; } }*root; int total,step; int source[MAX]; int ans[_MAX]; inline void Rotate(Complex*& a,int dir); void Insert(Complex*& a,int x); void Delete(Complex*& a,int x); int FindK(Complex*& a,int k); int main() { cin>>total>>step; for(int i=1;i<=total;i++) scanf("%d",&source[i]); for(int i=1;i<=step;i++) scanf("%d%d%d",&asks[i].l,&asks[i].r,&asks[i].k),asks[i].from=i; sort(asks+1,asks+step+1); for(int i=1;i<=step;i++){ if(asks[i-1].r>=asks[i].l){ for(int j=asks[i-1].l;json[dir^1]; a->son[dir^1]=k->son[dir]; k->son[dir]=a; a->Maintain(),k->Maintain(); a=k; } void Insert(Complex*& a,int x) { if(a==NULL){ a=new Complex(); a->val=x; return ; } int dir=a->Compare(x); if(dir==-1) a->cnt++; else{ Insert(a->son[dir],x); if(a->son[dir]->random > a->random) Rotate(a,dir^1); } a->Maintain(); } void Delete(Complex*& a,int x) { int dir=a->Compare(x); if(dir!=-1) Delete(a->son[dir],x); else{ if(a->cnt > 1) a->cnt--; else{ if(a->son[0]==NULL) a=a->son[1]; else if(a->son[1]==NULL) a=a->son[0]; else{ int _dir=(a->son[0]->random > a->son[1]->random); Rotate(a,_dir); Delete(a->son[_dir],x); } } } if(a!=NULL) a->Maintain(); } int FindK(Complex*& a,int k) { int t=0; if(a->son[0]!=NULL) t=a->son[0]->size; if(k<=t) return FindK(a->son[0],k); if(k>t+a->cnt) return FindK(a->son[1],k-t-a->cnt); return a->val; }