Znzryb's Blog
0%

P6136 【模板】普通平衡树（数据加强版）

Posted on Edited on

思路讲解

FHQ-Treap

https://www.luogu.com.cn/article/vj041eul

AC代码

AC

https://www.luogu.com.cn/record/200519720

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef array<ll, 3> arr;
const ll MAXN = static_cast<ll>(4e6) + 10;
ll N, M, idx, root, last, ans;
mt19937 rng(time(0));
//                          值         随机值
ll son[MAXN][2], size[MAXN], key[MAXN], rad[MAXN];
inline void resize(ll k) { size[k] = size[son[k][0]] + size[son[k][1]] + 1; }
// split函数返回的是分裂出来的左子树和右子树的编号
//          根与按值分裂的值
pll split(ll u, ll k) {
    // 这里按值分裂,分裂为左子树<k，右子树>=k;
    if (!u)
        return {0, 0}; // 递归终止条件
    if (key[u] < k) {
        // 继续分裂右子树（左子树全部<k，也都符合条件）
        pll t = split(son[u][1], k);
        son[u][1] = t.first;
        resize(u); // 重新计算树大小
        // 进入到了这个节点，就是来找左子树中有没有>=k的值的
        return {u, t.second};
    } else {
        // 继续分裂左子树（右子树全部>=k，都符合条件）
        pll t = split(son[u][0], k);
        son[u][0] = t.second;
        resize(u);
        // 进入到了这个节点，就是来找右子树中有没有<k的值的，右子树中<k的值的就是在左子树
        return {t.first, u};
    }
}
// merge函数接受两个参数，为两棵树的根；返回合并后的根。
ll merge(ll u, ll v) {
    if (!u | !v)
        return u + v; // 如果任何一棵树为空，返回另一棵树
    if (rad[u] < rad[v]) {
        // 小根堆，我们让随机值小的u当根，merge左子树
        son[u][1] = merge(son[u][1], v);
        resize(u);
        return u;
    } else {
        // u值比较大，当v的右边
        son[v][0] = merge(u, son[v][0]);
        resize(v);
        return v;
    }
}
inline void insert(ll k) {
    key[++idx] = k;
    rad[idx] = rng();
    size[idx] = 1;
    pll t = split(root, k);
    root = merge(merge(t.first, idx), t.second);
}
inline void eraser(ll k) {
    pll x = split(root, k);
    // x.second 是所有>=k的，所以y就分成了=k的和>k的
    pll y = split(x.second, k + 1);
    // 把=k的根节点吃掉了
    y.first = merge(son[y.first][0], son[y.first][1]);
    // 依次合并起来，更新根
    root = merge(x.first, merge(y.first, y.second));
}
// 查询k的排名
inline ll find1(ll k) {
    pll t = split(root, k);
    ll rank = size[t.first] + 1;
    root = merge(t.first, t.second);
    return rank;
}
// 根据排名找数
inline ll find2(ll rank) {
    ll pos = root;
    while (pos) {
        if (rank == size[son[pos][0]] + 1)
            return key[pos];
        else if (size[son[pos][0]] + 1 > rank)
            pos = son[pos][0];
        else
            rank -= size[son[pos][0]] + 1, pos = son[pos][1];
    }
    return 0;
}
// 查询前驱
inline ll lst(ll k) { return find2(find1(k) - 1); }
// 直接find1(k+1)，查询的值+1，避免了值相同的问题
inline ll nxt(ll k) { return find2(find1(k + 1)); }
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; ++i) {
        ll a;
        cin >> a;
        insert(a);
    }
    // cout<<"debug "<<0<<" :\n";
    // cout<<root<<'\n';
    // for(int j=1;j<=N;++j) {
    //  cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
 // }
 for(int i=1;i<=M;i++){
  ll o,x;
  cin>>o>>x;
  // x^=last;
  if(o==1) insert(x^last);
  if(o==2) eraser(x^last);
  if(o==3) { last=find1(x^last); ans^=last; }
  if(o==4) { last=find2(x^last); ans^=last; }
  if(o==5) { last=lst(x^last); ans^=last; }
  if(o==6) { last=nxt(x^last); ans^=last; }
  // cout<<"debug "<<i<<" :\n";
  // for(int j=1;j<=N;++j) {
  //  cout<<"son "<<key[j]<<" "<<key[son[j][0]]<<' '<<key[son[j][1]]<<'\n';
  // }
 }
 cout<<ans<<endl;
 return 0;
}
/*
AC https://www.luogu.com.cn/record/200519720
6 7
1 1 4 5 1 4
2 1
1 9
4 1
5 8
3 13
6 7
1 4

*/

心路历程（WA，TLE，MLE……）

各种奇怪的地方吧，导致WA了。