首先考虑转化一下操作 \(3\)。
令 \(m = \lfloor\frac{l + r}{2}\rfloor\)，操作 \(3\) 就相当于是在 \([l, m]\) 内的数变为 \(l - 1\)，在 \((m, r]\) 内的数变为 \(r + 1\)。
于是现在对于操作 \(3\) 其实就是将一个区间内的数都转为同一个值。
其实对于这类将大量信息整合为一体的题目，往往运用势能分析能得到更优美的结果。
先给出对应的做法，再对时间复杂度进行一定的分析。
考虑把相同的 \(a_i\) 放在一起处理，因为这些值肯定对于 \(3\) 操作也是共同变化的。
那么就可以用并查集保存信息，每个位置在并查集上对应找到的祖先就为其对应的权值，同时用 set 维护下所有的不同的值和对应的并查集的点的编号。
- 对于操作 \(1\)，直接新开一个节点表示 \(a_x = y\) 即可，同时在 set 中删去 \(a'_x\) 的信息（若存在），并加入 \(a_x\) 的信息。
- 对于操作 \(2\)，直接并查集查祖先即可。
- 对于操作 \(3\)，以将 \([l, m]\) 内的值变为 \(l - 1\) 举例。
考虑新建一个表示值 \(l - 1\) 的点，然后直接暴力在 set 中枚举在区间内的值，直接删去这些信息并把其在并查集中的父亲改为新建的 \(l - 1\) 的点。
最后在 set 加入 \(l - 1\) 的点的信息即可。
对于操作 1 和 2，显然单次的复杂度为 \(\mathcal{O}(\log n)\)。
这里着重考虑操作 \(3\) 暴力的时间复杂度。
考虑令势能函数 \(\varphi(i)\) 为第 \(i\) 次操作后不同的 \(a_i\) 的值的数量。
- 如果是 \(2\) 操作，因为不会使数发生改变，于是有 \(\varphi(i) = \varphi(i - 1)\)。
- 如果为 \(1\) 操作，那么其实就是删一个数加一个数，肯定势能变化不会超过 \(+ 1\)，于是有 \(\varphi(i) \le \varphi(i - 1) + 1\)。
- 如果为 \(3\) 操作，不妨先只考虑一半。
考虑到这个时候因为会多加入一个值，\(\varphi(i)\) 可能会多 \(1\)。
对于暴力删除，设删除了 \(c\) 个不同的值，那么就有 \(\varphi(i) \le \varphi(i - 1) - c + 1\)，此时对应的代价为 \(\mathcal{O}(c\log n)\)。
那么有 \(\varphi(q) \le \varphi(0) + \sum\limits_{i = 1}^q [op_i = 1] + 2\sum\limits_{i = 1}^q [op_i = 3] - \sum c\le n + 2q - \sum c\)。
又因为有 \(\varphi(q) > 0\)，所以可以知道 \(\sum c < n + 2q\)。
那么总代价 \(\mathcal{O}(\sum c\log n)\) 就是 \(\mathcal{O}((n + q)\log n)\) 级别的了。
于是时间复杂度就为 \(\mathcal{O}((n + q)\log n)\)。
#include<bits/stdc++.h>
constexpr int maxn = (4e5 + 10) * 3;
int fa[maxn], val[maxn];
inline int getfa(int x) {
return ! fa[x] ? x : (fa[x] = getfa(fa[x]));
}
std::set<std::pair<int, int> > s;
int a[maxn], id[maxn];
int main() {
int n, q, m = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
val[++m] = a[i], s.emplace(a[i], m), id[i] = m;
}
scanf("%d", &q);
for (int op; q--; ) {
scanf("%d", &op);
if (op == 1) {
int x, y;
scanf("%d%d", &x, &y);
if (s.find({a[x], id[x]}) != s.end()) {
s.erase({a[x], id[x]});
}
val[++m] = a[x] = y, s.emplace(y, m), id[x] = m;
} else if (op == 2) {
int x;
scanf("%d", &x);
printf("%d\n", val[getfa(id[x])]);
} else {
int l, r;
scanf("%d%d", &l, &r);
int mid = l + r >> 1;
val[++m] = l - 1;
for (auto it = s.lower_bound({l, 0}); it != s.end() && (*it).first <= mid; ) {
fa[(*it).second] = m;
it = s.erase(it);
}
s.emplace(l - 1, m);
val[++m] = r + 1;
for (auto it = s.lower_bound({mid + 1, 0}); it != s.end() && (*it).first <= r; ) {
fa[(*it).second] = m;
it = s.erase(it);
}
s.emplace(r + 1, m);
}
}
return 0;
}