数据结构的常用维护方法

在处理一些数据结构问题时有一些经典模型和常用手段，还有一些比较少见的实用数据结构，本文会简单介绍。

主要是存放一些无处安放的和综合内容。

颜色段均摊

维护序列时，一个经典的操作是区间染色，我们可以考虑使用平衡树了来维护区间的颜色连续段。区间染色每次最多只会增加均摊 $O(1)$ 个颜色段。

珂朵莉树

模板。

维护一个序列，支持区间加，区间染色，区间 $k$ 小查询，区间每个数的 $x$ 次方的和模 $y$ 的值。使用数据生成器生成数据（数据随机）。

询问的内容非常诡异，不是传统树套树可以支持的操作。这里我们介绍珂朵莉树（ODT，严格意义上是一种思想），利用一个 set 存储所用的颜色段，然后进行暴力操作。

核心数据结构如下定义：

struct Node {
    int l, r; mutable i64 v; // 这个 v 接下来需要修改
    Node(int l = 0, int r = 0, i64 v = 0) : l(l), r(r), v(v) {}
    bool operator < (const Node &a) const { return l < a.l; }
};
set<Node> T;

最为关键的是 split 操作，其作用是将 $l$ 开始的颜色段单独分裂出来，并返回这一个颜色段的指针。

auto split(int p) {
    auto it = T.lower_bound(Node(p));
    if (it != T.end() && it->l == p) return it;
    --it; int l = it->l, r = it->r; i64 v = it->v;
    T.erase(it); T.insert(Node(l, p - 1, v));
    return T.insert(Node(p, r, v)).first;
}

当我们要取出一段区间时，一定要先 split(r + 1)，再 split(l)，否则可能 RE。取出颜色段后直接暴力操作即可。

在数据随机的情况下，期望复杂度是 $O(n\log \log n)$ 的。但是由于现在基本上都卡，所以出现区间染色操作时尽量往势能上想。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int n, m, seed, vmax;
int rnd(void) {
    int ret = seed; seed = (1ll * seed * 7 + 13) % 1000000007;
    return ret;
}

i64 poww(i64 a, int b, int p) {
    a %= p; i64 res = 1;
    for (; b; b >>= 1, a = 1ll * a * a % p)
        if (b & 1) res = 1ll * res * a % p;
    return res;
}

struct Node {
    int l, r; mutable i64 v;
    Node(int l = 0, int r = 0, i64 v = 0) : l(l), r(r), v(v) {}
    bool operator < (const Node &a) const { return l < a.l; }
};
set<Node> T;

auto split(int p) {
    auto it = T.lower_bound(Node(p));
    if (it != T.end() && it->l == p) return it;
    --it; int l = it->l, r = it->r; i64 v = it->v;
    T.erase(it); T.insert(Node(l, p - 1, v));
    return T.insert(Node(p, r, v)).first;
}

int main(void) {
    scanf("%d%d%d%d", &n, &m, &seed, &vmax);
    for (int i = 1; i <= n; ++i) T.insert(Node(i, i, rnd() % vmax + 1));
    int op, l, r, x, y;
    while (m--) {
        op = rnd() % 4 + 1, l = rnd() % n + 1, r = rnd() % n + 1;
        if (l > r) swap(l, r);
        if (op == 3) x = rnd() % (r - l + 1) + 1;
        else x = rnd() % vmax + 1;
        if (op == 4) y = rnd() % vmax + 1;
        if (op == 1) {
            auto R = split(r + 1), L = split(l);
            for (auto i = L; i != R; ++i) i->v += x;
        } else if (op == 2) {
            auto R = split(r + 1), L = split(l);
            T.erase(L, R); T.insert(Node(l, r, x));
        } else if (op == 3) {
            auto R = split(r + 1), L = split(l);
            vector<pair<i64, int>> v;
            for (auto i = L; i != R; ++i) v.push_back({i->v, i->r - i->l + 1});
            sort(v.begin(), v.end());
            for (int i = 0; i < v.size(); ++i) {
                if (v[i].second < x) x -= v[i].second;
                else { printf("%lld\n", v[i].first); break; }
            }
        } else {
            auto R = split(r + 1), L = split(l);
            i64 ans = 0;
            for (auto i = L; i != R; ++i) ans = (ans + poww(i->v, x, y) * (i->r - i->l + 1)) % y;
            printf("%lld\n", ans);
        }
    }
    return 0;
}

势能线段树

还记得花神游历各国（区间开方区间和）吗？它的修改非常暴力，但是复杂度是正确的。

由于区间染色每次最多只会增加均摊 $O(1)$ 个颜色段，因此可以考虑使用线段树暴力维护。

[CF444C] DZY Loves Colors.

有一个 $n$ $n$ 个元素组成的序列，每个元素有两个属性：颜色 $c_i$ $c_{i}$ 和权值 $w_i$ $w_{i}$ 。 $c_i$ $c_{i}$ 初始为 $i$ $i$ ， $w_i$ $w_{i}$ 初始为 $0$ $0$ 。 $m$ $m$ 次操作，操作有两种：
1. 1 l r x：对 $i\in [l,r]$ 的所有 $i$ 进行如下操作：设第 $i$ 个元素原来的颜色为 $y$ ，您要把第 $i$ 个元素的颜色改为 $x$ ，权值增加 $|y-x|$ 。
2. 2 l r：求 $\sum\limits_{i=l}^r w_i$ 。
$1\le n,m\le 10^5$ ， $1\le x\le 10^8$ 。

我们记一个 $c$ 代表区间颜色，不一样时记为 $-1$ 。如果一样则打标记修改，不一样则暴力递归修改。一次区间染色只会产生两个新的端点，暴力查询的次数为 $O(n+m)$ 级别。因此时间复杂度为 $O((n+m)\log n)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

int n, m, a[100005];
struct Node {
    int c; i64 w, t; // 区间是否为同一颜色 c（不同 c = -1），区间和 w，累加颜色改变值 t
    bool tag; // 区间 set 标记 tag
    #define ls o << 1
    #define rs ls | 1
} T[400005];

