Honorable Mention 平衡树+树状数组

(Updated: )
(7 mins to read)

给定一个排列$p_i$​，表示第i个人的排名，要求支持两种操作：

  • 第x个人的排名上升到y，显然原来y$\sim$rank(x)-1的人的排名就要下降1
  • 问第x到第y个人中有多少人的排名在后40%

我们发现第一个操作需要以排名为下标进行维护，而第二个操作又需要以编号为下标进行维护。似乎不太可做。但是仔细想想，对于后40%，我们并不关心谁在前谁在后，我们只需要知道哪些人是在后40%那么用一个树状数组，以编号为下标维护哪些人是后40%然后用一个平衡树，以排名为下标来维护第一个操作。当x的排名原先在后40%，然后提升后不再后40%，就需要对树状数组的x-1，然后对原来排名40%的那个在树状数组中+1。然后只需要将x这个节点删掉，再插到排名为y节点的前面就可以了。还有一个问题，x的排名怎么求，我们以排名为下标怎么求排名呢。容易发现对于每个编号在平衡树中的节点是一一对应的，所以我们用数组保存x是平衡树中的哪个节点，然后把它splay到根，则左儿子的size+1就是排名了。最后不要忘记在splay中前后各插入一个哨兵！！

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 5;
int n, q, p[N], rp[N];
int c[N];
void upd(int x, int v)
{
  for(int i=x; i<=n; i+=(i&-i)) c[i] += v;
}
int ask(int x)
{
  int ans = 0;
  for(int i=x; i>0; i-=(i&-i)) ans += c[i];
  return ans;
}
int rt;
int ch[N][2], sz[N], val[N], fa[N], id[N];
bool rs(int x) { return ch[fa[x]][1]==x; }
void up(int p) { if(p) sz[p] = sz[ch[p][0]] + sz[ch[p][1]] + 1; }
void bld(int l, int r, int f)
{
  if(l>r) return;
  int p = (l+r)>>1;
  sz[p] = 1;
  ch[p][0] = ch[p][1] = 0;
  if(p>=2&&p<=n+1)
  {
    val[p] = rp[p-1];
    id[rp[p-1]] = p;
  }
  fa[p] = f, ch[f][p>f] = p;
  if(l==r) return;
  bld(l, p-1, p); bld(p+1, r, p);
  up(p);
}
void rotate(int x)
{
  int y = fa[x], z = fa[y], k = rs(x), w = ch[x][k^1];
  ch[y][k] = w; fa[w] = y;
  ch[z][rs(y)] = x; fa[x] = z;
  ch[x][k^1] = y; fa[y] = x;
  up(y); up(x);
}
void splay(int x, int g=0)
{
  while(fa[x]!=g)
  {
    int y = fa[x];
    if(fa[y]!=g) (rs(x)==rs(y) ? rotate(y) : rotate(x));
    rotate(x);
  }
  if(!g) rt = x;
}
int kth(int p, int k)
{
  if(ch[p][0]&&sz[ch[p][0]]>=k) return kth(ch[p][0], k);
  else if(sz[ch[p][0]]+1==k) return p;
  else return kth(ch[p][1], k-sz[ch[p][0]]-1);
}
int rnk(int p)
{
  splay(p);
  return sz[ch[p][0]] + 1;
}
void ins(int l, int r)
{
  int x = kth(rt, l-1), y = kth(rt, l+1);
  splay(x); splay(y, x);
  int z = ch[y][0];
  ch[y][0] = 0; fa[z] = 0;
  up(y); up(fa[y]);
  int x2 = kth(rt, r-1), y2 = kth(rt, r);
  splay(x2); splay(y2, x2);
  ch[y2][0] = z; fa[z] = y2;
  up(y2); up(fa[y2]);
}
void solve()
{
  scanf("%d", &n);
  for(int i=1; i<=n; i++)
  {
    scanf("%d", p+i);
    rp[p[i]] = i;
  }
  scanf("%d", &q);
  int lim = n*0.6;
  for(int i=1; i<=n; i++) c[i] = 0;
  for(int i=lim+1; i<=n; i++) upd(rp[i], 1);
  bld(1, n+2, 0);
  rt = (n+3)>>1;
  while(q--)
  {
    int op, x, y; scanf("%d%d%d", &op, &x, &y);
    if(op==1)
    {
      if(y<=lim)
      {
        int rkx = rnk(id[x]) - 1;
        if(rkx>lim)
        {
          upd(x, -1);
          upd(val[kth(rt, lim+1)], 1);
        }
        ins(rkx+1, y+1);
      }
    }
    else printf("%d\n", ask(y)-ask(x-1));
  }
}
int main()
{
  int _; scanf("%d", &_);
  while(_--) solve();
  return 0;
}