题解：P16679 [CSPro 27] 吉祥物投票
__An
·
·
题解
题解：P16679 [CSPro 27] 吉祥物投票
目前唯一非 ODT 解法！！
鸣谢
特别感谢 jrscy 与 Planetary_system 以及前人的题解对本题解的大力支持！！！（陪我调了 7（更多？）个小时）。
题目大意
需要维护一个数据结构，使得该数据结构可以进行如下操作：
- 1\ l\ r\ x：将区间 [l,r] 推平为 x。
- 2\ x\ w：将所有 x 改为 w（若 w 为 0 则认为是退出）。
- 3\ x\ y：将所有 x 改为 y，y 改为 x。
- 4\ w：输出有几个 w。
- 5：输出哪个数最多。
其中 1 \le l \le r \le 10^9，操作数与 x,y,w 不超过 10^5。
正文
其实思路还是很明确且简单的，就是调起代码来很费人。
我们考虑维护一棵线段树，其节点的值有如下几种可能：
-
-
- 当 tr[p] 为其余值时：代表区间内所有值全为 tr[p]。
现在考虑操作：
- 操作 1：直接找到该区间，向下遍历线段树节点，若线段树节点不为
0；直接修改即可，否则向下继续遍历。
- 操作 4：直接维护 cnt 数组输出即可。
- 操作 5：维护一个全局的
set 或平衡树（本题解中使用 pb_ds 库中的红黑树）。
- 操作 2：考虑进行颜色映射，使用并查集优化映射路径即可。可开一个新点重新映射被改点。
- 操作 3：同操作 2。
用上动态开点线段树即可做完此题。
代码解释
::::warning{open}
这一部分非常重要，不看必然不能理解代码。
::::
Part 1：颜色映射 now,tnow,fa
$tnow[x]$ 代表线段树中颜色 $x$ 实际代表颜色应为 $tnow[x]$。
$fa[x]$ 代表输入颜色为 $x$ 时实际颜色为 $fa[x]$。
因此 **$tnow$ 与 $fa$ 应一起使用**。
::::warning[注意]
在线段树节点 $tr[p]$ 中，由于访问到一个被进行过操作 2 的节点，存储的有可能是未经变换的值，所以需要进行 $find(tr[p])$ 的操作。
::::
### Part 2：全局答案 $tt
### Part 3：《你真的仔细审题了吗？》
注意在操作 2 与操作 4 中会有 $w=0$ 的特殊情况，记得特判。同时对于操作 2 的特殊情况，由于笔者不想再调试了，因此直接写了暴力（~~然而可过~~）。
### Part 4：卡过小 Trick
对于 Part 2 中的全局 $tt$ 可以在插入时特判一下，如果当前 $cnt$ 小于等于 ```0``` 则可以不插入 $tt$。
于是耗时 7 小时，暴打 200 行（压行后 150）的代码震撼来袭！
::::success[AC Code]
```
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define mp(a, b) make_pair(a, b)
#define pr pair<int, int>
#define fir first
#define sec second
#define pb push_back
#define iosfst ios::sync_with_stdio(false);cin.tie(0), cout.tie(0)
using namespace std;
using namespace __gnu_pbds;
const int N = 2e5 + 10;
int n, m, q, sum, k, cnt[N];
int now[N], tnow[N], fa[N], rt, tot, tot_t, tr[N * 20], ls[N * 20], rs[N * 20];
struct node{
int a, b;
bool operator > (const node& y) const {
if (a != y.a) return a > y.a;
return b < y.b;
}
};
tree<node, null_type, greater<node>, rb_tree_tag, tree_order_statistics_node_update> tt;
inline int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y) {
fa[x] = y, cnt[y] += cnt[x];
return;
}
inline void pushup(int p) {
if (ls[p] && tr[ls[p]] == tr[rs[p]] && tr[ls[p]] != 0) tr[p] = tr[ls[p]];
else tr[p] = 0;
return;
}
inline void pushdown(int p) {
if(!ls[p]) ls[p] = ++tot_t;
if(!rs[p]) rs[p] = ++tot_t;
if (tr[p]) tr[ls[p]] = tr[rs[p]] = tr[p];
return;
}
inline void kill(int &p, int l, int r, int x) {
if(!p) p = ++tot_t;
if (tr[p]) {
if (tr[p] != -1 && find(tr[p]) == x) return;
int len = r - l + 1;
if (tr[p] != -1) {
int old_phys = tr[p], old_log = tnow[find(old_phys)];
tt.erase({cnt[find(old_phys)], old_log});
cnt[find(old_phys)] -= len;
if (cnt[find(old_phys)] > 0) tt.insert({cnt[find(old_phys)], old_log});
sum -= len;
}
int new_log = tnow[find(x)];
tt.erase({cnt[find(x)], new_log});
cnt[find(x)] += len;
tt.insert({cnt[find(x)], new_log});
sum += len, tr[p] = x;
return;
}
pushdown(p);
int mid = l + r >> 1;
kill(ls[p], l, mid, x);
kill(rs[p], mid + 1, r, x);
pushup(p);
return;
}
inline void update(int &p, int l, int r, int s, int t, int x) {
if(!p) p = ++tot_t;
if (s <= l && r <= t) {
kill(p, l, r, x);
return;
}
pushdown(p);
int mid = l + r >> 1;
if (s <= mid) update(ls[p], l, mid, s, t, x);
if (t > mid) update(rs[p], mid + 1, r, s, t, x);
pushup(p);
return;
}
inline int query() {
if (tt.empty()) return 0;
auto res = tt.find_by_order(0);
if (res -> a <= 0) return 0;
return res -> b;
}
inline void killall2(int &p, int l, int r, int x) {
if(!p) p = ++tot_t;
if (tr[p]) {
if (tr[p] == -1) return;
if (find(tr[p]) != x) return;
int len = r - l + 1;
int root_x = find(x), log_x = tnow[root_x];
tt.erase({cnt[root_x], log_x});
cnt[root_x] -= len;
if (cnt[root_x] > 0) tt.insert({cnt[root_x], log_x});
sum -= len;
tr[p] = -1;
return;
}
pushdown(p);
int mid = l + r >> 1;
killall2(ls[p], l, mid, x);
killall2(rs[p], mid + 1, r, x);
pushup(p);
return;
}
signed main() {
iosfst;
memset(tr, -1, sizeof tr);
cin >> n >> m >> q;
tot = m;
rep(i, 1, N - 5) fa[i] = i;
rep(i, 1, m) now[i] = tnow[i] = i;
sum = 0;
while (q--) {
int op; cin >> op;
if (op == 1) {
int l, r, x; cin >> l >> r >> x;
update(rt, 1, n, l, r, find(now[x]));
}
else if (op == 2) {
int x, w; cin >> x >> w;
int h = x;
int phys_x = now[x];
if (w != 0) {
int phys_w = now[w];
tot++;
tt.erase({cnt[find(phys_w)], tnow[find(phys_w)]}), tt.erase({cnt[find(phys_x)], h});
int temp = phys_x;
merge(phys_x, phys_w);
cnt[temp] = 0;
tt.insert({0, h}), tt.insert({cnt[find(phys_w)], tnow[find(phys_w)]});
now[h] = tot, tnow[tot] = h;
}
else killall2(rt, 1, n, find(phys_x));
}
else if (op == 3) {
int x, y; cin >> x >> y;
int h1 = x, h2 = y;
int px = now[x], py = now[y];
tt.erase({cnt[find(py)], h2}), tt.erase({cnt[find(px)], h1});
merge(py, tot + 1), merge(px, tot + 2);
now[h1] = tot + 1, now[h2] = tot + 2;
tnow[tot + 1] = h1, tnow[tot + 2] = h2;
tt.insert({cnt[tot + 1], h1}), tt.insert({cnt[tot + 2], h2});
tot += 2;
}
else if (op == 4) {
int w; cin >> w;
if (w != 0) cout << cnt[find(now[w])] << '\n';
else cout << n - sum << '\n';
}
else cout << query() << '\n';
}
return 0;
}
```
::::
### 讲个笑话:
太讷了。