void pushup(int o) {
    if (T[ls].c == T[rs].c && T[ls].c != -1) T[o].c = T[ls].c;
    else T[o].c = -1;
    T[o].w = T[ls].w + T[rs].w;
}
void build(int o, int l, int r) {
    if (l == r) return T[o].c = l, T[o].w = 0, void();
    int mid = l + r >> 1;
    build(ls, l, mid); build(rs, mid + 1, r);
    pushup(o);
}
void pushdown(int o, int l, int r) {
    if (!T[o].tag) return;
    int mid = l + r >> 1;
    T[o << 1].w += (mid - l + 1) * T[o].t;
    T[o << 1 | 1].w += (r - mid) * T[o].t;
    T[o << 1].c = T[o << 1 | 1].c = T[o].c;
    T[o << 1].tag = T[o << 1 | 1].tag = 1; 
    T[o << 1].t += T[o].t; T[o << 1 | 1].t += T[o].t;
    T[o].tag = T[o].t = 0;
}
void update(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y && T[o].c != -1) {
        T[o].t += abs(k - T[o].c);
        T[o].w += 1ll * (r - l + 1) * abs(k - T[o].c);
        T[o].c = k; T[o].tag = 1;
        return;
    }
    int mid = l + r >> 1; pushdown(o, l, r);
    if (x <= mid) update(ls, l, mid, x, y, k);
    if (mid < y) update(rs, mid + 1, r, x, y, k);
    pushup(o);
}
i64 query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o].w;
    int mid = l + r >> 1; i64 res = 0; pushdown(o, l, r);
    if (x <= mid) res += query(ls, l, mid, x, y);
    if (mid < y) res += query(rs, mid + 1, r, x, y);
    return res;
}

int main(void) {
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m--) {
        int op, l, r, x; scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            scanf("%d", &x);
            update(1, 1, n, l, r, x);
        } else printf("%lld\n", query(1, 1, n, l, r));
    }
    return 0;
}

扫描线

扫描线具有非常广泛的应用。就是一根横着或者竖着的线沿着一个方向进行扫描，并利用数据结构（比如线段树）统计信息。

二维数点问题

模板。

给定二维平面上的 $n$ 个整点，多次询问一个矩形中点的个数。

我们记 $S(x,y)$ 代表 $(0,0),(x,y)$ 构成的矩形中点的个数，那么询问 $(a,b),(c,d)$ 的答案是： $S(c,d)-S(a-1,d)-S(c,b-1)+S(a-1,b-1)$ 。

我们将得到的询问按照 $x$ 排序，然后放一根扫描线从左到右进行扫描，将点加入树状数组，并进行统计。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, ans[500005], b[2000005], C[2000005], p = 0;
struct Node {
    int x, y, type, id;
    bool operator< (const Node &a) const {
        if (x == a.x) return type < a.type;
        return x < a.x;
    }
} a[3000005];
#define lowbit(x) (x & -x)
void add(int x, int k) {
    for (; x <= p; x += lowbit(x)) C[x] += k;
}
int query(int x) {
    int res = 0;
    for (; x; x -= lowbit(x)) res += C[x];
    return res;
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &a[i].x, &a[i].y); ++a[i].x; ++a[i].y;
        a[i].type = 1; b[++p] = a[i].y;
    }
    int tot = n;
    for (int i = 1; i <= m; ++i) {
        int x, y, _x, _y; scanf("%d%d%d%d", &x, &y, &_x, &_y);
        ++x; ++y; ++_x; ++_y; b[++p] = y - 1; b[++p] = _y;
        a[++tot] = {_x, _y, 3, i};
        a[++tot] = {x - 1, y - 1, 3, i};
        a[++tot] = {_x, y - 1, 2, i};
        a[++tot] = {x - 1, _y, 2, i};
    }
    sort(a + 1, a + tot + 1);
    sort(b + 1, b + p + 1); 
    p = unique(b + 1, b + p + 1) - (b + 1);
    for (int i = 1; i <= tot; ++i) {
        a[i].y = lower_bound(b + 1, b + p + 1, a[i].y) - b;
        if (a[i].type == 1) add(a[i].y, 1);
        else if (a[i].type == 2) ans[a[i].id] -= query(a[i].y);
        else ans[a[i].id] += query(a[i].y);
    }
    for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);
    return 0;
}

矩形面积并

模板。

求 $n$ 个矩形的面积并。

我们把这些矩形放在平面直角坐标系中，然后手握一根竖直的线线（当然你也可以握着一条横的上下扫，我们把它称之为扫描线，从左到右扫过整个坐标系，在这条扫描线上覆盖的图形长度只有在每个矩形的左右边界处会变化。

图片来自 <a target=_blank rel=noopener href=https://www.luogu.com.cn/blog/happy404/solution-p5490> https://www.luogu.com.cn/blog/happy404/solution-p5490</a>，可以看到在扫并起来的矩形时覆盖的长度变化

图片来自 https://www.luogu.com.cn/blog/happy404/solution-p5490，可以看到在扫并起来的矩形时覆盖的长度变化

也就是说，整个图形可以被分为 $n\times 2$ 段（每到一个矩形的两边长度就需要改变），每一段覆盖的长度 $L$ 是固定的（扫描这一段时的长度不变），这样就可以使用幼儿园数学求解这一段的矩形面积： $L\times 该段的宽度$ 。

实现上，我们取出 $n$ 个矩形的左右边界，如果一个矩形的两个对角顶点坐标分别为 $(x_1,y_1),(x_2,y_2),x_1<x_2,y_1<y_2$ ，那么左边界为 $(x_1,y_1,y_2,1)$ ，右边界为 $(x_2,y_1,y_2,-1)$ ，四个数分别代表 $x$ 坐标， $y$ 坐标上界， $y$ 坐标下界，对以后的面积是加 $1$ 还是减 $1$ （类似差分）。现在将这 $2n$ 个四元组按照 $x$ 从小到大的顺序排序。这就相当于给了我们 $2n$ 个区间加的操作，但是 $y$ 的范围很大，所以需要离散化后才能完成，而区间加就是典型的线段树操作了。

实现的时候有一点细节：

我们不需要 pushdown，因为我们只查总区间，只需要返回 T[1] 即可，其余节点就让它~~自生自灭~~就行了。
在修改的时候 $y_2$ 要减去 $1$ ，因为给的是点，我们想要覆盖，令 $y$ 覆盖的是 $[y,y+1]$ ，那么作为上面的 $y_2$ 就需要减去 $1$ 。
这里的标记很特殊，我们用一个 flag 来记录，当它是正数的时候说明被覆盖了，这时候就直接赋值为对应的区间所对应的值，如果没有被覆盖就是左右儿子的和。而且它在排序后进行扫描，只可能是一个自然数。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64;

