题目链接：https://www.luogu.org/problemnew/show/P1801
替罪羊树吼啊！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define il inline
using namespace std;
const int maxn = 2000001;
const int alpha = 0.7;
struct scapegoat{
int son[2], val, valid, below;
bool del;
}e[maxn];
int cur[maxn], memory[maxn], root, pool, posi, cnt, to_rebuild, a[maxn], u[maxn], n, m;
il bool isbad(int now)
{
if((double)e[now].valid*alpha <= (double)max(e[e[now].son[0]].valid, e[e[now].son[1]].valid)) return true;
return false;
}
void dfs(int now)
{
if(!now) return;
dfs(e[now].son[0]);
if(e[now].del) cur[++posi] = now;
else memory[++pool] = now;
dfs(e[now].son[1]);
}
void build(int l, int r, int &now)
{
int mid = l+r>>1;
now = cur[mid];
if(l == r)
{
e[now].son[0] = e[now].son[1] = 0;
e[now].valid = e[now].below = 1;
return;
}
if(l < mid) build(l,mid-1,e[now].son[0]);
else e[now].son[0] = 0;
build(mid+1, r, e[now].son[1]);
e[now].below = e[e[now].son[0]].below+e[e[now].son[1]].below+1;
e[now].valid = e[e[now].son[0]].valid+e[e[now].son[1]].valid+1;
}
il void rebuild(int &now)
{
posi = 0;
dfs(now);
if(posi) build(1,posi,now);
else now = 0;
}
il int find_rank(int tar)
{
int now = root;
int ans = 1;
while(now)
{
if(e[now].val >= tar) now = e[now].son[0];
else
{
ans+=e[e[now].son[0]].valid+e[now].del;
now = e[now].son[1];
}
}
return ans;
}
void insert(int &now, int val)
{
if(!now)
{
now = memory[pool--]; e[now].val = val;
e[now].below = e[now].valid = e[now].del = 1;
e[now].son[0] = e[now].son[1] = 0;
return;
}
e[now].below++, e[now].valid++;
if(e[now].val >= val) insert(e[now].son[0], val);
else insert(e[now].son[1], val);
if(!isbad(now))
{
if(to_rebuild)
{
if(e[now].son[0] == to_rebuild) rebuild(e[now].son[0]);
else rebuild(e[now].son[1]);
to_rebuild = 0;
}
}
else to_rebuild = now;
}
void delete_pos(int &now, int tar)
{
if(e[now].del && e[e[now].son[0]].valid + 1 == tar)
{
e[now].del = false; e[now].valid--; return;
}
e[now].valid--;
if(e[e[now].son[0]].valid+e[now].del >= tar) delete_pos(e[now].son[0],tar);
else delete_pos(e[now].son[1], tar-e[e[now].son[0]].valid-e[now].del);
}
il void delete_val(int tar)
{
delete_pos(root, find_rank(tar));
if((double)e[root].below*alpha > e[root].valid) rebuild(root);
}
il int kth(int tar)
{
int now = root;
while(now)
{
if(e[now].del&&e[e[now].son[0]].valid+1==tar) return e[now].val;
else if(e[e[now].son[0]].valid >= tar) now = e[now].son[0];
else
{
tar-=e[e[now].son[0]].valid+e[now].del;
now = e[now].son[1];
}
}
}
int main()
{
root = 0;
for(int i = 2000000; i >= 1; i--)
memory[++pool] = i;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++) scanf("%d",&a[i]);
for(int i = 1; i <= m; i++) scanf("%d",&u[i]);
int qaq = 1;
for(int i = 1; i <= m; i++)
{
while(qaq <= u[i])
{
insert(root, a[qaq]);
qaq++;
}
printf("%d\n",kth(i));
}
return 0;
}