1 /*************************************************************  2 题目：    Feed the dogs(poj 2761)  3 链接：    http://poj.org/problem?id=2761  4 题意：    给一个数列，在给一些区间，求这些区间第k小的值，这些  5           区间没有包含关系，也就是说如果La>Lb那么Ra>Rb;  6 算法：    treap树  7 思路：    由于这些区间没有包含关系，把这些区间排序后从左边  8           开始计算，每计算一个区间把前面多余数删除，这样每  9           个点只要插入和删除一次就可以了。 10 **************************************************************/ 11 #include
     
       12 #include
      
        13 #include
       
         14 #include
        
          15 using namespace std; 16  17 const int mx=1000005; 18 struct S 19 { 20     int l, r; 21     int di,k; 22 }; 23 S s[mx]; 24 int a[mx]; 25 int ans[mx]; 26 int n,m; 27 bool com(S a,S b) 28 { 29     if (a.l==b.l) return a.r
         
          sz; 52 } 53 Node *L_rotate(Node *T)    ///右节点的优先级大于当前节点的优先级，进行左旋转 54 { 55     Node *A=T->r;         ///A表示有节点 56     T->r=A->l; 57     A->l=T; 58     A->sz-T->sz;         ///交换后A变成当前节点，所以它的子树的节点数等于原来节点的节点数 59     T->sz=Tsize(T->l)+Tsize(T->r)+1; 60     return A; 61 } 62 Node *R_rotate(Node *T)   ///左节点的优先级大于当前节点的优先级，进行右旋转 63 { 64     Node *A=T->l; 65     T->l=A->r; 66     A->r=T; 67     A->sz=T->sz; 68     T->sz=Tsize(T->l)+Tsize(T->r)+1; 69     return A; 70 } 71  72 void inser(Node *&T,int val) ///插入函数,和二叉排序树差不多 73 { 74     if (T==NULL)             75     { 76         T=new Node(val); 77         return ; 78     } 79     if (T->val>=val) 80     { 81         inser(T->l,val); 82         if ((T->l->pri)<(T->pri)) T=R_rotate(T); ///优先级比较，并旋转 83     } 84     else 85     { 86         inser(T->r,val); 87         if ((T->r->pri)<(T->pri)) T=L_rotate(T); 88     } 89     T->sz=Tsize(T->l)+Tsize(T->r)+1;    90 } 91  92 void Delete(Node *&T,int val)        ///删除函数 93 { 94     if (T->val>val) Delete(T->l,val); 95     else if (T->val
          
           r,val); 96 else 97 { 98 if (T->l==NULL&&T->r==NULL) T=NULL; ///左右节点都为空 99 else if (T->r==NULL) T=T->l; ///右节点为空100 else if(T->l==NULL) T=T->r; ///左节点为空101 else ///左右都不空102 {103 if (T->l->pri
           
            r->pri) ///左节点优先级小于右边104 { ///右旋转，并向右子树删除105 T=R_rotate(T); ///应为有旋转后，要删除的节点到有子树去了106 Delete(T->r,val);107 }108 else109 {110 T=L_rotate(T);111 Delete(T->l,val);112 }113 }114 }115 if (T!=NULL)116 {117 T->sz=Tsize(T->l)+Tsize(T->r)+1;118 }119 }120 121 int Find(Node *T,int k) ///查找第k小的树122 {123 int temp=Tsize(T->l)+1; ///temp小于等于T->val数的个数124 if (temp==k) return T->val;125 if (temp>k) return Find(T->l,k);126 return Find(T->r,k-temp);127 }128 129 130 void solve()131 {132 sort(s+1,s+m+1,com);133 s[0].l=-1;134 s[0].r=-2;135 for (int i=1;i<=m;i++)136 {137 for (int j=s[i-1].l;j<=min(s[i-1].r,s[i].l-1);j++)138 Delete(root,a[j]); ///删除比要计算区间多的数139 for (int j=max(s[i-1].r+1,s[i].l);j<=s[i].r;j++) 140 inser(root,a[j]); ///插入该区间剩下的数141 ans[s[i].di]=Find(root,s[i].k);142 }143 for (int j=s[m].l;j<=s[m].r;j++) Delete(root,a[j]);144 }145 146 int main()147 {148 scanf("%d%d",&n,&m);149 for (int i=1;i<=n;i++) scanf("%d",&a[i]);150 for (int i=1;i<=m;i++)151 {152 int l,r;153 scanf("%d%d%d",&l,&r,&s[i].k);154 s[i].l=min(l,r);155 s[i].r=max(l,r);156 s[i].di=i;157 }158 root=NULL;159 solve();160 for (int i=1;i<=m;i++) printf("%d\n",ans[i]);161 }