struct line {
    int x, yl, yh, flag;
    line(int x = 0, int yl = 0, int yh = 0, int flag = 0) :
        x(x), yl(yl), yh(yh), flag(flag) {}
    bool operator < (const line &a) const { return x < a.x; }
} e[2000005];

int n, m;
int b[2000005], raw[2000005], tag[8000005];
i64 T[8000005];

void maintain(int o, int l, int r) {
    if (tag[o]) T[o] = raw[r + 1] - raw[l];
    else T[o] = T[o << 1] + T[o << 1 | 1];
}

void update(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return tag[o] += k, maintain(o, l, r);
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x, y, k);
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
    maintain(o, l, r);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1, x, y, _x, _y; i <= n; ++i) {
        scanf("%d%d%d%d", &x, &y, &_x, &_y);
        e[(i << 1) - 1] = line(x, y, _y, 1);
        e[i << 1] = line(_x, y, _y, -1);
        b[(i << 1) - 1] = y, b[i << 1] = _y;
    } n <<= 1;
    sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; ++i) {
        int pos1 = lower_bound(b + 1, b + m + 1, e[i].yl) - b;
        int pos2 = lower_bound(b + 1, b + m + 1, e[i].yh) - b;
        raw[pos1] = e[i].yl, raw[pos2] = e[i].yh;
        e[i].yl = pos1, e[i].yh = pos2;
    }
    sort(e + 1, e + n + 1);
    i64 ans = 0;
    for (int i = 1; i < n; ++i) {
        update(1, 1, m - 1, e[i].yl, e[i].yh - 1, e[i].flag);
        ans += T[1] * (e[i + 1].x - e[i].x);
    }
    printf("%lld\n", ans);
    return 0;
}

实际上扫描线还可以用在更复杂的几何问题上，比如圆的面积并和三角形面积并，请参考笔者有关计算几何的文章。

扫描线本质

比如很多问题中都存在二维数点的模型，比如询问两棵子树内是否有共同编号的节点，可以将一棵子树看作时间维（扫描线扫这个），然后使用数据结构来维护序列维（另一棵子树）。

当然这个问题也可以使用主席树在线解决，利用可持久化的性质来维护时间维，线段树维护序列维。

扫描线离线还是最通用的做法，因为它可以适配所有数据结构。

然而扫描线也可以扫序列维，用数据结构来维护时间维。

线段树的进阶用法

线段树是功能非常强大的数据结构，我们来看一些它的变种。

李超线段树

考虑这样一个问题：加入给定定义域的一次函数，查询 $x=k$ 时的最大值。

怎么做？考虑一种线段树，维护 $[l,r]$ 的节点只存储一个 $mid$ 处值最大的线段。修改操作如何实现呢？如果修改的线段不比当前线段优，那么下传修改线段；如果修改线段比当前线段优，那么下传当前线段。也就是说，要下传的一定是哪个更劣的线段。如何下传？只有当在某一部分的线段有交点时才需要下传。

单次修改时间复杂度为 $O(\log^2 n)$ ，查询时直接记录路过的所有线段的答案即可，时间复杂度依然为 $O(\log n)$ 。

模板，代码如下：

查看代码

#include <bits/stdc++.h>
#define pdi pair<double, int> 
using namespace std; 
const int P1 = 39989, P2 = 1000000000; 
const double eps = 1e-9; 

int n; 
struct Line {
    double k, b; 
} a[100005]; 
inline double calc(int x, int id) { return a[id].k * x + a[id].b; }
inline void add(int x0, int y0, int x1, int y1) {
    ++n; 
    if (x0 == x1) a[n].k = 0, a[n].b = max(y0, y1); 
    else a[n].k = 1.0 * (y1 - y0) / (x1 - x0), a[n].b = y0 - a[n].k * x0; 
}
int cmp(double x, double y) {
    if (x - y > eps) return 1; 
    if (y - x > eps) return -1; 
    return 0; 
}

int T[400005]; 
void upd(int o, int l, int r, int x) {
    if (T[o] == 0) return T[o] = x, void(); 
    int &y = T[o], mid = l + r >> 1; 
    int b = cmp(calc(mid, x), calc(mid, y)); 
    if (b == 1 || (b == 0 && x < y)) swap(x, y); // 现在满足 x 在中点处比 y 劣
    int bl = cmp(calc(l, x), calc(l, y)), br = cmp(calc(r, x), calc(r, y)); 
    if (bl == 1 || (bl == 0 && x < y)) upd(o << 1, l, mid, x); // 左半部分有交点
    if (br == 1 || (br == 0 && x < y)) upd(o << 1 | 1, mid + 1, r, x); 
}
void update(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return upd(o, l, r, k); 
    int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y, k); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k); 
}
pdi pmax(pdi x, pdi y) {
    if (cmp(x.first, y.first) == 1) return x; 
    if (cmp(x.first, y.first) == -1) return y; 
    return x.second < y.second ? x : y; 
}
pdi query(int o, int l, int r, int x) {
    if (r < x || l > x) return {0, 0}; 
    int mid = l + r >> 1; double res = calc(x, T[o]); 
    if (l == r) return {res, T[o]}; 
    return pmax({res, T[o]}, pmax(query(o << 1, l, mid, x), query(o << 1 | 1, mid + 1, r, x))); 
}

int main(void) {
    int m; scanf("%d", &m); 
    for (int lst = 0; m--; ) {
        int op; scanf("%d", &op); 
        if (op == 1) {
            int x0, y0, x1, y1; scanf("%d%d%d%d", &x0, &y0, &x1, &y1); 
            x0 = (x0 + lst - 1 + P1) % P1 + 1; 
            x1 = (x1 + lst - 1 + P1) % P1 + 1; 
            y0 = (y0 + lst - 1 + P2) % P2 + 1; 
            y1 = (y1 + lst - 1 + P2) % P2 + 1; 
            if (x0 > x1) swap(x0, x1), swap(y0, y1); 
            add(x0, y0, x1, y1); 
            update(1, 1, P1, x0, x1, n); 
        } else {
            int x; scanf("%d", &x); 
            x = (x + lst - 1 + P1) % P1 + 1; 
            printf("%d\n", lst = query(1, 1, P1, x).second); 
        }
    }
    return 0; 
}

