P3850

发表于 分类于
[TJOI2007]书架

[TJOI2007]书架

这里的平衡树不是用来维护权值关系的，而是维护相对关系的。

因此我们的插入会和正常的权值插入方式有所区别，实际上也很简单。

对于 Splay，我们直接把排名 $pos-1$ 的值查找到并 splay 到根节点，然后把这个新点连接上即可。

对于 FHQ-Treap，我们可以按排名（依靠子树大小）分裂，然后合并起来即可。

两种的实现都有些特色，但都很体现这题平衡树的优势。

当然删除也是同理。

这里我写的是 Splay 的实现方式。

注意考虑极端情况并特判。

时间复杂度 $O(n\log n)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=1e6;

char s[N+5][15];
ll buffa[N+5],bufch[2][N+5],bufval[N+5],bufsiz[N+5];
ll *nowfa=buffa,*nowch[2]={bufch[0],bufch[1]},*nowval=bufval,*nowsiz=bufsiz;

struct Splay{
  ll *fa,*ch[2],*val,*siz;ll rt,sz;
  inline void Init(ll x) {
    x+=5;fa=nowfa;ch[0]=nowch[0];ch[1]=nowch[1];val=nowval;siz=nowsiz;
    nowfa+=x;nowch[0]+=x;nowch[1]+=x;nowval+=x;nowsiz+=x;
  }
  inline ll Get(ll x) {return x==ch[1][fa[x]];}
  inline void Pushup(ll x) {siz[x]=siz[ch[0][x]]+siz[ch[1][x]]+1;}
  inline void Rotate(ll x) {
    ll y=fa[x],z=fa[y],c=Get(x);ch[c][y]=ch[c^1][x];
    if(ch[c^1][x]) fa[ch[c^1][x]]=y;ch[c^1][x]=y;fa[y]=x;fa[x]=z;
    if(z) ch[y==ch[1][z]][z]=x;Pushup(y);Pushup(x);
  }
  inline void splay(ll x,ll g) {
    if(!x) return;
    for(ll f=fa[x];f=fa[x],f!=g;Rotate(x)) {
      if(fa[f]!=g) Rotate(Get(f)==Get(x)?f:x);
    }
    if(!g) rt=x;
  }
  inline ll Kth(ll k) {
    ll cur=rt;
    while(1) {
      if(ch[0][cur]&&k<=siz[ch[0][cur]]) cur=ch[0][cur];
      else {
        k-=siz[ch[0][cur]]+1;
        if(k<=0) return splay(cur,0),val[cur];cur=ch[1][cur];
      }
    }
  }
  inline void Ins(ll pos,ll k) {
    val[++sz]=k;if(!rt) {rt=sz;return;}Kth(pos-1);
    if(pos==1) {ch[1][sz]=rt;fa[rt]=sz;rt=sz;Pushup(sz);return;}
    ch[1][sz]=ch[1][rt];fa[ch[1][rt]]=sz;ch[1][rt]=sz;fa[sz]=rt;
    Pushup(sz);Pushup(rt);
  }
}t;

int main() {

  t.Init(N-5);
  ll n,m,q,cnt=0;n=read();
  for(ll i=1;i<=n;i++) {
    cnt++;scanf("%s",s[i]);t.Ins(i,cnt);
  }

  m=read();
  for(ll i=1;i<=m;i++) {
    cnt++;scanf("%s",s[cnt]);t.Ins(read()+1,cnt);
  }

  q=read();
  while(q--) {
    ll x=read();ll tmp=t.Kth(x+1);
    // printf("x=%lld kth=%lld\n",x,tmp);
    // cout<<s[tmp]<<endl;
    cout<<s[tmp]<<endl;
  }

  return 0;
}