表面上看是主席树之类的区间k大
实际上，除了主席树，还可以测各种结构
因为题目中说，任意区间不会完全包含
于是，我们把区间按左端点排序，依次添加，用平衡树求当前的k大
每个狗最多被添加一次，删除一次
所以复杂度为O(nlogn)
被来写的是splay，结果一直WA到死
结果改成treap，第一次写就1Y了，不错
不过调treap需要把一组数据跑很多遍（至少我是这么认为的）
以免出现rp过好导致错误的程序跑对……
1 const rd=2000007; 2 type node=record 3 x,y,num,k:longint; 4 end; 5 var ans,pretty,fa,count,key,b:array[0..200100] of longint; 6 son:array[0..200100,1..2] of longint; 7 a:array[0..50010] of node; 8 p,j,root,n,q,i,t,s:longint; 9 10 procedure update(i:longint); 11 begin 12 count[i]:=count[son[i,1]]+count[son[i,2]]+1; 13 end; 14 15 function find(x:longint):longint; 16 var p:longint; 17 begin 18 p:=root; 19 repeat 20 if b[p]=x then exit(p); 21 if b[p]>x then p:=son[p,1] 22 else p:=son[p,2]; 23 until false; 24 end; 25 26 function kth(x:longint):longint; //找k大 27 var p:longint; 28 begin 29 p:=root; 30 while true do 31 begin 32 if count[son[p,1]]+1=x then exit(p); 33 if count[son[p,1]]+1>x then p:=son[p,1] 34 else begin 35 x:=x-count[son[p,1]]-1; 36 p:=son[p,2]; 37 end; 38 end; 39 end; 40 41 procedure clear(i:longint); 42 begin 43 count[i]:=1; 44 son[i,1]:=0; 45 son[i,2]:=0; 46 fa[0]:=0; 47 count[0]:=0; 48 end; 49 50 procedure rotate(x,w:longint); //基本的BST左右旋，和splay是一样的 51 var y:longint; 52 begin 53 y:=fa[x]; 54 if fa[y]=0 then root:=x; 55 if fa[y]<>0 then 56 begin 57 if son[fa[y],1]=y then son[fa[y],1]:=x 58 else son[fa[y],2]:=x; 59 end; 60 fa[x]:=fa[y]; 61 son[y,3-w]:=son[x,w]; 62 fa[son[x,w]]:=y; 63 son[x,w]:=y; 64 fa[y]:=x; 65 update(y); 66 update(x); 67 end; 68 69 procedure swap(var a,b:node); 70 var c:node; 71 begin 72 c:=a; 73 a:=b; 74 b:=c; 75 end; 76 77 procedure up(i:longint); //类似堆的上浮操作 78 var j:longint; 79 begin 80 j:=fa[i]; 81 while j<>0 do 82 begin 83 if key[i]<key[j] then 84 begin 85 if son[j,1]=i then rotate(i,2) 86 else rotate(i,1); 87 end 88 else break; 89 j:=fa[i]; 90 end; 91 if j=0 then root:=i; 92 end; 93 94 procedure sift(i:longint); //类似堆的下沉操作 95 var j1,j2:longint; 96 begin 97 repeat 98 j1:=son[i,1]; //选择较小的那个孩子旋转，使下沉后还能满足小根堆的性质 99 j2:=son[i,2]; 100 if (j1=0) and (j2=0) then break; 101 if (j1=0) then 102 rotate(j2,1) 103 else if (j2=0) then 104 rotate(j1,2) 105 else begin 106 if key[j1]>key[j2] then rotate(j2,1) else rotate(j1,2); 107 end; 108 until false; 109 end; 110 111 procedure sort(l,r: longint); 112 var i,j,x,y: longint; 113 begin 114 i:=l; 115 j:=r; 116 x:=a[(l+r) shr 1].x; 117 repeat 118 while (a[i].x<x) do inc(i); 119 while (x<a[j].x) do dec(j); 120 if not(i>j) then 121 begin 122 swap(a[i],a[j]); 123 inc(i); 124 j:=j-1; 125 end; 126 until i>j; 127 if l<j then sort(l,j); 128 if i<r then sort(i,r); 129 end; 130 131 procedure insert(x:longint); 132 var p:longint; 133 begin 134 inc(t); 135 inc(s); 136 clear(t); 137 key[t]:=trunc(random(rd)); //随机生成一个优先级，这个优先级满足小根堆的性质 138 b[t]:=x; 139 if root=0 then 140 begin 141 root:=t; 142 fa[t]:=0; 143 end 144 else begin 145 p:=root; //先插入到treap中 146 repeat 147 inc(count[p]); 148 if b[p]>x then 149 begin 150 if son[p,1]=0 then break; 151 p:=son[p,1]; 152 end 153 else begin 154 if son[p,2]=0 then break; 155 p:=son[p,2]; 156 end; 157 until false; 158 fa[t]:=p; 159 if b[p]>x then son[p,1]:=t else son[p,2]:=t; 160 up(t); //调整treap 161 end; 162 end; 163 164 procedure delete(x:longint); 165 var i,p:longint; 166 begin 167 i:=find(x); 168 key[i]:=2147483647; //只是为了清楚，treap删除是把当前节点旋转到叶节点 169 dec(s); 170 sift(i); 171 p:=i; 172 while p<>root do //注意删除时要更改它的父亲（祖先）的子树规模 173 begin 174 dec(count[fa[p]]); 175 p:=fa[p]; 176 end; 177 if son[fa[i],1]=i then son[fa[i],1]:=0 178 else son[fa[i],2]:=0; 179 count[i]:=0; 180 key[i]:=0; 181 b[i]:=0; 182 fa[i]:=0; 183 if s=0 then root:=0; 184 end; 185 186 begin 187 randomize; 188 readln(n,q); 189 for i:=1 to n do 190 read(pretty[i]); 191 readln; 192 for i:=1 to q do 193 begin 194 readln(a[i].x,a[i].y,a[i].k); 195 a[i].num:=i; 196 end; 197 count[0]:=0; 198 sort(1,q); 199 root:=0; 200 t:=0; 201 for i:=a[1].x to a[1].y do 202 insert(pretty[i]); 203 ans[a[1].num]:=b[kth(a[1].k)]; 204 for i:=2 to q do //按顺序一次添加删除 205 begin 206 if a[i].x>a[i-1].y then 207 begin 208 root:=0; 209 t:=0; 210 s:=0; 211 fillchar(fa,sizeof(fa),0); 212 fillchar(son,sizeof(son),0); 213 fillchar(count,sizeof(count),0); 214 fillchar(b,sizeof(b),0); 215 fillchar(key,sizeof(key),0); 216 for j:=a[i].x to a[i].y do 217 begin 218 insert(pretty[j]); 219 end; 220 end 221 else begin 222 for j:=a[i-1].y+1 to a[i].y do 223 insert(pretty[j]); 224 for j:=a[i-1].x to a[i].x-1 do 225 begin 226 delete(pretty[j]); 227 end; 228 end; 229 p:=kth(a[i].k); 230 ans[a[i].num]:=b[p]; 231 end; 232 for i:=1 to q do 233 writeln(ans[i]); 234 end.