单侧递归问题

[CTT2012 Day 1] 楼房重建.

小 A 在平面上 $(0,0)$ 点的位置，第 $i$ 栋楼房可以用一条连接 $(i,0)$ 和 $(i,H_i)$ 的线段表示，其中 $H_i$ 为第 $i$ 栋楼房的高度。如果这栋楼房上任何一个高度大于 $0$ 的点与 $(0,0)$ 的连线没有与之前的线段相交，那么这栋楼房就被认为是可见的。

初始时所有楼房的高度都为 $0$ ，支持单点修改，修改后询问能看到多少栋楼房。

本质上是单点修改，询问全局有多少位置是前缀最大值。可以使用很屑的根号来维护，但是这里考虑 poly log。

使用线段树维护。一个节点记录两个数：区间所对应的答案，当前区间的最大斜率。修改时很容易实现，关键是，pushup？问题在于如何统计当前节点的答案，也就是说，如何统计右半段在被左半段影响之后应该如何计算答案。怎么办？不会！俗话说的好，那么直接递归下去！

如果右区间的最大值小于等于左区间，那么就被全部挡住了。否则递归考虑右半段，这样所有的贡献都可以计算。

pushup(T[o << 1].k, o << 1 | 1, mid + 1, r); // 调用

int pushup(double k, int o, int l, int r) {
    if (T[o].k <= k) return 0; // 当这一部分的斜率小于左半部分的斜率，答案为 0
    if (a[l] > k) return T[o].ans; // l 的斜率大于左半边，左半对右半没有影响，返回右半边答案
    if (l == r) return a[l] > k; // 只有一个点，直接返回
    int mid = l + r >> 1;
    if (T[o << 1].k <= k) return pushup(k, o << 1 | 1, mid + 1, r); // 左半边斜率小于等于限制，只有右半边会计入答案
    return pushup(k, o << 1, l, mid) + T[o].ans - T[o << 1].ans; // 统计左半边答案，同时直接加上右半边的答案（当前答案减去左子节点答案）
}

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m;
struct Node {
    int ans;
    double k;
} T[400005];
double a[100005];

int pushup(double k, int o, int l, int r) {
    if (T[o].k <= k) return 0;
    if (a[l] > k) return T[o].ans;
    if (l == r) return a[l] > k;
    int mid = l + r >> 1;
    if (T[o << 1].k <= k) return pushup(k, o << 1 | 1, mid + 1, r);
    return pushup(k, o << 1, l, mid) + T[o].ans - T[o << 1].ans;
}

void update(int o, int l, int r, int x, int k) {
    if (l == r) return T[o] = {1, a[x]}, void();
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x, k);
    else update(o << 1 | 1, mid + 1, r, x, k);
    T[o].k = max(T[o << 1].k, T[o << 1 | 1].k);
    T[o].ans = T[o << 1].ans + pushup(T[o << 1].k, o << 1 | 1, mid + 1, r);
}

int main(void) {
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, y;
        scanf("%d%d", &x, &y); a[x] = double(y) / x;
        update(1, 1, n, x, y);
        printf("%d\n", T[1].ans);
    }
    return 0;
}

吉司机线段树

指的是一类维护区间最值操作与历史最值的线段树。

区间最值操作

待填坑。

区间历史最值

其余内容待填坑。

CPU 监控。

考虑没有染色操作怎么做。简单，维护最大的历史加标记。

发现一次染色后所有的加都可以转化为染色，因此直接做就行。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x7fffffff;

int n, m, a[100005];
struct Node {
    int mx, hmx, setv, addv, hset, hadd, tag; 
    void cover(int v, int hv) {
        setv = mx = v; addv =-0; 
        if (tag) hset = max(hset, hv);
        else hset = hv, tag = 1;
        hmx = max(hmx, hv); 
    }
    void add(int v, int hv) {
        hadd = max(hadd, addv + hv);
        hmx = max(hmx, mx + hv);
        addv += v; mx += v;
    }
    void change(int v, int hv) {
        if (tag) cover(setv + v, setv + hv);
        else add(v, hv);
    }
} T[400005];
inline void pushup(int o) {
    T[o].mx = max(T[o << 1].mx, T[o << 1 | 1].mx); 
    T[o].hmx = max(T[o << 1].hmx, T[o << 1 | 1].hmx); 
}
void build(int o, int l, int r) {
    if (l == r) return T[o].mx = T[o].hmx = a[l], void();
    int mid = l + r >> 1; build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
    pushup(o);
}
inline void pushdown(int o) {
    T[o << 1].change(T[o].addv, T[o].hadd);
    T[o << 1 | 1].change(T[o].addv, T[o].hadd);
    T[o].addv = T[o].hadd = 0;
    if (T[o].tag) {
        T[o << 1].cover(T[o].setv, T[o].hset);
        T[o << 1 | 1].cover(T[o].setv, T[o].hset);
        T[o].tag = 0;
    }
}
void update(int o, int l, int r, int x, int y, int k, bool type) {
    if (x <= l && r <= y) return type ? T[o].cover(k, k) : T[o].change(k, k), void(); 
    int mid = l + r >> 1; pushdown(o); 
    if (x <= mid) update(o << 1, l, mid, x, y, k, type); 
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k, type); 
    pushup(o); 
}
int query(int o, int l, int r, int x, int y, bool type) {
    if (x <= l && r <= y) return type ? T[o].hmx : T[o].mx;
    int mid = l + r >> 1, res = -INF; pushdown(o);
    if (x <= mid) res = max(res, query(o << 1, l, mid, x, y, type));
    if (mid < y) res = max(res, query(o << 1 | 1, mid + 1, r, x, y, type));
    return res;
}

int main(void) {
    scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    build(1, 1, n); char s[5]; int x, y, z;
    for (scanf("%d", &m); m--; ) {
        scanf("%s%d%d", s, &x, &y);
        if (s[0] == 'Q') printf("%d\n", query(1, 1, n, x, y, 0));
        else if (s[0] == 'A') printf("%d\n", query(1, 1, n, x, y, 1));
        else scanf("%d", &z), update(1, 1, n, x, y, z, s[0] == 'P' ? 0 : 1);
    }
    return 0;
}

重构

