模板题,以后要学splay,大概看一下treap就好了。
#include <cstdio>
#include <algorithm>
#include <cstring> using namespace std; const int maxn = 3e5+;
int num[maxn],st[maxn]; struct Treap{
int size;
int key,fix;
Treap *ch[]; Treap(int key)
{
size = ;
fix = rand();
this->key = key;
ch[] = ch[] = NULL;
}
int compare(int x) const
{
if(x == key) return -;
return x < key ? : ;
}
void Maintain()
{
size = ;
if(ch[] != NULL) size += ch[]->size;
if(ch[] != NULL) size += ch[]->size;
}
}; void Rotate(Treap* &t ,int d)
{
Treap *k = t->ch[d^];
t->ch[d^] = k->ch[d];
k->ch[d] = t;
t->Maintain();
k->Maintain();
t = k;
} void Insert(Treap* &t,int x)
{
if(t == NULL) t = new Treap(x);
else
{
int d = x < t->key ? : ;
Insert(t->ch[d],x);
if(t->ch[d]->fix > t->fix)
Rotate(t,d^);
}
t->Maintain();
} void Delete(Treap* &t,int x)
{
int d = t->compare(x);
if(d == -)
{
Treap *tmp = t;
if(t->ch[] == NULL)
{
t = t->ch[];
delete tmp;
tmp = NULL;
}
else if(t->ch[] == NULL)
{
t = t->ch[];
delete tmp;
tmp = NULL;
}
else
{
int k = t->ch[]->fix > t->ch[]->fix ? : ;
Rotate(t,k);
Delete(t->ch[k],x);
}
}
else Delete(t->ch[d],x);
if(t!=NULL) t->Maintain();
} bool Find(Treap *t,int x)
{
while(t != NULL)
{
int d = t->compare(x);
if(d == -) return true;
t = t->ch[d];
}
return false;
} int Kth(Treap *t,int k)
{
if(t == NULL || k <= || k > t->size)
return -;
if(t->ch[] == NULL && k == )
return t->key;
if(t->ch[] == NULL)
return Kth(t->ch[],k-);
if(t->ch[]->size >= k)
return Kth(t->ch[],k);
if(t->ch[]->size + == k)
return t->key;
return Kth(t->ch[],k--t->ch[]->size);
} int Rank(Treap *t,int x)
{
int r;
if(t->ch[] == NULL) r = ;
else r = t->ch[]->size;
if(x == t->key) return r+;
if(x < t->key)
return Rank(t->ch[],x);
return r++Rank(t->ch[],x);
} void DeleteTreap(Treap* &t)
{
if(t == NULL) return;
if(t->ch[] != NULL) DeleteTreap(t->ch[]);
if(t->ch[] != NULL) DeleteTreap(t->ch[]);
delete t;
t = NULL;
} int save[maxn];
int M,N; int main()
{
while(~scanf("%d%d",&M,&N))
{
for(int i=;i<=M;i++)
scanf("%d",&save[i]);
Treap *root = NULL;
int cnt = ;
for(int i=,x;i<=N;i++)
{
scanf("%d",&x);
for(int j = cnt;j <= x;j++)
Insert(root,save[j]);
cnt = x+;
printf("%d\n",Kth(root,i));
}
DeleteTreap(root);
}
}