Description
cjBBteam拥有一个很大的野生动物园。这个动物园坐落在一个狭长的山谷内，这个区域从南到北被划分成N个区域，每个区域都饲养着一头狮子。这些狮子从北到南编号为1,2,3,…,N。每头狮子都有一个觅食能力值Ai，Ai越小觅食能力越强。饲养员cmdButtons决定对狮子进行M次投喂，每次投喂都选择一个区间[I,J]，从中选取觅食能力值第K强的狮子进行投喂。值得注意的是，cmdButtons不愿意对某些区域进行过多的投喂，他认为这样有悖公平。因此的投喂区间是互不包含的。你的任务就是算出每次投喂后，食物被哪头狮子吃掉了。
Input
输入第一行有两个数N和M。此后一行有N个数，从南到北描述狮子的觅食能力值。此后M行，每行描述一次投喂。第t+2的三个数I,J,K表示在第t次投喂中，cmdButtons选择了区间[I,J]内觅食能力值第K强的狮子进行投喂。
Output
输出有M行，每行一个整数。第i行的整数表示在第i次投喂中吃到食物的狮子的觅食能力值。
Sample Input
7 2
1 5 2 6 3 7 4
1 5 3
2 7 1Sample Output
3
2HINT
对于100%的数据，有1< =N< =100000，1< =M< =50000。
思路：
因为区间互不包含，所以这题我们可以离线，先将查询区间排序，然后判断区间是否交叉，同时动态维护treap中的数都在当前的区间里就可以了，treap支持删除，加入元素，和查询操作
貌似不想离线就要用主席树？？？ 蒟蒻表示马上学QAQ
#include<cstdio>
#include<cstring>
#include<ctime>
#include<algorithm>
using namespace std;
struct your
{
int l,r,v,rnd,w,s;
}a[200000];
int root,tot;
void push(int k)
{
a[k].s=a[k].w+a[a[k].l].s+a[a[k].r].s;
}
void lturn(int &k)
{
int t=a[k].r;
a[k].r=a[t].l;
a[t].l=k;
push(k);push(t);
k=t;
}
void rturn(int &k)
{
int t=a[k].l;
a[k].l=a[t].r;
a[t].r=k;
push(k);push(t);
k=t;
}
void update(int &k,int temp)
{
if(!k)
{
k=++tot;
a[k].w=a[k].s=1;
a[k].v=temp;
a[k].rnd=rand();
return ;
}
a[k].s++;
if(temp==a[k].v) a[k].w++;
else if(temp<a[k].v)
{
update(a[k].l,temp);
if(a[a[k].l].rnd<a[k].rnd) rturn(k);
}
else
{
update(a[k].r,temp);
if(a[a[k].r].rnd<a[k].rnd) lturn(k);
}
}
void del(int &k,int temp)
{
if(!k)return ;
if(temp==a[k].v)
{
if(a[k].w>1) a[k].w--,a[k].s--;
else if(a[k].l*a[k].r==0)
k=a[k].l+a[k].r;
else if(a[a[k].l].rnd<a[a[k].r].rnd)
rturn(k),del(k,temp);
else lturn(k),del(k,temp);
}
else if(temp<a[k].v) del(a[k].l,temp),a[k].s--;
else del(a[k].r,temp),a[k].s--;
}
int ask(int k,int temp)
{
if(a[a[k].l].s>=temp)
return ask(a[k].l,temp);
else if(temp>a[a[k].l].s+a[k].w)
return ask(a[k].r,temp-a[k].w-a[a[k].l].s);
else return k;
}
int n,m;
struct something
{
int x,y,c,id,tmp;
}b[120000];
int num[120000];
bool cmp(something j,something k)
{
return j.x<k.x;
}
bool cmp2(something j,something k)
{
return j.id<k.id;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&b[i].x,&b[i].y,&b[i].tmp),b[i].id=i;
sort(b+1,b+m+1,cmp);
for(int i=1;i<=m;i++)
{
if(b[i].x>b[i-1].y)
{
for(int j=b[i-1].x;j<=b[i-1].y;j++)
del(root,num[j]);
for(int j=b[i].x;j<=b[i].y;j++)
update(root,num[j]);
}
else
{
for(int j=b[i-1].x;j<=b[i].x-1;j++)
del(root,num[j]);
for(int j=b[i-1].y+1;j<=b[i].y;j++)
update(root,num[j]);
}
b[i].c=a[ask(root,b[i].tmp)].v;
}
sort(b+1,b+m+1,cmp2);
for(int i=1;i<=m;i++)
printf("%d\n",b[i].c);
}