有些对数据结构的操作较难维护，我们可以定期对整个数据结构进行 $O(n)$ 重构，在两次重构之间的修改，则暴力处理。

操作分块

即根号重构。

二进制分组

分块系列

分块是最难的数据结构^[1]。我们之前见过对于序列的各种分块，有的题相当麻烦。但是实际上分块还有许多变种应用，本节将初探这些内容。

逐块处理

如果每个块对答案的贡献独立，那么可以将询问离线，然后逐个块进行处理。这样可以做到线性空间，并且常数可以得到相当的优化。

[SNOI2022] 军队。

没有 $l,r$ 的话是个经典问题，那么直接将序列分块逐块处理，不是完整的修改则暴力重构。

查看代码

#include <bits/stdc++.h>
using namespace std;
typedef long long i64; 
const int BLOCK_SIZE = 5000; 

int n, q, C, LL, RR; 
int c[250005], cc[250005];
int L[505], R[505], vis[250005], cnt[250005]; 
i64 a[250005], ans[250005], aa[250005]; 
struct Query {
    int op, l, r, x, y;
} Q[250005]; 

int main(void) {
    scanf("%d%d%d", &n, &q, &C); int t = (n - 1) / BLOCK_SIZE + 1; 
    for (int i = 1; i <= t; ++i) L[i] = R[i - 1] + 1, R[i] = i * BLOCK_SIZE; R[t] = n; 
    for (int i = 1; i <= n; ++i) scanf("%lld", a + i); 
    for (int i = 1; i <= n; ++i) scanf("%d", c + i), cc[i] = i; 
    for (int i = 1; i <= q; ++i) {
        scanf("%d%d%d", &Q[i].op, &Q[i].l, &Q[i].r); 
        if (Q[i].op != 3) scanf("%d%d", &Q[i].x, &Q[i].y); 
    }
    for (int k = 1; k <= t; ++k) {
        LL = L[k], RR = R[k]; i64 res = 0;
        memset(cnt, 0, sizeof cnt); 
        for (int i = LL; i <= RR; ++i) ++cnt[c[i]], res += a[i]; 
        for (int i = 1; i <= q; ++i) {
            int op = Q[i].op, l = Q[i].l, r = Q[i].r, x = Q[i].x, y = Q[i].y;
            if (r < LL || l > RR) continue; 
            if (l <= LL && RR <= r) {
                if (op == 1) cnt[y] += cnt[x], cnt[x] = 0; 
                else if (op == 2) res += 1ll * cnt[x] * y; 
                else ans[i] += res; 
            } else {
                int bl = max(l, LL), br = min(r, RR); 
                vector<int> bin; 
                for (int j = i - 1; j >= 1 && vis[j] != k; --j) {
                    vis[j] = k; 
                    if (Q[j].r < LL || Q[j].l > RR) continue; 
                    if (Q[j].op == 1) aa[Q[j].x] = aa[Q[j].y], cc[Q[j].x] = cc[Q[j].y]; 
                    else if (Q[j].op == 2) aa[Q[j].x] += Q[j].y;
                    bin.push_back(Q[j].x); 
                } vis[i] = k; 
                for (int j = LL; j <= RR; ++j) a[j] += aa[c[j]], c[j] = cc[c[j]]; 
                for (int x : bin) aa[x] = 0, cc[x] = x; 
                if (op == 1) {
                    for (int j = bl; j <= br; ++j)
                        if (c[j] == x) c[j] = y, --cnt[x], ++cnt[y]; 
                } else if (op == 2) {
                    for (int j = bl; j <= br; ++j)
                        if (c[j] == x) a[j] += y, res += y; 
                } else {
                    for (int j = bl; j <= br; ++j)
                        ans[i] += a[j]; 
                }
            }
        }
    }
    for (int i = 1; i <= q; ++i) if (Q[i].op == 3) printf("%lld\n", ans[i]); 
    return 0; 
}

Problemset

扫描线

一些简单题。

[Luogu P1502] 窗口的星星

Portal.

我们将每个星星看成一个左下角为 $(x,y)$ ，右上角为 $(x+w-1,y+h-1)$ 的矩形，窗户看成一个点，那么使用扫描线维护平面中的最大值即可。

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;
typedef long long i64;

struct Line {
    int x, yl, yh, c;
    Line(int x = 0, int yl = 0, int yh = 0, int c = 0) :
        x(x), yl(yl), yh(yh), c(c) {}
    bool operator < (const Line &a) const {
        // 先扫加的来保证结果正确
        if (x != a.x) return x < a.x;
        else return c > a.c;
    }
}e[20005];

int n, W, H, m;
int b[20005];
i64 T[80005], tag[80005];

inline void pushdown(int o) {
    if (!tag[o]) return;
    tag[o << 1] += tag[o];
    tag[o << 1 | 1] += tag[o];
    T[o << 1] += tag[o];
    T[o << 1 | 1] += tag[o];
    tag[o] = 0;
}

void update(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) {
        T[o] += k;
        tag[o] += k;
        return;
    }
    pushdown(o);
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x, y, k);
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
    T[o] = max(T[o << 1], T[o << 1 | 1]);
}

void solve(void) {
    scanf("%d%d%d", &n, &W, &H);
    for (int i = 1, x, y, l; i <= n; ++i) {
        scanf("%d%d%d", &x, &y, &l);
        e[(i << 1) - 1] = Line(x, y, y + H - 1, l);
        e[i << 1] = Line(x + W - 1, y, y + H - 1, -l);
        b[(i << 1) - 1] = y, b[i << 1] = y + H - 1;
    }
    sort(b + 1, b + (n << 1) + 1);
    m = unique(b + 1, b + (n << 1) + 1) - (b + 1);
    for (int i = 1; i <= (n << 1); ++i) {
        int pos1 = lower_bound(b + 1, b + m + 1, e[i].yl) - b;
        int pos2 = lower_bound(b + 1, b + m + 1, e[i].yh) - b;
        e[i].yl = pos1, e[i].yh = pos2;
    }
    sort(e + 1, e + (n << 1) + 1);
    i64 ans = 0;
    memset(T, 0, sizeof(T));
    memset(tag, 0, sizeof(tag));
    for (int i = 1; i <= (n << 1); ++i) {
        update(1, 1, n << 1, e[i].yl, e[i].yh, e[i].c);
        ans = max(ans, T[1]);
    }
    printf("%lld\n", ans);
}

int main(void) {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}

颜色段均摊

不一定是区间染色，有些操作也具有类似于颜色段均摊的性质。

「C.E.L.U-02」苦涩

Portal.

建立一棵线段树，每个节点保存一个优先队列作为区间加的标记，并永久化（即当前节点的优先队列中的内容对它的儿子都有效）。删除时可以暴力遍历线段树，因为每一次添加只会添加一个拥有最大数值最大的颜色段，这样删除它的时间就会在 $O(\log n)$ 级别。若 $n,m$ 同阶，那么总时间复杂度为 $O(n\log^2 n)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m; 

struct Node {
    int maxx; 
    priority_queue<int> q; 
} T[800005];
void pushup(int o) {
    T[o].maxx = max({T[o << 1].maxx, T[o << 1 | 1].maxx, T[o].q.top()});
}
void build(int o, int l, int r) {
    T[o].maxx = -1; T[o].q.push(-1);
    if (l == r) return; int mid = l + r >> 1; 
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
}
void maketag(int o, int k) {
    T[o].q.push(k); T[o].maxx = max(T[o].maxx, k);
}
void update(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return maketag(o, k);
    int mid = l + r >> 1; 
    if (x <= mid) update(o << 1, l, mid, x, y, k);
    if (mid < y) update(o << 1 | 1, mid + 1, r, x, y, k);
    pushup(o);
}
void remove(int o, int l, int r, int x, int y, int k) {
    if (T[o].maxx < k) return;
    if (x <= l && r <= y) {
        if (T[o].q.top() == k) {
            T[o].q.pop();
            if (l == r) T[o].maxx = T[o].q.top();
            else pushup(o);
            return; 
        }
        int mid = l + r >> 1; 
        remove(o << 1, l, mid, x, y, k); remove(o << 1 | 1, mid + 1, r, x, y, k);
        return pushup(o);
    }
    if (T[o].q.top() == k) T[o].q.pop(), maketag(o << 1, k), maketag(o << 1 | 1, k);
    int mid = l + r >> 1; 
    if (x <= mid) remove(o << 1, l, mid, x, y, k);
    if (mid < y) remove(o << 1 | 1, mid + 1, r, x, y, k);
    pushup(o);
}
int query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o].maxx; 
    int mid = l + r >> 1, ans = T[o].q.top();
    if (x <= mid) ans = max(ans, query(o << 1, l, mid, x, y));
    if (mid < y) ans = max(ans, query(o << 1 | 1, mid + 1, r, x, y));
    return ans; 
}

int main(void) {
    scanf("%d%d", &n, &m); build(1, 1, n);
    while (m--) {
        int op, l, r, k; scanf("%d%d%d", &op, &l, &r);
        if (op == 1) {
            scanf("%d", &k); 
            update(1, 1, n, l, r, k);
        } else if (op == 2) {
            k = query(1, 1, n, l, r);
            if (k != -1) remove(1, 1, n, l, r, k);
        } else printf("%d\n", query(1, 1, n, l, r));
    }
    return 0;
}

线段树进阶用法

各种线段树！

[CF1340F] Nastya and CBS

维护一个括号序列，可以支持简单的修改，询问区间括号匹配信息，这是可以使用单侧递归结构解决的经典问题。

Portal.

$k$ 种括号，支持单点修改括号种类，询问区间是否为合法的括号序列。

一段括号序列怎么维护？由于线段树上的结构是不断合并的，因此在不断删去相邻的括号匹配后，如果仍然包含相向的括号（(]），那么就失配了。这样当前节点的匹配信息必定是若干右括号加若干左括号。

也就是说，线段树的当前节点存储左侧的右括号和右侧的左括号，储存时储存它们的长度和哈希值，合并的时候需要查询某个节点左右侧部分前后缀哈希值，然后进行匹配，这个过程可以直接单侧递归下去。

对于询问，将线段树上的区间抽离出来放在一个栈中，利用匹配的过程中不应有右括号这一特点不断进行匹配，看最后是否剩的元素长度为 $0$ 。

时间复杂度为 $O(n+m\log^2 n)$ ，空间复杂度为 $O(n)$ 。

查看代码

#include <bits/stdc++.h>
#define ls o << 1
#define rs ls | 1
using namespace std;

int n, m, k; 
int a[100005]; 
namespace Hash {
    const int B1 = 10009, B2 = 254350526, P = 943236167; 
    int _w[200010], *w = _w + 100005; 
    void init(int n) {
        w[0] = 1; 
        for (int i = 1; i <= n; ++i) {
            w[i] = 1ll * w[i - 1] * B1 % P; 
            w[-i] = 1ll * w[-i + 1] * B2 % P; 
        }
    }
    struct str {
        int l, x; 
        str() { l = x = 0; }
        str(int v) : l(1), x(v) {}
        str(int l, int x) : l(l), x(x) {}
        friend bool operator== (str a, str b) { return a.l == b.l && a.x == b.x; }
        friend str operator+ (str a, str b) {
            return str(a.l + b.l, (a.x + 1ll * b.x * w[a.l]) % P); 
        }
        friend str operator- (str a, str b) { 
            return str(a.l - b.l, (0ll + a.x - b.x + P) * w[-b.l] % P); 
        }
    }; 
}
using Hash::str; 

struct Node {
    bool err; 
    str vl, vr; 
    Node(int x = 0) : err(0) { if (x > 0) vr = x; else vl = -x; }
} T[400005]; 

str gValL(int o, int k) {
    if (!k) return str(); 
    if (k == T[o].vl.l) return T[o].vl; 
    if (k <= T[ls].vl.l) return gValL(ls, k); 
    return T[ls].vl + (gValL(rs, k - T[ls].vl.l + T[ls].vr.l) - T[ls].vr); 
}
str gValR(int o, int k) {
    if (!k) return str(); 
    if (k == T[o].vr.l) return T[o].vr; 
    if (k <= T[rs].vr.l) return gValR(rs, k); 
    return T[rs].vr + (gValR(ls, k - T[rs].vr.l + T[rs].vl.l) - T[rs].vl); 
}

inline void pushup(int o) {
    if (T[ls].err || T[rs].err) return T[o].err = 1, void(); 
    T[o].err = 0; T[o].vl = T[ls].vl, T[o].vr = T[rs].vr; 
    if (T[ls].vr.l <= T[rs].vl.l) { // 左半段合并到右半段
        if (T[ls].vr == gValL(rs, T[ls].vr.l)) T[o].vl = T[o].vl + (T[rs].vl - T[ls].vr); 
        else T[o].err = 1; 
    } else {
        if (T[rs].vl == gValR(ls, T[rs].vl.l)) T[o].vr = T[o].vr + (T[ls].vr - T[rs].vl); 
        else T[o].err = 1; 
    }
}
void build(int o, int l, int r) {
    if (l == r) return T[o] = Node(a[l]), void(); 
    int mid = l + r >> 1; 
    build(ls, l, mid); build(rs, mid + 1, r); 
    pushup(o); 
}
void update(int o, int l, int r, int x, int k) {
    if (l == r) return T[o] = k, void(); 
    int mid = l + r >> 1; 
    if (x <= mid) update(ls, l, mid, x, k); 
    else update(rs, mid + 1, r, x, k); 
    pushup(o); 
}

int st[50], tot; 
void get(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return st[++tot] = o, void(); 
    int mid = l + r >> 1; 
    if (x <= mid) get(ls, l, mid, x, y); 
    if (mid < y) get(rs, mid + 1, r, x, y); 
}
str seq[50]; 
str gVal(int o, int k) {
    if (!k) return str(); 
    if (k == seq[o].l) return seq[o]; 
    if (k <= T[st[o]].vr.l) return gValR(st[o], k);
    return T[st[o]].vr + (gVal(o - 1, k - T[st[o]].vr.l + T[st[o]].vl.l) - T[st[o]].vl); 
}

bool query(int l, int r) {
    tot = 0; get(1, 1, n, l, r);
    for (int i = 1; i <= tot; ++i) {
        if (T[st[i]].err) return 0; 
        if (seq[i - 1].l < T[st[i]].vl.l) return 0; 
        if (T[st[i]].vl == gVal(i - 1, T[st[i]].vl.l)) 
            seq[i] = T[st[i]].vr + (seq[i - 1] - T[st[i]].vl); 
        else return 0; 
    }
    return !seq[tot].l; 
}

int main(void) {
    scanf("%d%d", &n, &k); Hash::init(n); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    build(1, 1, n); 
    for (scanf("%d", &m); m--; ) {
        int op, x, y; scanf("%d%d%d", &op, &x, &y); 
        if (op == 1) update(1, 1, n, x, y); 
        else puts(query(x, y) ? "Yes" : "No"); 
    }
    return 0;
}

根号技巧

一些根号杂题。

大分块系列

由于它们都比较经典，故此放在这里。

突刺贯穿的第二分块 | [Ynoi2018] 五彩斑斓的世界

Portal.

神秘的修改+神秘的查询，怎么搞？发现其值域小得可怜，而且时限很大，空限却很小。

离线，逐块处理（因为空间限制实在太小，想要预处理任何信息都是不可能的）。我们需要一个可以在 $O(m)$ 完成单个块内处理的算法。

记块内最大值为 $k$ ，那么：

$k\le 2x$ ，令大于 $x$ 的数减去 $x$ 后就没有比 $x$ 大的数了， $k$ 会减小至少 $k-x$ ；
$k>2x$ ，令小于等于 $x$ 的数加上 $x$ ，就没有比 $x$ 小的数了。然后打上全局减标记， $k$ 在操作后减少至少 $x$ 。

发现这个 $k$ 单调不增，那么时间复杂度为 $O(V)$ 。

维护数值时直接采用并查集，记录集合的大小。零散块修改直接重构，整块则直接维护。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int BLOCK_SIZE = 900; 

inline int read(void) {
    int x = 0, c = getchar_unlocked(); 
    while (!isdigit(c)) c = getchar_unlocked(); 
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar_unlocked(); 
    return x;  
}
void print(int x) {
    if (x > 9) print(x / 10); 
    putchar_unlocked(x % 10 ^ 48); 
}

int n, m, LL, RR, tag, mx, op, l, r, x; 
int a[1000005], Ans[500005]; 
int L[2005], R[2005]; 
int fa[1000005], root[100005], cnt[100005], val[1000005]; 
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
inline void merge(int x, int y) {
    if (root[y]) fa[root[x]] = root[y]; 
    else root[y] = root[x], val[root[y]] = y; 
    cnt[y] += cnt[x]; root[x] = cnt[x] = 0; 
}
struct Operation {
    int op, l, r, x; 
} Q[500005];

inline void build(void) {
    mx = tag = 0; 
    for (int i = LL; i <= RR; ++i) {
        mx = max(mx, a[i]); 
        if (root[a[i]]) fa[i] = root[a[i]]; 
        else root[a[i]] = fa[i] = i, val[i] = a[i]; 
        ++cnt[a[i]]; 
    }    
}
inline void rebuild(void) {
    for (int i = LL; i <= RR; ++i) {
        a[i] = val[find(i)]; root[a[i]] = cnt[a[i]] = 0; 
        a[i] -= tag; 
    }
    for (int i = LL; i <= RR; ++i) val[i] = 0; 
    int ql = max(l, LL), qr = min(r, RR); 
    for (int i = ql; i <= qr; ++i) if (a[i] > x) a[i] -= x; 
    build(); 
}
inline void modify(void) {
    if (x * 2 > mx - tag) {
        for (int i = x + 1 + tag; i <= mx; ++i) if (root[i]) merge(i, i - x); 
        mx = min(mx, x + tag); 
    } else {
        for (int i = tag; i <= x + tag; ++i) if (root[i]) merge(i, i + x); 
        tag += x; 
    }
}
inline int get(void) {
    int ql = max(l, LL), qr = min(r, RR), res = 0; 
    for (int j = ql; j <= qr; ++j) if (val[find(j)] == x + tag) ++res;  
    return res; 
}

int main(void) {
    n = read(); m = read(); int t = (n - 1) / BLOCK_SIZE + 1; 
    for (int i = 1; i <= t; ++i) L[i] = R[i - 1] + 1, R[i] = i * BLOCK_SIZE; R[t] = n; 
    for (int i = 1; i <= n; ++i) a[i] = read(); 
    for (int i = 1; i <= m; ++i) Q[i].op = read(), Q[i].l = read(), Q[i].r = read(), Q[i].x = read(); 

    for (int k = 1; k <= t; ++k) {
        LL = L[k], RR = R[k]; build(); 
        for (int i = 1; i <= m; ++i) {
            op = Q[i].op, l = Q[i].l, r = Q[i].r, x = Q[i].x; 
            if (r < LL || l > RR) continue; 
            if (op == 1) {
                if (x == 0) continue;                 
                if (l <= LL && RR <= r) modify(); 
                else rebuild(); 
            } else {
                if (x + tag > 100001) continue; 
                if (l <= LL && RR <= r) Ans[i] += cnt[x + tag]; 
                else Ans[i] += get(); 
            }
        }
        if (k != t) memset(root, 0, sizeof root), memset(cnt, 0, sizeof cnt); 
    }
    for (int i = 1; i <= m; ++i) if (Q[i].op == 2) print(Ans[i]), putchar_unlocked('\n');
    return 0; 
}

弑尽破净的第四分块 | [Ynoi2018] 天降之物

Portal.

本题存在序列分块做法，但对于本题来说根号分治可以做得更好。

考虑一个最暴力的做法，将所有数的位置放在 vector 中，然后直接暴力扫。对于出现次数多的数预处理出答案然后将 vector 清空。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int BLOCK_SIZE = 500; 
const int INF = 1e9; 

inline int read(void) {
    int x = 0, c = getchar_unlocked(); 
    while (!isdigit(c)) c = getchar_unlocked(); 
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar_unlocked();
    return x; 
}

int n, m, a[100005], siz[100005], F[100005], tot, id[100005], ans[230][100005]; 
vector<int> v[100005];

inline int calc(int x, int y) { // 对于 y 计算 x
    int i = 0, j = 0, ans = INF, sx = v[x].size(), sy = v[y].size(); 
    if (!sx || !sy) return INF; 
    while (i < sx && j < sy) {
        if (v[x][i] > v[y][j]) ans = min(ans, v[x][i] - v[y][j++]); 
        else ans = min(ans, v[y][j] - v[x][i++]); 
    }
    if (i < sx) ans = min(ans, abs(v[x][i] - v[y][sy - 1])); 
    if (j < sy) ans = min(ans, abs(v[x][sx - 1] - v[y][j])); 
    return ans; 
}
inline int query(int x, int y) {
    x = F[x], y = F[y]; 
    if (!siz[x] || !siz[y]) return -1; 
    if (x == y) return 0; 
    if (siz[x] > siz[y]) swap(x, y); 
    if (siz[y] <= BLOCK_SIZE) return calc(x, y); 
    if (siz[x] <= BLOCK_SIZE) return min(ans[id[y]][x], calc(x, y)); 
    return min({ans[id[y]][x], ans[id[x]][y], calc(x, y)}); 
}
inline void build(int x, int ID = 0) { // 处理 x, 存储在 ID 的答案
    if (ID) id[x] = ID; else id[x] = ++tot; int t = id[x]; 
    memset(ans[t], 0x3f, sizeof ans[t]); 
    for (int i = 1, j = INF; i <= n; ++i) 
        if (a[i] == x) j = 0; else ans[t][a[i]] = min(ans[t][a[i]], ++j); 
    for (int i = n, j = INF; i >= 1; --i) 
        if (a[i] == x) j = 0; else ans[t][a[i]] = min(ans[t][a[i]], ++j); 
    ans[t][x] = 0; vector<int> cl; v[x].swap(cl); 
}
inline void merge(int x, int y) { // 将 x 中的元素合并到 y 
    int i = 0, j = 0, sx = v[x].size(), sy = v[y].size(); vector<int> res; 
    while (i < sx && j < sy) {
        if (v[x][i] < v[y][j]) res.emplace_back(v[x][i++]); 
        else res.emplace_back(v[y][j++]); 
    }
    while (i < sx) res.emplace_back(v[x][i++]); 
    while (j < sy) res.emplace_back(v[y][j++]);
    v[y] = res; 
}
inline void update(int x, int y) { // 所有 x -> y
    int x_ = F[x], y_ = F[y]; 
    if (!siz[x_] || x_ == y_) return; 
    if (siz[x_] > siz[y_]) F[y] = x_, F[x] = n + 1, swap(x_, y_); 
    else F[x] = n + 1; 
    if (x_ > n || y_ > n) return; 
    x = x_, y = y_; 
    if (siz[y] <= BLOCK_SIZE) {
        if (siz[x] + siz[y] <= BLOCK_SIZE) {
            for (int i : v[x]) a[i] = y; 
            for (int i = 1; i <= tot; ++i) ans[i][y] = min(ans[i][y], ans[i][x]); 
            merge(x, y); 
        } else {
            for (int i = 1; i <= n; ++i) if (a[i] == x) a[i] = y; 
            build(y);
        }
    } else if (siz[x] <= BLOCK_SIZE) {
        if (siz[x] + v[y].size() <= BLOCK_SIZE) {
            for (int i : v[x]) a[i] = y; 
            for (int i = 1; i <= tot; ++i) ans[i][y] = min(ans[i][y], ans[i][x]); 
            merge(x, y); 
        } else {
            for (int i = 1; i <= n; ++i) if (a[i] == x) a[i] = y; 
            build(y, id[y]);
        }
    } else {
        for (int i = 1; i <= n; ++i) if (a[i] == x) a[i] = y; 
        build(y, id[y]); 
    }
    siz[y] += siz[x]; siz[x] = 0; 
    vector<int> cl; v[x].swap(cl); 
}

int main(void) {
    n = read(), m = read(); 
    for (int i = 1; i <= n; ++i) v[a[i] = read()].emplace_back(i), F[i] = i, ++siz[a[i]]; 
    for (int i = 1; i <= n; ++i) if (siz[i] > BLOCK_SIZE) build(i); 
    for (int last = 0; m--; ) {
        int op = read(), x = read() ^ last, y = read() ^ last; 
        if (op == 1) update(x, y); 
        else {
            last = query(x, y); 
            if (last == -1) last = 0, puts("Ikaros"); 
            else printf("%d\n", last); 
        }
    }
    return 0;
}

数据结构综合

这里是一些综合性 DS 难题。

根本原因是分块基本上就是暴力，而越是暴力的算法可扩展性就越强，能解决的问题就越多，因此题就可以变得相当复杂。 ↩︎