XCPC wiki - 区间信息

ST Table

ST 表 (Sparse Table, 稀疏表) 基于 倍增 思想，用于解决 可重复贡献问题$^\dagger$，支持在$\Theta(1)$ 的时间内 区间查询，不支持在线修改。

递推计算所有长度为$2$ 的幂的区间的结果。对于询问$[\mathscr{l}, r)$，记$k = \lfloor \log_2(r - \mathscr{l}) \rfloor$，结果为$[\mathscr{l}, \mathscr{l} + 2^k)$ 和$[r - 2^k, r)$ 的结果的并。

$^\dagger:$ 区间询问对应的运算符$*$ 满足$x*x=x$ 和结合律$(x*y)*z=x*(y*z)$ ，如$\max,\ \min,\ |\ ,\ \&,\ \gcd$ 等，包括 RMQ (Range Maximum/Minimum Query) 问题和区间 GCD。

标准 RMQ，复杂度$\Theta(n \log \log n) - \Theta(1)$。

template<class T, class Cmp = less<T>>  // greater:最大值 less:最小值
struct RMQ {
    const Cmp cmp = Cmp();
    static constexpr unsigned B = 64;
    using u64 = unsigned long long;
    int n;
    vector<vector<T>> a;
    vector<T> pre, suf, ini;
    vector<u64> stk;
    RMQ() {}
    RMQ(const vector<T>& v) {
        init(v);
    }
    void init(const vector<T>& v) {
        n = v.size();
        pre = suf = ini = v;
        stk.resize(n);
        if (!n) {
            return;
        }
        const int M = (n - 1) / B + 1;
        const int lg = __lg(M);
        a.assign(lg + 1, vector<T>(M));
        for (int i = 0; i < M; i++) {
            a[0][i] = v[i * B];
            for (int j = 1; j < B && i * B + j < n; j++) {
                a[0][i] = min(a[0][i], v[i * B + j], cmp);
            }
        }
        for (int i = 1; i < n; i++) {
            if (i % B) {
                pre[i] = min(pre[i], pre[i - 1], cmp);
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (i % B != B - 1) {
                suf[i] = min(suf[i], suf[i + 1], cmp);
            }
        }
        for (int j = 0; j < lg; j++) {
            for (int i = 0; i + (2 << j) <= M; i++) {
                a[j + 1][i] = min(a[j][i], a[j][i + (1 << j)], cmp);
            }
        }
        for (int i = 0; i < M; i++) {
            const int l = i * B;
            const int r = min(1U * n, l + B);
            u64 s = 0;
            for (int j = l; j < r; j++) {
                while (s && cmp(v[j], v[__lg(s) + l])) {
                    s ^= 1ULL << __lg(s);
                }
                s |= 1ULL << (j - l);
                stk[j] = s;
            }
        }
    }
    T operator()(int l, int r) {  // [l, r)
        if (l / B != (r - 1) / B) {
            T ans = min(suf[l], pre[r - 1], cmp);
            l = l / B + 1;
            r = r / B;
            if (l < r) {
                int k = __lg(r - l);
                ans = min({ ans, a[k][l], a[k][r - (1 << k)] }, cmp);
            }
            return ans;
        } else {
            int x = B * (l / B);
            return ini[__builtin_ctzll(stk[r - 1] >> (l - x)) + l];
        }
    }
};

精简 RMQ，复杂度为$\Theta(n \log n) - \Theta(1)$。

template<class T, class Cmp = greater<T>>  // greater:最大值 less:最小值
struct RMQ {  // 存的是值
    static constexpr int D = 30;
    const Cmp cmp = Cmp();
    vector<T> t[D + 1];

    explicit RMQ(vector<T>& a) {
        const int n = a.size();
        t[0] = a;
        for (int d = 1; d <= __lg(n); d++) {
            t[d].resize(n);
            for (int i = 0; i + (1ll << d) <= n; ++i) {
                t[d][i] = min(t[d - 1][i], t[d - 1][i + (1ll << (d - 1))], cmp);
            }
        }
    }

    T operator()(int l, int r) {  // [l, r)
        if (l >= r) return 0;
        int d = __lg(r - l);
        return min(t[d][l], t[d][r - (1ll << d)], cmp);
    }
};

template<class T, class Cmp = less<T>>  // greater:最大值 less:最小值
struct RMQ {  // 存的是下标
    static constexpr int D = 30;
    const Cmp cmp = Cmp();
    vector<T> a, t[D + 1];

    explicit RMQ(vector<T>& a) : a(a) {
        const int n = a.size();
        t[0].resize(n);
        iota(t[0].begin(), t[0].end(), 0);
        for (int d = 1; d <= __lg(n); d++) {
            t[d].resize(n);
            for (int i = 0; i + (1ll << d) <= n; i++) {
                int& ls = t[d - 1][i], & rs = t[d - 1][i + (1ll << (d - 1))];
                t[d][i] = min(a[ls], a[rs], cmp) == a[rs] ? rs : ls;
            }
        }
    }

    int operator()(int l, int r) {  // [l, r)
        if (l >= r) return -1;
        int d = __lg(r - l);
        int& p = t[d][l], & q = t[d][r - (1ll << d)];
        return min(a[p], a[q], cmp) == a[q] ? q : p;
    }
};

RMQ 问题的其它解决方法：

离线 + 单调栈 考虑栈顶为$i$ 单调栈和$r = i + 1$ 的所有询问。在单调栈上二分查找最小的$\geqslant l$ 的下标。复杂度为$\Theta(n + q \log n)$。

分块 块大小为$B$。对于块的结果形成的序列，计算所有区间的最小值，这部分复杂度为$\Theta((\frac{n}{B})^2)$。对每个块计算块内前缀最小值和后缀最小值，这部分复杂度为$\Theta(n)$。若询问至少和两个块有交, 复杂度为$\Theta(1)$；否则为$\Theta(B)$。这部分复杂度为$\Theta(qB)$。取$B = n^{2/3} q^{-1/3}$，复杂度为$\Theta(n^{8/3})$。

线性算法 块大小为$w$, 在 Word-RAM 模型中$w = \Omega(\log n)$,$w$ 位整数位运算复杂度为$\Theta(1)$。对于块的结果形成的序列, 使用稀疏表, 由于$n \leqslant w \log n$ 这 部分复杂度为$\Theta(n)$。对每个块计算块内前缀最小值和后缀最小值, 这部分复杂度为$\Theta(n)$。对每个块在块内计算每个单调栈的二进制表示, 通过位运算可以使得计算单调栈均摊复杂度和询问复杂的都是$\Theta(1)$。复杂度为$\Theta(n) - \Theta(1)$。

BIT 树状数组

树状数组 (bisrch Index Tree, 二进制下标树) 用于维护满足 结合律 和 可差分（即具有逆运算，如和、积、异或）的区间信息，支持在$\Theta(n)$ 的空间和$\Theta(\log n)$ 的时间内 单点修改 和 区间查询。

树上节点$p$ 存储区间$(p-\operatorname{lowbit}p,\ p]$ 的某个性质，其中$\operatorname{lowbit}p$ 表示$p$ 的二进制中 1 的最低位。前缀查询 $[1,p]$ 可按二进制拆成对$\Theta(\log p)$ 个子区间求和。

以维护区间的和（单点修改和区间查询）为例：

struct BIT {
    vector<int> t;
    int N;
    BIT(int n) {
        N = n + 1;
        t.resize(N);
    }
    void update(int p, int x) {
        while (p < N) t[p] += x, p += p & -p;
    }
    int query(int p) {
        int res = 0;
        while (p >= 1) res += t[p], p -= p & -p;
        return res;
    }
    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

例题 洛谷P3374

BIT.1 权值树状数组 × 二维偏序

在二维的情形，分别对两个属性定义序关系，一定能得到一种偏序关系：

$$(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j\lesseqgtr a_i\;\text{and}\; b_j\lesseqgtr b_i$$

二维偏序问题一般用 树状数组 解决。

模板

给定平面直角坐标系上的若干点，定义点的等级为既不在它上面也不在它右边的点的数量，求每个等级的点的数量。数据范围：$n \leqslant 5\times10^{5},\ 0 < x,y < n$。

分析：这定义了偏序关系

$$(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j\ \leqslant a_i\;\text{and}\; b_j \leqslant b_i$$

选$a$ 为第一关键词，$b$ 为第二关键词排序，按顺序将$b$ 存入树状数组，动态求前缀和。

constexpr int N = 5e5 + 8;
struct BIT {
    ll t[N];
    void modify(int p, int x) { while (p < N) t[p] += x, p += p & -p; }
    ll query(int p) { ll res = 0; while (p >= 1) res += t[p], p -= p & -p; return res; }
    ll query(int l, int r) { return query(r) - query(l - 1); }
} bit;

int main() {
    int n = read();
    vector<pair<int, int> > a(n);
    for (auto& [x, y] : a) x = read(), y = read();
    sort(a.begin(), a.end());

    vector<int> ans(n);
    bit.init();
    for (auto& [x, y] : a) {
        ans[bit.query(y)] += 1;
        bit.modify(y, 1);
    }

    for (auto& i : ans) printf("%d\n", i);
}

应用：逆序对

逆序对的本质：

$$(j,a_j)\prec(i,a_i) \;\xlongequal{def}\; j\lt i\;\text{and}\; a_j\gt a_i$$

将序列从后向前倒着插入 BIT，插入$a_i$ 前，统计已插入的比$a_i$ 小的数字的数量 query(a[i])，即是序列中满足$j>i,\ a_j<a_i$ 的数量，也即$a_i$ 对应的逆序对的数量。考虑到给出的数字较大，且存在负数，又注意到逆序数只与数字的相对大小有关，先 离散化。

constexpr int N = 5e5 + 8;
struct BIT {
    ll t[N];
    void modify(int p, int x) { while (p < N) t[p] += x, p += p & -p; }
    ll query(int p) { ll res = 0; while (p >= 1) res += t[p], p -= p & -p; return res; }
    ll query(int l, int r) { return query(r) - query(l - 1); }
} bit;

int a[N];
pair<int, int> b[N];

int main() {
    int n = read();
    for (int i = 1; i <= n; ++i) b[i] = { read(),i };
    
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i) a[b[i].second] = i;  // 离散化

    ll sum = 0;
    bit.init();
    for (int i = n; i >= 1; --i) {
        sum += bit.query(a[i]);    // 插入前统计
        bit.modify(a[i], 1);       // 倒着插入
    }
    printf("%lld\n", sum);

    return 0;
}

注 更标准的离散化写法，即复制、排序、去重、查找，时间复杂度$\Theta(n\log n)$：

int arr[N], val[N];
void eachT() {
    memcpy(val, arr, sizeof arr);                       // 复制
    sort(val, val + n);                            // 排序
    int val_size = unique(val, val + n) - val;   // 去重
    for (int i = 0; i < n; ++i)                         // 查找
        arr[i] = lower_bound(val, val + val_size, arr[i]) - val + 1;
}

例题 HDU1394 Minimum Inversion Number

更一般的情形

而其他二维偏序关系，可以作不同的处理转化为最简单的二维偏序。例如：

• $(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j\lt a_i\;\text{and}\; ?$：把第一关键词的小于等于改成小于，需要在对第二关键词排序时进行 逆序排序。
• $(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j \geqslant a_i\;\text{and}\; ?$：把第一关键词的小于等于改成大于等于，需要在对第一关键词排序时进行 逆序排序。
• $(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j\gt a_i\;\text{and}\; ?$：把第一关键词的小于等于改成大于，需要在对两个关键词排序时都进行 逆序排序。
• $(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; ?\;\text{and}\; b_j\lt b_i$：把第二关键词的小于等于改成小于，查询时使用 query(x-1) 而不是 query(x)。
• $(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; ?\;\text{and}\; b_j \geqslant b_i$：把第二关键词的小于等于改成大于等于，对第二关键词 离散化 时进行 逆序排序。
• $(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; ?\;\text{and}\; b_j \geqslant b_i$：把第二关键词的小于等于改成大于等于，对第二关键词 离散化 时进行 逆序排序，并且查询时使用 query(x-1) 而不是 query(x)。

例题

坐标轴 OX 上有$n$ 个点。第$i$ 个点的初始坐标为$x_{i0}$（保证互不相同），速度为恒定值$v_i$，则它在$t\in\mathbb{R}_{+}$ 时刻的坐标为$x_{i}(t)=x_{i0} + t v_i$。

设$d(i, j)$ 为两点$i$ 和$j$ 之间的最小距离，即$\min\limits_{t>0}\lbrace |x_{i}(t)-x_{j}(t)| \rbrace$。

计算$\sum\limits_{1 \leqslant i, j \leqslant n}$$d(i, j)$。

| K | ⭐⭐ | 图论、线段树综合应用、思维 | 洛谷P5025[SNOI2017] |

BIT.2 高阶前缀和

BIT.2.1 区间修改和单点查询

利用差分，将此问题转化为单点修改和区间查询。具体地，记$b_i = a_i - a_{i-1}$，则$a_i = \sum b_j$，用 BIT 维护序列$\lbrace b_i\rbrace$ 的前缀和，修改$[l,r]$ 即$b_l:=b_l+x,\ b_{r+1}:=b_{r+1}-x$。

void eachT() {
    int n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        bit.modify(i, a[i] - a[i - 1]);
    }
    for (int q = read(); q--; ) {
        int op = read();
        if (op) bit.modify(l, num), bit.modify(r + 1, -num);
        else print(bit.query(x));
    }
}

例题 洛谷P3368

BIT.2.2 区间修改和区间查询

即线段树模板题。

类似地，利用差分，

$$s_k = \sum_{i=1}^{k} a_i = \sum_{i=1}^{k} \sum_{j=1}^{i} b_j = \sum_{i=1}^{k} \sum_{j=i}^{k} b_i = (k+1) \sum_{i=1}^{k} b_i - \sum\limits_{i=1}^{k} ib_i$$

用两个 BIT 分别维护序列$\lbrace b_i\rbrace$、$\lbrace ib_i\rbrace$ 的前缀和。

int n;
ll tr[N], tree2[N];

inline int lowbit(int _n) { return _n & (-_n); }

void modify(int i, int num) {
    for (int p = i; p < N; p += lowbit(p)) {
        tr[p] += num, tree2[p] += num * i;
    }   // 维护什么写什么
}

inline ll query(int i) {
    ll res = 0;
    for (int p = i; p; p -= lowbit(p)) {
        res += (i + 1) * tr[p] - tree2[p];
    }   // 计算公式是什么就写什么
    return res;
}

inline ll query(int l, int r) {
    return query(r) - query(l - 1);
}

void eachT() {
    memset(tree, 0, sizeof tree);
    n = read();
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        modify(i, a[i] - a[i-1]);
    }
    for (int q = read(); q--; ) {
        int op = read();
        if (op) modify(l, num), modify(r + 1, -num);
        else print(query(l, r));
    }
}

例题 洛谷P3372

BIT2.3 高阶前缀和

一般地，对于$m$ 阶前缀和，计算$C_{k-x+m-1}^{m-1}$，得到关于$x$ 的多项式$a_0x^0 + a_1x^1 + a_2x^2 + \cdots$，则

$$s_k = a_0\sum\limits_{i=1}^{k} b_i + a_1 \sum\limits_{i=1}^{k} ib_i + a_2 \sum\limits_{i=1}^{k} i^2b_i + \cdots$$

例如，当$m=3$ 时，$s_k = \left(k^2+3k+2\right)\sum\limits_{i=1}^{k} b_i + \left(-2k-3\right) \sum\limits_{i=1}^{k} ib_i + \sum\limits_{i=1}^{k} i^2b_i$。

BIT.2 多维 BIT

二维数组的区间修改和区间查询：构造差分数组$b_{ij}$，则

$$\begin{aligned} s_{uv} = \sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v} a_{ij} &= \sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v} \sum\limits_{k=1}^{i}\sum\limits_{l=1}^{j} b_{kl} \\ &= \sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v} \sum\limits_{k=i}^{u}\sum\limits_{l=j}^{v} b_{ij} \\ &= \sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v} (u-i+1)(v-j+1)b_{ij} \\ &= (u+1)(v+1)\sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v}b_{ij} -u\sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v}jb_{ij} \\ &\qquad\ -v\sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v}ib_{ij} +\sum\limits_{i=1}^{u}\sum\limits_{j=1}^{v}ijb_{ij} \end{aligned}$$

用四个 BIT 分别维护序列$\lbrace b_{ij}\rbrace$、$\lbrace ib_{ij}\rbrace$、$\lbrace jb_{ij}\rbrace$、$\lbrace ijb_{ij}\rbrace$ 的前缀和。

ll t1[N][N], t2[N][N], t3[N][N], t4[N][N];

inline int lowbit(int _n) { return _n & (-_n); }

void modify(int i, int j, int num) {
    for (int p = i; p < N; p += lowbit(p)) {
        for (int q = j; q < N; q += lowbit(q)) {
            t1[p][q] += num;
            t2[p][q] += j * num;
            t3[p][q] += i * num;
            t4[p][q] += i * j * num;
        }   // 维护什么写什么
    }
}

inline ll query(int i, int j) {
    ll res = 0;
    for (int p = i; p; p -= lowbit(p)) {
        for (int q = j; q; q -= lowbit(q)) {
            res += (i + 1) * (j + 1) * t1[p][q]
                - (i + 1) * t2[p][q]
                - (j + 1) * t3[p][q]
                + t4[p][q];
        }   // 计算公式是什么就写什么
    }
    return res;
}

void eachT() {
    for (int q = read(); q--; ) {
        int op = read();
        if (op) {
            int x1 = read(), y1 = read(), x2 = read(), y2 = read(), num = read();
            modify(x1, y1, num);
            modify(x2 + 1, y1, -num);
            modify(x1, y2 + 1, -num);
            modify(x2 + 1, y2 + 1, num);
        } else {
            int x1 = read(), y1 = read(), x2 = read(), y2 = read();
            printf("%lld\n", query(x2, y2)
                - query(x1 - 1, y2)
                - query(x2, y1 - 1)
                + query(x1 - 1, y1 - 1));
        }
    }
}

例题 洛谷P4514上帝造题的七分钟

BIT.3 后缀 BIT

维护后缀和。交换 modify 和 query 的跳转方式。

int n;
ll tr[N];

inline int lowbit(int _n) { return _n & (-_n); }

void modify(int i, int num) {
    for (int p = i; p; p -= lowbit(p)) tr[p] += num;
}  // 修改 a[i] += num

inline ll query(int i) {
    ll res = 0;
    for (int p = i; p < N; p += lowbit(p)) res += tr[p];
    return res;
}  // 查询 return lst[i]

对于可减信息，用前缀后缀 BIT 维护是一样的。但在当信息不可减且可转化为询问后缀时，能够不翻转序列地维护修改和查询。

二维数点

给定平面内$n$ 个点，每个点有点权，$q$ 次询问以$(x_1,y_1)$ 为左下角，$(x_2,y_2)$ 为右上角的矩形内部（包括边界）点权之和。

constexpr int N = 1e7 + 8;
struct BIT {
    ll t[N];
    void modify(int p, int x) { while (p < N) t[p] += x, p += p & -p; }
    ll query(int p) { ll res = 0; while (p >= 1) res += t[p], p -= p & -p; return res; }
    ll query(int l, int r) { return query(r) - query(l - 1); }
} bit;

struct POS {
    int x, y, val;
};
bool poscmp(const POS& a, const POS& b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

struct QUE {
    int x, y, id, d;
};
bool quecmp(const QUE& a, const QUE& b) {
    return a.x == b.x ? a.y < b.y : a.x < b.x;
}

void eachT() {
    int n = read(), q = read();

    vector<int> xall, yall;  // 离散化数组

    vector<POS> pos(n);
    for (int i = 0; i < n; ++i) {
        int x = read(), y = read(), val = read();
        pos[i] = { x, y, val };

        xall.push_back(x);
        yall.push_back(y);
    }
    sort(pos.begin(), pos.end(), poscmp);

    vector<QUE> que;
    for (int i = 0; i < q; ++i) {
        int x1 = read(), y1 = read(), x2 = read(), y2 = read();
        que.emplace_back(x2, y2, i, 1);
        que.emplace_back(x1 - 1, y1 - 1, i, 1);
        que.emplace_back(x1 - 1, y2, i, -1);
        que.emplace_back(x2, y1 - 1, i, -1);

        xall.push_back(x1 - 1);
        xall.push_back(x2);
        yall.push_back(y1 - 1);
        yall.push_back(y2);
    }
    sort(que.begin(), que.end(), quecmp);

    // 离散化
    sort(xall.begin(), xall.end());
    sort(yall.begin(), yall.end());
    for (int i = 0; i < n; ++i) {
        pos[i].x = lower_bound(xall.begin(), xall.end(), pos[i].x) - xall.begin() + 1;
        pos[i].y = lower_bound(yall.begin(), yall.end(), pos[i].y) - yall.begin() + 1;
    }
    for (int i = 0; i < q * 4; ++i) {
        que[i].x = lower_bound(xall.begin(), xall.end(), que[i].x) - xall.begin() + 1;
        que[i].y = lower_bound(yall.begin(), yall.end(), que[i].y) - yall.begin() + 1;
    }

    vector<ll> res(q);
    int pi = 0;
    for (int qi = 0; qi < que.size(); ++qi) {
        while (pi < n && pos[pi].x <= que[qi].x) {
            bit.modify(pos[pi].y, pos[pi].val);
            ++pi;
        }
        res[que[qi].id] += que[qi].d * bit.query(que[qi].y);
    }

    for (int i = 0; i < q; ++i) {
        printf("%lld\n", res[i]);
    }
}

SMT 线段树

线段树 (Segment Tree) 用于维护满足 结合律 的区间信息，支持在$\Theta(\log n)$ 的时间内 区间修改 和 区间查询。

线段树是一棵 平衡二叉树，树上每个 节点 $\pmb{p}$ 都存储一条 线段（区间） $\pmb{[l,r]}$ 的某个性质，节点$p$ 的左右子节点的编号分别为 $2p$ 和 $2p+1$，分别储存 $[l, \mathrm{mid}]$ 和 $[\mathrm{mid}+1, r]$。

修改时，使用 懒标记$\pmb{\mathrm{mark}_p}$，表示该节点$p$ 对应的区间上每一个点都要加上某个数，用到它的 子区间 的时候，再向下 传递 修改。

预处理时间复杂度$\Theta(n)$，查询或修改时间复杂度$\Theta(\log n)$。

当值域为$v$ 时，普通的线段树的空间复杂度是$\Theta(4v)$。如果$v$ 巨大，但查询次数$q$ 较小时，边修改边建树，这样空间的复杂度是$\Theta(q\log v)$。

递归的起点是区间$[L,R]$，依数据范围修改，允许是负数。注意，这里的 >>1 不能写为 /2。

SMT1. 单点修改

template<class info>
struct SMT {
    int L, R, p, pcnt;
    vector<info> t;
    vector<int> ls, rs;

    SMT() {
        init(0, 0);
        t.resize(N << 2);
        ls.resize(N << 2);
        rs.resize(N << 2);
    }

    void init(int l, int r) {
        L = l, R = r;
        p = pcnt = 0;
    }

    void init(int p) {
        t[p] = info();
        ls[p] = rs[p] = 0;
    }

#define mid ((L+R)>>1)
#define leaf (R-L<2)
#define curr p,L,R
#define lson ls[p],L,mid
#define rson rs[p],mid,R
#define self p,int L,int R

    void push_up(int& p) {
        t[p] = t[ls[p]] + t[rs[p]];
    }

    // 建树
    void build(int& self, const vector<info>& a) {
        if (!p) p = ++pcnt, init(p);
        if (leaf) return t[p].apply(a[L]);
        build(lson, a);
        build(rson, a);
        return push_up(p);
    }
    void build(const vector<info>& a) {
        return build(curr, a);
    }

    // 单点修改
    void modify(int& self, int x, const info& d) {
        if (!p) p = ++pcnt, init(p);
        if (leaf) return t[p].apply(d);
        if (x < mid) modify(lson, x, d);
        else modify(rson, x, d);
        return push_up(p);
    }
    void modify(int x, const info& d) {
        return modify(curr, x, d);
    }

    // 查询[l,r)
    info query(int& self, int l, int r) {
        if (l <= L && R <= r) return t[p];
        info res;
        if (l < mid) res = res + query(lson, l, r);
        if (mid < r) res = res + query(rson, l, r);
        return res;
    }
    info query(int l, int r) {
        if (l >= r) return info();
        return query(curr, l, r);
    }
};

SMT1.1 区间最大子段和

给定长度为$n$ 的整数序列$a$，有$q$ 个询问：

• $1, l, r$：输出$a_l, a_{l+1}, ..., a_{r-1}$ 中的最大子段和。
• $2, p, x$：将$a_p$ 修改为$x$。Link

struct info {
    ll sum{ 0 };       // 区间和
    ll lval{ -Inf };   // 左边界必选的最大区间和
    ll rval{ -Inf };   // 右边界必选的最大区间和
    ll val{ -Inf };    // 无限制的最大区间和
    void apply(const info& o)& {
        sum = lval = rval = val = o.sum;
    }
    friend info operator + (const info& l, const info& r) {
        info res;
        res.lval = max(l.lval, l.sum + r.lval);
        res.rval = max(r.rval, r.sum + l.rval);
        res.sum = l.sum + r.sum;
        res.val = max({ l.val, r.val, l.rval + r.lval });
        return res;
    }
};

区间修改，区间最大子段和是 黑题。

SMT1.2 一次函数区间复合函数求值

半群 若集合$S$ 和二元运算$\text{op} : S \times S \rightarrow S$ 满足对任意$x, y, z \in S$ 都有$\text{op}(\text{op}(x, y), z) = \text{op}(x, (y, z))$, 称$(S, \text{op})$ 为半群。因此本题为半群单点修改，区间求积 (Link)

给定长度为$n$ 的由一次函数形成的序列$f_{i}=a_{i}x+b_{i}$，有$q$ 个询问：

• $p, a, b$：将$f_p$ 修改为$f_p(x) = ax + b$。
• $l, r, x$：求$f_{r-1}(...f_{l+1}(f_l(x))) \bmod 998244353$。

Input	Output
5 5 1 2 3 4 5 6 7 8 9 10 1 0 5 11 1 2 4 12 0 1 13 14 1 0 4 15 1 2 5 16	14005 470 8275 5500

• 维护 区间$[l,r]$ 的$a$ 和$b$，即$f_{r}(...f_{l+1}(f_l(x)))=ax+b$；
• 修改 单点修改，无需懒标记；
• 合并 结合复合函数$f_{r}(f_{l}(x))=a_{r}(a_{l}x+b_{l})+b_{r}=(a_{r}a_{l})x+(a_{r}b_{l}+b_{r})$，注意复合具有方向性！即不满足交换律，$f_{r}(f_{l}(x)) \neq f_{l}(f_{r}(x))$。

struct info {
    Z a{ 1 }, b{ 0 };
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.a * r.a, r.a * l.b + r.b };
    }
};

smt.modify(p, { a, b });
auto res = smt.query(l, r);
cout << res.a * x + res.b << '\n';

SMT2. 区间修改、懒标记

template<class info, class mark>
struct SMT {
    int L, R, p, pcnt;
    vector<info> t;
    vector<mark> m;
    vector<int> ls, rs;

    SMT() {
        init(0, 0);
        t.resize(N << 2);
        m.resize(N << 2);
        ls.resize(N << 2);
        rs.resize(N << 2);
    }

    void init(int l, int r) {
        L = l, R = r;
        p = pcnt = 0;
    }

    void init(int p) {
        t[p] = info();
        m[p] = mark();
        ls[p] = rs[p] = 0;
    }

    #define mid ((L+R)>>1)
    #define leaf (R-L<2)
    #define curr p,L,R
    #define lson ls[p],L,mid
    #define rson rs[p],mid,R
    #define self p,int L,int R

    void push_up(int& p) {
        t[p] = t[ls[p]] + t[rs[p]];
    }

    void push_down(int& self, const mark& d) {
        if (!p) p = ++pcnt, init(p);
        t[p].apply(d, L, R);
        m[p].apply(d, L, R);
    }
    void push_down(int& self) {
        if (leaf) return;
        push_down(lson, m[p]);
        push_down(rson, m[p]);
        m[p] = mark();
    }

    // 建树
    void build(int& self, const vector<info>& a) {
        if (!p) p = ++pcnt, init(p);
        if (leaf) return t[p].apply(a[L]);
        build(lson, a);
        build(rson, a);
        return push_up(p);
    }
    void build(const vector<info>& a) {
        return build(curr, a);
    }

    // 区间[l,r)修改
    void modify(int& self, int l, int r, const mark& d) {
        if (!p) p = ++pcnt, init(p);
        if (l <= L && R <= r) return push_down(curr, d);
        push_down(curr);
        if (l < mid) modify(lson, l, r, d);
        if (mid < r) modify(rson, l, r, d);
        return push_up(p);
    }
    void modify(int l, int r, const mark& d) {
        if (l >= r) return;
        return modify(curr, l, r, d);
    }

    // 单点修改
    void modify(int& self, int x, const info& d) {
        if (!p) p = ++pcnt, init(p);
        if (leaf) return t[p].apply(d);
        push_down(curr);
        if (x < mid) modify(lson, x, d);
        else modify(rson, x, d);
        return push_up(p);
    }
    void modify(int x, const info& d) {
        return modify(curr, x, d);
    }

    // 查询[l,r)
    info query(int& self, int l, int r) {
        if (l <= L && R <= r) return t[p];
        push_down(curr);
        info res;
        if (l < mid) res = res + query(lson, l, r);
        if (mid < r) res = res + query(rson, l, r);
        return res;
    }
    info query(int l, int r) {
        if (l >= r) return info();
        return query(curr, l, r);
    }

    // 全局找满足f的最小下标
    int findL(int& self, auto&& f) {
        if (!f(t[p])) return inf;  // 整个区间不合题意
        if (leaf) return L;        // 到达叶子 返回键
        push_down(curr);
        int s = findL(lson, f);    // 优先看左边
        if (s != inf) return s;    // 左边合题意
        return findL(rson, f);     // 左边不合题意再看右边
    }
    int findL(auto&& f) {
        return findL(curr, f);
    }

    // 全局找满足f的最大下标
    int findR(int& self, auto&& f) {
        if (!f(t[p])) return -inf; // 整个区间不合题意
        if (leaf) return L;        // 到达叶子 返回键
        push_down(curr);
        int s = findR(rson, f);    // 优先看右边
        if (s != -inf) return s;   // 右边合题意
        return findR(lson, f);     // 右边不合题意再看左边
    }
    int findR(auto&& f) {
        return findR(curr, f);
    }

    // 在区间[l,r)中找满足f的最小下标
    int findL(int& self, int l, int r, auto&& f) {
        if (l <= L && R <= r && !f(t[p])) return inf;  // 在当前区间内且不合题意
        if (leaf) return L;                            // 递归到叶 直接返回
        push_down(curr);
        if (l < mid) {
            int res = findL(lson, l, r, f);            // 先向左递归找
            if (res != inf) return res;                // 左边不是-1说明左边有解 那不用管右边了
        }
        if (mid < r) return findL(rson, l, r, f);      // 左边无解再看右边
        return inf;
    }
    int findL(int l, int r, auto&& f) {
        return findL(curr, l, r, f);
    }

    // 在区间[l,r)中找满足f的最大下标
    int findR(int& self, int l, int r, auto&& f) {
        if (l <= L && R <= r && !f(t[p])) return -inf; // 在当前区间内且不合题意
        if (leaf) return L;                            // 递归到叶 直接返回
        push_down(curr);
        if (mid < r) {
            int res = findR(rson, l, r, f);            // 先向右递归找
            if (res != -inf) return res;               // 右边不是-1说明右边有解 那不用管左边了
        }
        if (l < mid) return findR(lson, l, r, f);      // 右边无解再看左边
        return -inf;
    }
    int findR(int l, int r, auto&& f) {
        return findR(curr, l, r, f);
    }
};

SMT2.1 区间乘、区间加，区间和

自同态 若$f : S \rightarrow S$ 满足对任意$x, y \in S$,$f(\text{op}(x, y)) = \text{op}(f(x), f(y))$, 称$f$ 为$S$ 的自同态。$S$ 所有自同态的集合记为$\text{End}(S)$。所以这也叫半群区间自同态作用，区间求积（？

给定长度为$n$ 的整数序列$a$，有$q$ 个询问：

• $0, l, r, b, c$：对所有$i \in [l, r)$, 将$a_i$ 修改为$a_i \times b + c$。
• $1, l, r, b$：对所有$i \in [l, r)$, 将$a_i$ 修改为$a_i \times b$。
• $2, l, r, c$：对所有$i \in [l, r)$, 将$a_i$ 修改为$a_i + c$。
• $3, l, r$：求$\sum_{i=l}^{r-1} a_i \bmod 571373$。Link

区间乘、区间加：

struct mark {
    Z mul{ 1 };   // 乘法标记
    Z add{ 0 };   // 加法标记
    void apply(const mark& o, int s)& {
        mul *= o.mul;
        add = add * o.mul + o.add;
    }
};

struct info {
    Z sum{ 0 };
    void apply(const mark& o, int s)& {
        sum *= o.mul;
        sum += o.add * s;
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.sum + r.sum };
    }
};

if (op == 0) smt.modify(l, r, { read(), read() });
if (op == 1) smt.modify(l, r, { read(), 0 });
if (op == 2) smt.modify(l, r, { 1, read() });
if (op == 3) cout << smt.query(l, r).sum << '\n';

应用：VJspr15H - 序列操作

长度为$n$ 的序列，有三种操作：

1. I a b c 表示将$[a,b]$ 这一段区间的元素集体增加$c$；
2. R a b表示将$[a,b]$ 区间内所有元素变成相反数；
3. Q a b c 表示询问$[a,b]$ 这一段区间中选择$c$ 个数相乘的所有方案的和$\bmod 19940417$ 的值。

Input	Output
5 5 1 2 3 4 5 I 2 3 1 Q 2 4 2 R 1 5 I 1 3 -1 Q 1 5 1	40 19940397

数据范围：$n \leqslant 50000$，$q \leqslant 50000$，初始$|a_{i}|\leqslant 10^9$，I 操作中$|c| \leqslant 10^9$，Q 操作中$1 \leqslant c \leqslant \min(b-a+1,20)$。

维护什么？
设$f_{c}$ 为选择$c$ 个数相乘的所有方案的和，这具有递推性，直接维护所有的答案$f_{c}\ (1 \leqslant c \leqslant 20)$。

如何更新？
push_up：选择$c$ 个数，可以左边选$i$ 个，右边选$c-i$ 个，结果应当是相乘，即

$$p.f_{c}=\sum_{i=0}^{20}l.f_{i}\cdot r.f_{c-i}$$

void push_up(seg& p, seg l, seg r) {
    for (int i = 0; i <= 20; ++i) {
        p.f[i] = 0;
        for (int j = 0; j <= i; ++j) {
            p.f[i] += l.f[j] * r.f[i - j];
        }
    }
    return;
}

区间变成相反数是区间乘的简化版，考察区间乘和区间加对$f$ 的影响：

• 根据上一题的结论，懒标记的下传应当先乘再加；
• 区间$\times d$ 后，选择$c$ 个数相乘的所有方案的和$f_{c}\leftarrow f_{c}\times d^{c}$，子节点的两种懒标记都$\times d$；
• 区间$+d$ 后，选择$c$ 个数相乘的所有方案的和的变化比较复杂，假设我们选出的数是$a_{1},a_{2},\dots, a_{c}$，原先对答案的贡献是$S_{c}=\prod\limits_{i=1}^{c} a_{i}$，区间$+d$ 后，对答案的贡献是$S'_{c}=\prod\limits_{i=1}^{c} (a_{i}+d)$，对答案的贡献的增量$$\Delta S_{c}=\sum_{k=0}^{c}d{k}\operatorname{C}{n-(c-k)}^{k}\prod a$$，因此答案的总增量可以表示为$$
  \Delta f{c}=\sum_{k=0}^{c}d{k}\operatorname{C}{n-(c-k)}^{k}f{i-k}$$预处理组合数，根据递推式二重循环即可。

时间复杂度$\Theta(m^{2}n\log n)$，其中$m=20$，常数较大。

constexpr int N = 5e4 + 8, M = 21;
using Z = ModInt<19940417>;
Z C[N][M];
void beforeT() {
    for (int i = 0; i < N; ++i) {
        C[i][0] = 1;
        if (i < M) C[i][i] = 1;
        for (int j = 1; j < i && j < M; ++j)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
    }
}

struct mark {
    Z mul{ 1 };   // 乘法标记
    Z add{ 0 };   // 加法标记
    void apply(const mark& o, int s)& {
        mul *= o.mul;
        add = add * o.mul + o.add;
    }
};

struct info {
    vector<Z> sum;
    info(Z a0 = 0, Z a1 = 0) {
        sum.resize(M);
        sum[0] = a0;
        sum[1] = a1;
    }
    void apply(const mark& o, int s)& {
        if (o.mul == -1) {
            for (int i = M - 1; i >= 0; --i) {
                if (i & 1) sum[i] *= o.mul;
            }
        }
        if (o.add.vale()) {
            for (int i = M - 1; i >= 0; --i) {
                for (int j = 1; j <= i; ++j) {
                    if (s - i + j >= 0)
                        sum[i] +=
                        C[s - i + j][j]
                        * ((o.add).pow(j))
                        * sum[i - j];
                }
            }
        }
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        info res;
        for (int i = 0; i < M; ++i) {
            res.sum[i] = 0;
            for (int j = 0; j <= i; ++j) {
                res.sum[i] += l.sum[j] * r.sum[i - j];
            }
        }
        return res;
    }
};

void eachT() {
    int n = read(), q = read();

    beforeT();
    SMT<info, mark> smt;
    smt.init(1, n);

    for (int i = 1; i <= n; ++i) {
        int x = read();
        smt.modify(i, info{ 1, x });
    }

    while (q--) {
        char op = getchar();
        int l = read(), r = read();
        if (op == 'I') smt.modify(l, r, { 1, read() });
        if (op == 'R') smt.modify(l, r, { -1, 0 });
        if (op == 'Q') cout << smt.query(l, r).sum[read()] << '\n';
    }
}

SMT2.2 区间加，区间平方和

struct mark {
    double add{ 0 };
    void apply(const mark& o, int s)& {
        add += o.add;
    }
};

struct info {
    double sum{ 0 }, ssq{ 0 };
    void apply(const mark& o, int s)& {
        ssq += 2 * o.add * sum + o.add * o.add * s;
        sum += o.add * s;
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.sum + r.sum, l.ssq + r.ssq };
    }
};

例：区间方差

$$S^{2}=\dfrac{1}{n}\sum(x_{i}-\bar{x})^{2}=\dfrac{1}{n}\sum x_{i}^{2}-\bar{x}^{2}$$

SMT2.3 区间赋值，区间和

603 教室里有$n$ 盏灯，从左到右依次编号为：$1,2,\dots,n$，初始时都是开着的。人走灯灭，下课后，$m$ 个同学依次经过灯的开关，每个人会执行以下两种操作中的一种：

• 操作$1$：关上从$l$ 到$r$（含边界）范围内的所有灯；
• 操作$2$：打开从$l$ 到$r$（含边界）范围内的所有灯。

请你帮助班长计算，为了关上所有的灯，他还需要关上几盏灯。

数据范围：$1  \leqslant  n \leqslant 10^9, \quad 1  \leqslant  m \leqslant  3·10^{5}, \quad 1  \leqslant  l_{i},r_{i} \leqslant  n, \quad 1  \leqslant  k_{i} \leqslant  2$，本题的内存限制为 256 megabytes。(VJsum1B. Physical Education Lessons)

为优化阅读体验，重写了题目描述。——KobicGend

struct mark {
    int asn{ -1 };  // 赋值标记
    void apply(const mark& o, int s)& {
        if (~o.asn) asn = o.asn;
    }
};

struct info {
    int sum{ 0 };
    void apply(const mark& o, int s)& {
        if (~o.asn) sum = o.asn * s;
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.sum + r.sum };
    }
};

void eachT() {
    int n = read();
    SMT<info, mark> smt;
    smt.init(1, n);
    smt.modify(1, n, { 1 });
    for (int q = read(); q--; ) {
        int l = read(), r = read(), op = read();
        smt.modify(l, r, { op - 1 });
        printf("%d\n", smt.query(1, n).sum);
    }
}

SMT2.4 区间赋值、区间加，区间最值及其个数

struct mark {
    int asn{ -1 };  // 赋值标记
    int add{ 0 };   // 加法标记
    void apply(const mark& o, int s)& {
        // 先赋值再加法
        if (~o.asn) {
            asn = o.asn;
            add = 0;
        }
        add += o.add;
    }
};

struct info {
    int mn{ 0 };  // 最小值
    int tot{ 0 }; // 最小值的个数
    void apply(const mark& o, int s)& {
        if (~o.asn) mn = o.asn;
        mn += o.add;
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        if (l.mn < r.mn) return l;
        if (l.mn > r.mn) return r;
        return { l.mn, l.tot + r.tot };
    }
};

例 1 给定$n$ 个点、$n$ 条双向边的环。有$m$ 对点对$a_i,b_i$，要求删掉尽可能多的边，使得删完后，每对$a_i,b_i$ 仍联通。求出剩余边数的最小值。(CF1996G. Penacony)

struct mark {
    int add{ 0 };   // 加法标记
    void apply(const mark& o, int s)& {
        add += o.add;
    }
};

struct info {
    int mn{ 0 };  // 最小值
    int tot{ 1 }; // 最小值的个数
    void apply(const mark& o, int s)& {
        mn += o.add;
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        if (l.mn < r.mn) return l;
        if (l.mn > r.mn) return r;
        return { l.mn, l.tot + r.tot };
    }
};

SMT<info, mark> smt;
void eachT() {
    int n = read(), m = read();

    smt.init(1, n << 1);

    vector<int> t(n << 1 | 1);
    smt.build(t);  // 先把叶子的tot设为1

    vector<int> a(m), b(m);
    vector<vector<int>> pos(n << 1 | 1);
    for (int i = 0; i < m; ++i) {
        a[i] = read(), b[i] = read();
        if (a[i] > b[i]) swap(a[i], b[i]);
        smt.modify(a[i], b[i] - 1, { 1 });
        pos[a[i]].push_back(i);
    }

    int ans = 0;
    for (int j = 1; j <= n; ++j) {
        auto res = smt.query(j, j + n - 1);
        ans = max(ans, (res.mn == 0) * res.tot);
        for (auto& i : pos[j]) {
            smt.modify(a[i], b[i] - 1, { -1 });
            swap(a[i], b[i]);
            b[i] += n;
            smt.modify(a[i], b[i] - 1, { 1 });
            pos[a[i]].push_back(i);
        }
    }

    printf("%d\n", n - ans);
}

SMT.3 线段树二分

对于朴素二分，每次 check 需查询单点前缀和，一次询问复杂度$\Theta(\log^{2}n)$；而线段树的分治结构 合并二分和查询的过程，实现$\Theta(\log n)$ 的复杂度。

例 1 给定一个长度为$n$ 的序列$a_i\ (1\leqslant i\leqslant n)$，参数$B$，询问数$q$。每一次询问首先给出两个整数$c$ 和$x$，表示将序列的第$c$ 个数字永久地修改为$x$，然后你需要按如下规则输出一个实数：

1. 如果不存在某一个前缀平均值不低于$B$，则输出整体平均值；
2. 否则，输出第一个不低于$B$ 的前缀平均值。

其中，序列的第$k$ 个前缀平均值定义为$s_k=\dfrac1k\sum\limits_{i=1}^{k}a_i$，整体平均值为$s_n$。

数据范围：$1 \leqslant n \leqslant 5 \times 10^5,\quad1 \leqslant q \leqslant 10^5,\quad0 \leqslant a_i,x,B \leqslant 10^9,\quad1 \leqslant c \leqslant n$(VJsum1F. abc292Ex - Rating Estimator)

思路 将所有数减去$B$，前缀平均值$\geqslant B$ 转化为前缀和$\geqslant 0$，需要找到第一个$\geqslant 0$ 的前缀。（很经典的分式化整式，回忆 洛谷 P1419 寻找段落）

线段树维护（下标，前缀和序列区间最大值），二分求解，对于某个节点$p$，如果在左儿子对应的区间上找到了一个区间最大值$\geqslant 0$ 的，那答案在左儿子，否则在右儿子上找$\geqslant 0$ 的，如果都找不到，就说明所求不存在。只有单点修改，对于前缀和序列来说，就是进行了一次 区间加。（题设没有区间修改，间接证明了这种方法的合理性）

时间复杂度$\Theta((n+q)\log n)$，空间$\Theta(n)$。

struct mark {
    ll add{ 0 };
    void apply(const mark& d, int s)& {
        add += d.add;
    }
};

struct info {
    ll mx{ (ll)-1e18};
    void apply(const mark& d, int s)& {
        mx += d.add;
    }
    void apply(const info& o)& {
        *this = o;
    }
    friend info operator + (const info& l, const info& r) {
        return { max(l.mx, r.mx) };
    }
};

void eachT() {
    int n, B, q;
    cin >> n >> B >> q;

    SMT<info, mark> smt;
    smt.init(0, n);

    vector<ll> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] -= B;
    }

    vector<info> pre(n);
    pre[0].mx = a[0];
    for (int i = 0; i < n; ++i) {
        if (i) pre[i].mx = pre[i - 1].mx + a[i];
    }
    smt.build(pre);

    while (q--) {
        int c, x;
        cin >> c >> x;
        c--;
        x -= B;

        smt.modify(c, n, { x - a[c] });
        a[c] = x;
        
        int pos = smt.findL([&](const auto& p) {
            return p.mx >= 0;
        });
        if (pos == inf) pos = n - 1;
        printf("%.15lf\n", 1.0 * smt.query(pos, pos + 1).mx / (pos + 1) + B);
    }
}

例 2 CF2000H. Ksyusha and the Loaded Set

struct mark {
    int asn{ -1 };
    void apply(const mark& o, int s)& {
        if (~o.asn) asn = o.asn;
    }
};

struct info {
    int mx{ 0 };
    void apply(const mark& o, int s)& {
        if (~o.asn) mx = o.asn;
    }
    void apply(const info& o, int s)& {
        *this = o;
    };
    friend info operator + (const info& l, const info& r) {
        return { max(l.mx, r.mx) };
    }
};

SMT<info, mark> smt;
void eachT() {
    int n = read();
    int L = 0, R = 2e6 + 8;

    smt.init(L, R);

    set<int> s;
    s.insert(L), s.insert(R);
    int lst = L, now = 0;
    for (int i = 1; i <= n; ++i) {
        now = read();
        smt.modify(lst, lst, { now - lst - 1 });
        s.insert(now);
        lst = now;
    }

    int q = read();
    while (q--) {
        char c; do c = getchar(); while (c != '-' && c != '?' && c != '+');
        int x = read();

        if (c == '+') {
            s.insert(x);
            auto it = s.find(x);
            int l = *prev(it), r = *next(it);
            smt.modify(l, l, { x - l - 1 });
            smt.modify(x, x, { r - x - 1 });
        }
        else if (c == '-') {
            auto it = s.find(x);
            int l = *prev(it), r = *next(it);
            s.erase(x);
            smt.modify(l, l, { r - l - 1 });
            smt.modify(x, x, { 0 });
        }
        else {
            int res = smt.findL([&](const auto& p) {
                return p.mx >= x;
            });
            if (res == R + 1) res = *next(s.rbegin());
            printf("%d%c", res + 1, " \n"[q == 0]);
        }
    }
}

例 3 给定序列$a$ 和序列$b$，长度均为$n$。问有多少组$(l,r)$，满足$1 \leqslant l \leqslant r \leqslant n$ 且

$$\max\limits_{l \leqslant i \leqslant r}\lbrace a_{i} \rbrace = \min\limits_{l \leqslant i \leqslant r}\lbrace b_{i} \rbrace$$

数据范围：$n \leqslant 2\times 10^5$，$|a_i|,|b_i| \leqslant 10^9$。(CF689D - Friends and Subsequences)

思路 固定$l$，计算满足条件的$r$ 的个数，注意到$\max\limits_{l \leqslant i \leqslant p_{1}}\lbrace a_{i} \rbrace$ 是关于$p_{1}$ 单调增的，$\min\limits_{l \leqslant i \leqslant p_{1}}\lbrace b_{i} \rbrace$ 是关于$p_{2}$ 单调减的，因此必然存在一组$p_{1},p_{2}$，使得答案在$[p_{1},p_{2})$ 之间，具体的，

• $p_{1}$ 为满足$\max\limits_{l \leqslant i \leqslant p_{1}}\lbrace a_{i} \rbrace \geqslant \min\limits_{l \leqslant i \leqslant p_{1}}\lbrace b_{i} \rbrace$ 的最小的下标；
• $p_{2}$ 为满足$\max\limits_{l \leqslant i \leqslant p_{2}}\lbrace a_{i} \rbrace > \min\limits_{l \leqslant i \leqslant p_{2}}\lbrace b_{i} \rbrace$ 的最小的下标，也即$p_{2}-1$ 为满足$\max\limits_{l \leqslant i \leqslant p_{2}-1}\lbrace a_{i} \rbrace \leqslant \min\limits_{l \leqslant i \leqslant p_{2}-1}\lbrace b_{i} \rbrace$ 的最大的下标。

用 ST 表二分或线段树二分实现，虽然不涉及修改，但线段树二分能省去一个$\log$。

struct mark {
    void apply(const mark& d, int s) {}
};

struct info {
    int amx{ 0 };
    int bmn{ 0 };
    void apply(const mark& d, int s) {}
    void apply(const info& d, int s) {
        *this = d;
    };
    friend info operator + (const info& l, const info& r) {
        return { max(l.amx, r.amx), min(l.bmn, r.bmn) };
    }
};

void eachT() {
    int n = read();

    SMT<info, mark> smt;
    smt.init(1, n);

    vector<info> a(n + 1);
    for (int i = 1; i <= n; ++i) a[i].amx = read();
    for (int i = 1; i <= n; ++i) a[i].bmn = read();
    smt.build(a);

    ll res = 0;
    for (int i = 1; i <= n; ++i) {
        int mx = -0x3f3f3f3f, mn = 0x3f3f3f3f;
        int p1 = smt.findL(i, n, [&](const auto& p) {
            // 找满足max{a[i~p]} >= min{b[i~p]}的最小p
            if (max(mx, p.amx) >= min(mn, p.bmn)) return true;
            mx = max(mx, p.amx);
            mn = min(mn, p.bmn);
            return false;
        });

        mx = -0x3f3f3f3f, mn = 0x3f3f3f3f;
        int p2 = smt.findL(i, n, [&](const auto& p) {
            // 找满足max{a[i~p]} > min{b[i~p]}的最小p
            if (max(mx, p.amx) > min(mn, p.bmn)) return true;
            mx = max(mx, p.amx);
            mn = min(mn, p.bmn);
            return false;
        });

        res += p2 - p1;
    }
    printf("%lld\n", res);
}

例 4 有$n$ 个商店，去第$i$个商店购买物品需要花费$a_{i}$ 元，保证$a$ 序列为非增序列。两种操作：

1. 对所有的$i\in[1, x]$，令$a_{i} \leftarrow \max\lbrace a_{i}, y \rbrace$；
2. 你有$y$ 元钱，从编号为$x$ 的商店出发，依次遍历所有商店直至到$n$ 号商店为止，如果能购买当前商店的物品则购买。问你能买多少物品。

数据范围：$0\leqslant n,q\leqslant 20000,\quad 0\leqslant a_{i},y\leqslant 10^9$。(VJsum1G. CF1440E. Greedy Shopping)

思路 题给初始序列单调不增，进一步考察，序列在任意时刻都 单调不增。（题目的每个条件都是有用的）

操作 1，对$[1, x]$ 区间赋值。由于序列单调不增，因此存在一个分界线，它左边都不需要修改，右边都需要修改。这个分界线由 二分 获得，具体来说，

• 如果当前区间的最小值$>y$，则不需要修改；
• 如果当前区间的最大值$<y$，则应当修改；
• 否则无法判断，继续递归。

操作 2，进行询问区间$[x, n]$。因为购买的区间不一定连续，不能直接用线段树二分返回某个特定的下标，而是应当将所有满足条件的记录下来，具体来说，

• 如果当前区间的最小值$<y$，则一个都买不起，返回；
• 如果当前区间的和$\geqslant y$，全买，买了区间长度个，花费区间和的费用，更新这两个数值，返回；
• 否则买其中一部分，继续递归。

struct SMT {
    int pcnt;
    static int L, R, rt;
    struct info {
        ll sum;     // 区间和
        int mn, mx; // 区间最值
        ll mrk;     // 懒标记
        int len;    // 区间长度
        int l, r;
    } t[N << 2];

    void init(int l, int r) {
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    // 在这两个函数中写需要维护的东西
    void push_up(info& p, info l, info r) {
        p.sum = l.sum + r.sum;
        p.mx = max(l.mx, r.mx);
        p.mn = min(l.mn, r.mn);
        p.len = l.len + r.len;
    }
    void push_down(info& p, ll d, int l) {
        p.sum = d * l;
        p.mx = p.mn = p.mrk = d;
        p.len = l;
    }

    void push_up(int p) { return push_up(t[p], t[ls], t[rs]); }
    void push_down(int p, int l) {
        if (!t[p].mrk) return;
        if (!ls) ls = ++pcnt, init(ls);
        push_down(t[ls], t[p].mrk, l - (l >> 1));
        if (!rs) rs = ++pcnt, init(rs);
        push_down(t[rs], t[p].mrk, l >> 1);
        t[p].mrk = 0;
    }

    void build(auto& a, int& p = rt, int cl = L, int cr = R) {
        if (!p) p = ++pcnt, init(p);
        if (cl == cr) return push_down(p, a[cl], 1);
        build(a, lson), build(a, rson);
        return push_up(p);
    }

    void modify(int l, int r, int d, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) {
            if (t[p].mn >= d) return;
            if (t[p].mx < d)  return push_down(t[p], d, len);
        }
        push_down(p, len);
        if (l <= mid) modify(l, r, d, lson);
        if (mid < r)  modify(l, r, d, rson);
        return push_up(p);
    }

    // 在区间[l,r]中找到满足f的全部位置
    void findin(int l, int r, auto&& f, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r && !f(t[p])) return;  // 在当前区间内且不合题意
        push_down(p, len);
        if (l <= mid) findin(l, r, f, lson);
        if (mid < r)  findin(l, r, f, rson);
        return push_up(p);
    }
};
int SMT::L, SMT::R, SMT::rt;
SMT smt;

void eachT() {
    int n = read(), m = read();

    smt.init(1, n);

    vector<int> arr(n + 1);
    for (int i = 1; i <= n; ++i) {
        arr[i] = read();
    }
    smt.build(arr);

    while (m--) {
        int op = read(), x = read(), y = read();
        if (op == 1) {
            smt.modify(1, x, y);
        }
        else {
            int res = 0;
            smt.findin(x, n, [&](const auto& p) {
                if (y < p.mn) return 0;        // 一个都买不起
                if (y >= p.sum) {
                    y -= p.sum, res += p.len;  // 全买了 买了cr-cl+1个，花费t[p].sum
                    return 0;
                }
                return 1;                       // 买部分 继续递归
            });
            printf("%d\n", res);
        }
    }
}

SMT.4 权值线段树

用线段树维护 桶，在$\Theta(\log v)$ 的时间内查询某个范围内的数出现的总次数、第$k$ 大数、前驱后继等。空间复杂度$\Theta(q\log v)$。

权值线段树无需懒标记 mrk，由于是单点更新，也无需 push_down 和 push_up 函数，而是递归到底、区间相加，代码相对于普通线段树更短，这也是较 平衡树 的优势，但是当值域较大、询问较多时空间占用较大。

int countl(int x) { return query(L, x - 1).val; }
int countg(int x) { return query(x + 1, R).val; }
int rankof(int x) { return countl(x) + 1; }  // 排名 (比当前数小的数的个数+1)
int kthnum(int k, int p = rt, int cl = L, int cr = R) {  // 指定排名的数
    if (cl == cr) return cl;
    if (k <= t[ls].val) return kthnum(k, lson);  // 往左搜
    else return kthnum(k - t[ls].val, rson);  // 往右搜
}
int prenum(int x) { return kthnum(countl(x)); }  // 前驱
int sucnum(int x) { return kthnum(t[rt].val - countg(x) + 1); }  // 后继

例 1 两个人用石头博弈，共$n$ 种石头，每种石头有两块，价值分别为$a_{i},\ b_{i}$。A 和 B 按照 ABBAABBAABBA 的顺序依次购买一块石头。

规定：

• 每种石头每个人只能买一次，即对于每种石头，要么买第一块，要么买第二块；
• 对于每种石头，只有当第一块被买走才能买第二块。

两个人都最小化买齐$n$ 种石头的花费，求 A 的最小花费。按顺序给出$m$ 次永久修改，每次修改给出这个答案。(VJsum1A & 2022 ICPC 沈阳 I. Quartz Collection)

当时完美地解决了 Step1，但是不会线段树。

Step1 假博弈真贪心

这部分比较简单。

称$a_{i} - b_{i}$ 为 代价，两个人均希望代价尽可能小，故按代价从小到大排序。

• 对于$a_{i} \leqslant b_{i}$ 的部分，两人均优先买第一块，于是按购买顺序依次买第一块，即 A 买$a_{0}$，B 买$a_{1}$，B 买$a_{2}$，A 买$a_{3}$…… A 买到的第一块石头的下标$i,\ i \equiv 0, 3 \pmod 4$。
• 对于$a_{i} > b_{i}$ 的部分，两人均避免买第一块，于是能买第二块就买第二块，否则选择代价最小的第一块购买。考虑$a_{i} \leqslant b_{i}$ 都买完后轮到了谁：
  • 若$a_{i} \leqslant b_{i}$ 的数量为奇数，设有$m$ 个。
    这部分的购买情况是 ABB / AAB / BAABBAA… 或 ABBAA / BBAAB / BAABBAA…，无论哪种情况，$a_{i} \leqslant b_{i}$ 都买完后都轮到了 B，且为 BAABBAA。
    于是 B 先买代价最小的$a_{m}$，然后 A 买对应的第二块$b_{m}$，再买$a_{m+1}$，B 买$b_{m+1},\ a_{m+2}$……
    A 买到的第一块石头的下标$i,\ i-m \equiv 1, 3 \pmod 4$。
  • 若$a_{i} \leqslant b_{i}$ 的数量为偶数，类似地分析，ABBA / ABBA / ABBAABB，$a_{i} \leqslant b_{i}$ 都买完后都轮到了 A，于是 A 买到的第一块石头的下标$i,\ i-m \equiv 0, 2 \pmod 4$。
    将上面两部分的结果相加，再加上$\sum b_{i}$，即是答案。

Step2 线段树

首先明确，因涉及排名，我们需要建立 权值线段树，具体地，以代价$a_{i} - b_{i}$ 建立权值线段树。

维护什么？

• 每个数出现的次数 siz，常规的权值线段树。
• 排名为$i$ 的数的总和，记为 sum[4]，其中 tr[p].sum[k] 表示节点$p$ 对应的区间$[l,r]$ 中，排名为$i,\ i \equiv k \pmod 4$ 的数的总和。

如何更新？ 考察两个方面，即 push_up 和对叶的操作。

• push_up：
  • 对于 siz，常规操作，tr[p].siz = tr[ls].siz + tr[rs].siz；
  • 对于 sum[4]，感性地理解一下，不难得到 tr[p].sum[i] = tr[ls].sum[i] + tr[rs].sum[i-m]，即左节点排名为$i,\ i \equiv k$ 的总和加上右节点排名为$i,\ i-m \equiv k$ 的总和相加，其中$m$ 是左节点的数的数量。
• 对叶的操作：
  • 对于 siz，常规操作，tr[p].siz += d；
  • 对于 sum[4]，因为叶只有一个数，那排名就是 0，容易想到 tr[p].val[0] += x * d，但这样是错误的，原因是 相同的数也应当要排名，具体写法参见代码。

如何查询？

• 注意到查询只需要查询根节点$\mathrm{rt}$，所以只需写一个简略的函数：置值域为$[-10^{5},10^{5}]$，这样，根节点的左儿子即是$a_{i} - b_{i} \leqslant 0$，右儿子即是$a_{i} - b_{i} > 0$，天然地将树分成了两块。根据 Step1 的推断，对于左儿子，查询 sum[0] + sum[3]，对于右儿子，视左儿子的节点个数分情况讨论，再将两者求和即可。

struct SMT {
    int pcnt;
    static int L, R, rt;
    struct info {
        int siz;
        ll sum[4];
        int l, r;
    } t[N << 2];

    void init(int l, int r) {
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, {0}, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(int& p = rt) {
        t[p].siz = t[ls].siz + t[rs].siz;
        for (int i = 0; i < 4; ++i) {
            t[p].sum[i] = t[ls].sum[i] + t[rs].sum[((i - t[ls].siz) % 4 + 4) % 4];
        }
    }

    void modify(int x, int d, int& p = rt, int cl = L, int cr = R) {
        if (!p) p = ++pcnt, init(p);
        if (cl == cr) {  // 叶子的处理
            // WA: t[p].sum[0] += x * d;
            if (d == 1) t[p].sum[t[p].siz % 4] += x;
            else  t[p].sum[(t[p].siz - 1) % 4] -= x;
            t[p].siz += d;
            return;
        }
        if (x <= mid) modify(x, d, lson);
        if (x > mid)  modify(x, d, rson);
        return push_up(p);
    }

    ll query(int& p = rt) {
        ll sum1 = t[ls].sum[0] + t[ls].sum[3];  // 左节点a_i-b_i<0的情形
        ll sum2 = t[ls].siz & 1
            ? t[rs].sum[1] + t[rs].sum[3]
            : t[rs].sum[0] + t[rs].sum[2];      // 右节点a_i-b_i>0的情形 需分两种情况讨论
        return sum1 + sum2;
    }
};
int SMT::L, SMT::R, SMT::rt;
SMT smt;

void eachT() {
    int n = read(), m = read();

    smt.init(-1e5, 1e5);

    vector<int> a(n + 1), b(n + 1);
    ll sum0 = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = read(), b[i] = read();
        sum0 += b[i];
        smt.modify(a[i] - b[i], 1);
    }
    printf("%lld\n", sum0 + smt.query());

    while (m--) {
        int p = read();
        sum0 -= b[p], smt.modify(a[p] - b[p], -1);
        a[p] = read(), b[p] = read();
        sum0 += b[p], smt.modify(a[p] - b[p], 1);
        printf("%lld\n", sum0 + smt.query());
    }
}

例 2 2023 ICPC 沈阳 K. Maximum Rating

struct mark {
    int add{ 0 };
    void apply(const mark& self)& {
        add += p.add;
    }
};

struct info {
    ll sum{ 0 };
    int cnt{ 0 };
    void apply(const mark& self)& {
        sum += p.add * L;
        cnt += p.add;
    }
    void apply(const info& p)& {
        *this = p;
    }
    friend info operator + (const info& l, const info& r) {
        return { l.sum + r.sum, l.cnt + r.cnt };
    }
};

void eachT() {
    int n, q;
    cin >> n >> q;

    ll sum = 0;   // 负数之和
    SMT<info, mark> smt;
    smt.init(1, inf + 1);

    auto modify = [&](int val, int d) {
        if (val < 0) sum += val * d;
        if (val > 0) smt.modify(val, val + 1, { d });
    };

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        modify(a[i], 1);
    }

    while (q--) {
        int p, val;
        cin >> p >> val;
        p--;

        modify(a[p], -1);
        a[p] = val;
        modify(a[p], 1);

        ll need = -sum;
        p = smt.findL([&](const info& p) {
            if (p.sum <= need) {
                need -= p.sum;
                return false;
            }
            return true;
        });

        int res = 1;
        res += smt.query(0, p).cnt;
        res += min(smt.query(p, p + 1).cnt, int(need / p));  // WA: need - smt.query(0, p).sum 因为在二分中已经减去了
        cout << res << '\n';
    }
}

SMT.5 线段树合并

维护 从若干子结构合并成大结构 的合并过程中所有出现过的结构的完整信息，如 并查集、树上每个节点的 子树信息 等。时空复杂度与开的总点数相同，为线性对数。

动态开点，rt[p] 表示节点$p$ 所在树的根节点 unix。递归地将两棵线段树的节点信息对应合并：

// 将树上节点x,y合并到节点z
int merge(int x, int y, int cl = L, int cr = R) {
    if (!x || !y) return x | y;                  // 一方为空 递归到叶 返回非空的那个节点
    int z = ++pcnt;
    if (cl == cr) return /* 合并叶子节点x,y 将y的信息传递给x */, z;
    push_down(x), push_down(y);
    tr[z].ls = merge(tr[x].ls, tr[y].ls, cl, mid);      // x的左节点和y的左节点合并为z的左节点 
    tr[z].rs = merge(tr[x].rs, tr[y].rs, mid + 1, cr);  // x的右节点和y的右节点合并为z的右节点 
    push_up(z);                                               // 更新当前节点信息
    return z;
}

void eachT() {
    L = 1, R = n, pcnt = 0;
    for (int i = 1; i <= n; ++i) {
        rt[i] = ++pcnt;          // 建立根节点
        modify(num, 1, rt[i]);   // 将num插入权值线段树i 指定树的根是rt[i]
    }  // 建n颗权值线段树
    for (int q = read(); q--; ) {
        rt[x] = rt[y] = merge(rt[x], rt[y]);     // 从树根开始合并x,y 并将x和y的根设置为新根
    }
}

上面的写法保留原来两棵线段树的信息，创建了一棵新树，因此需要额外的一倍空间。如果不要求保留原来的信息，优先选择直接把第二棵树的信息加到第一棵树上，这不需要新建节点，但会毁掉原先的两棵树：

// 将树上节点x,y合并到节点x
int merge(int x, int y, int cl = L, int cr = R) {
    if (!x || !y) return x | y;      // 一方为空 递归到叶 返回非空的那个节点
    if (cl == cr) return /* 合并叶子节点x,y 将y的信息传递给x */, x;
    push_down(x), push_down(y);
    tr[x].ls = merge(tr[x].ls, tr[y].ls, cl, mid);      // x的左节点和y的左节点合并为x的左节点 
    tr[x].rs = merge(tr[x].rs, tr[y].rs, mid + 1, cr);  // x的右节点和y的右节点合并为x的右节点 
    push_up(x);                                               // 更新当前节点信息
    return x;
}

不可以把自己和自己合并！

SMT5.1 区间加，区间积，区间删除，并查集维护连通性

题意 请用某种数据结构维护一个图，您的代码应当能够实现：（以下节点$a$ 指节点编号为$a$ 的节点）

1. 新建一个节点，权值为$a$，若当前有$n$ 个节点，则节点编号为$n+1$；
2. 连接两个节点$a,b$；
3. 将一个节点$a$ 所属于的联通块内权值小于$b$ 的所有节点权值变成$b$；
4. 将一个节点$a$ 所属于的联通块内权值大于$b$ 的所有节点权值变成$b$；
5. 询问一个节点$a$ 所属于的联通块内的第$b$ 小的权值是多少；
6. 询问一个节点$a$ 所属联通块内所有节点权值之积与另一个节点$b$ 所属联通块内所有节点权值之积的大小，若$a$ 所属联通块内所有节点权值之积大于$b$ 所属联通块内所有节点权值之积，输出$1$，否则为$0$；
7. 询问$a$ 所在联通块内节点的数量。

数据范围：$0\leqslant q\leqslant 400000, \quad 1\leqslant\mathrm{opt}\leqslant7, \quad 0\leqslant a,b\leqslant 10^9$。(VJsum1D - BZOJ4399. 魔法少女LJJ)

思路 用并查集维护连通性。为了查询每个连通块里的第$k$ 大，自然想到权值线段树，每个联通块都需要维护一个权值线段树。在并查集合并联通块的同时合并线段树。具体地，

• 操作 1, 2, 7 是基础写法。
• 操作 3, 4：以 3 为例，把大于$b$ 的变成$b$ 等价于把大于$b$ 的都删除，即区间赋值，再插入这么多个$b$，即权值线段树的插入，为了知道需要插入多少个，需先查询这段区间数的数量 siz。
• 操作 5：权值线段树的 kthnum 模板函数。
• 操作 6：需维护区间积，显然这个积会爆 LL，稍作转换，维护区间$\log$ 和。

struct SMT {
    int pcnt;
    static int L, R;
    struct info {
        int siz;
        int mrk;    // 是否删除
        double mul;
        int l, r;
    } t[N << 6];

    void init(int l, int r) {
        pcnt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, -1, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(info& p, info l, info r) {
        p.siz = l.siz + r.siz;
        p.mul = l.mul + r.mul;
    }
    void push_down(info& p, int d, int l) {
        p.siz = d, p.mul = d * log2(l);
        p.mrk = d;
    }

    void push_up(int& p) { push_up(t[p], t[ls], t[rs]); }
    void push_down(int p, int l) {
        if (t[p].mrk == -1) return;
        push_down(t[ls], t[p].mrk, l - (l >> 1));
        push_down(t[rs], t[p].mrk, l >> 1);
        t[p].mrk = -1;
    }

    void modify(int x, int d, int& p, int cl = L, int cr = R) {
        if (!p) p = ++pcnt, init(p);
        if (cl == cr) return t[p].siz += d, t[p].mul += d * log2(x), void();
        push_down(p, len);
        if (x <= mid) modify(x, d, lson);
        else modify(x, d, rson);
        return push_up(p);
    }

    void clear(int l, int r, int& p, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return push_down(t[p], 0, len);
        push_down(p, len);
        if (l <= mid) clear(l, r, lson);
        if (mid < r)  clear(l, r, rson);
        return push_up(p);
    }

    info query(int l, int r, int& p, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p];
        push_down(p, len);
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        info res;
        push_up(res, query(l, r, lson), query(l, r, rson));
        return res;
    }

    int kthnum(int k, int& p, int cl = L, int cr = R) {
        if (cl == cr) return cl;
        push_down(p, len);
        if (k <= t[ls].siz) return kthnum(k, lson);
        else return kthnum(k - t[ls].siz, rson);
    }

    int merge(int q, int p, int cl = L, int cr = R) {
        if (!q || !p) return q | p;
        if (cl == cr) return push_up(t[q], t[q], t[p]), q;
        push_down(q, len), push_down(p, len);
        t[q].l = merge(t[q].l, lson);
        t[q].r = merge(t[q].r, rson);
        return push_up(q), q;
    }
};
int SMT::L, SMT::R;
SMT smt;

struct DSU {
    vector<int> p, siz;

    DSU() {}
    DSU(int n) {
        init(n);
    }

    void init(int n) {
        p.resize(n + 1);
        iota(p.begin(), p.end(), 0);
        siz.assign(n + 1, 1);
    }

    int find(int x) {
        while (x != p[x]) x = p[x] = p[p[x]]; // 路径压缩
        return p[x];
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    bool uno(int x, int y) {
        x = find(x), y = find(y);
        if (same(x, y)) return false;
        siz[x] += siz[y];
        p[y] = x;
        return true;
    }

    int size(int x) {
        return siz[find(x)];
    }
};

int rt[N];
void eachT() {
    int q = read(), n = 0;

    DSU dsu(q);

    int L = 1, R = 1e9;
    smt.init(L, R);

    while (q--) {
        int op = read();
        if (op == 1) {  // 新建
            int a = read();
            smt.modify(a, 1, rt[++n]);  // 将1个a插入新节点的权值线段树
        }
        else if (op == 2) {  // 连接
            int a = dsu.find(read()), b = dsu.find(read());
            if (a == b) continue;  // 不能合并自己
            rt[a] = rt[b] = smt.merge(rt[a], rt[b]);
            dsu.uno(a, b);
        }
        else if (op == 3) {  // 把小于b的变成b
            int a = dsu.find(read()), b = read();
            int num = smt.query(L, b, rt[a]).siz;  // 需要删除L~b所有的数 共num个
            smt.clear(L, b, rt[a]);                // 删除L~b
            smt.modify(b, num, rt[a]);             // 将num个b插入权值线段树n
        }
        else if (op == 4) {  // 把大于b的变成b
            int a = dsu.find(read()), b = read();
            int num = smt.query(b, R, rt[a]).siz;
            smt.clear(b, R, rt[a]);
            smt.modify(b, num, rt[a]);
        }
        else if (op == 5) {  // 求a的第b小
            int a = dsu.find(read()), b = read();
            printf("%d\n", smt.kthnum(b, rt[a]));
        }
        else if (op == 6) {  // 比较a和b的乘积的大小
            int a = dsu.find(read()), b = dsu.find(read());
            printf("%d\n", smt.query(L, R, rt[a]).mul > smt.query(L, R, rt[b]).mul);
        }
        else if (op == 7) {  // 求a的siz
            int a = dsu.find(read());
            printf("%d\n", smt.query(L, R, rt[a]).siz);
        }
    }
}

SMT.6 线段树上树

[[…/图论 - 树/树 05 - 树的重链剖分、树上启发式合并|树 05 - 树的重链剖分、树上启发式合并]]
[[…/图论 - 树/树 06 - 树与线段树合并|树 06 - 树与线段树合并]]

SMT.7 线段树优化建图

[[…/图论/图论技巧集#转化为线段树——区间连边|图论习题集]]

SMT.8 线段树与扫描线

求所有$W\times H$ 格点矩形区域（不含边框）内，点权之和最大值。(VJsum7F - 窗口的星星)

将点$(x,y)$ 扩展为$(x+W-1,y+H-1)$ 的矩形，矩形重叠则点权相加，即是求平面内权值最大的区域。类似于扫描线，但是求区间最大值，而不是区间不同数的个数。

/// ----------------扫描线----------------
struct RECT {
    int x, y1, y2, op;
    bool operator < (const RECT& yall) const {
        return x == yall.x ? op > yall.op : x < yall.x;
    }
};
vector<RECT> rect;  // {x, y1, y2, op}
vector<int> yall;
void add(int x1, int x2, int y1, int y2, int d = 1) {
    yall.push_back(y1);
    yall.push_back(y2);
    rect.push_back({ x1, y1, y2, d });
    rect.push_back({ x2, y1, y2, -d });
    return;
}

/// ----------------线段树----------------
struct SMT {
    int pcnt;
    static int L, R, rt;
    struct info {
        ll mx, mrk;
        int l, r;
    } t[N << 6];

    void init(int l, int r) {
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    // 在这两个函数中写需要维护的东西
    void push_up(info& p, info l, info r) {
        p.mx = max(l.mx, r.mx);
    }
    void push_down(info& p, ll d, int l) {
        p.mx += d;
        p.mrk += d;
    }

    // 下传与回溯
    void push_up(int& p) { push_up(t[p], t[ls], t[rs]); }
    void push_down(int p, int l) {
        if (l <= 1) return;
        if (!ls) ls = ++pcnt, init(ls);
        push_down(t[ls], t[p].mrk, l - (l >> 1));
        if (!rs) rs = ++pcnt, init(rs);
        push_down(t[rs], t[p].mrk, l >> 1);
        t[p].mrk = 0;
    }

    // 区间[l,r]加d
    void modify(int l, int r, ll d, int& p = rt, int cl = L, int cr = R) {
        if (!p) p = ++pcnt, init(p);
        if (l <= cl && cr <= r) return push_down(t[p], d, len);
        push_down(p, len);
        if (l <= mid) modify(l, r, d, lson);
        if (mid < r)  modify(l, r, d, rson);
        return push_up(p);
    }

    // 查询[l,r]
    info query(int l, int r, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p];
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        info res;
        push_up(res, query(l, r, lson), query(l, r, rson));
        return res;
    }

};
int SMT::L, SMT::R, SMT::rt;
SMT smt;

/// ----------------主函数----------------
void eachT() {
    int n = read(), W = read(), H = read();

    smt.init(-1e9, 1e9);

    for (int i = 0; i < n; ++i) {
        int x = read(), y = read(), d = read();
        add(x, x + W - 1, y, y + H - 1, d);
    }
    sort(rect.begin(), rect.end());
    sort(yall.begin(), yall.end());

    ll res = 0;
    for (auto& [x, y1, y2, op] : rect) {
        y1 = lower_bound(yall.begin(), yall.end(), y1) - yall.begin();
        y2 = lower_bound(yall.begin(), yall.end(), y2) - yall.begin();

        res = max(res, smt.query(-1e9, 1e9).mx);
        smt.modify(y1, y2, op);
    }

    printf("%lld\n", res);

    rect.clear();
    yall.clear();
}

SMT8.1 区间加，区间数的种类（标记永久化／拖拖）

拖拖是一个扫地机器猫。给定一个由$n$ 个移动操作组成的序列，第$i$ 个移动操作由方向$d_i$ 和距离$a_i$ 组成。根据给定的拖拖移动操作，计算清扫的总面积。洛谷 10096

数据范围：$1 \leqslant k \leqslant 10^4$，$1 \leqslant n \leqslant 10^5$，$1 \leqslant a_i \leqslant 10^9$。

/// ----------------扫描线----------------
struct RECT {
    ll x, y1, y2;
    int op;
    bool operator < (const RECT& yall) const {
        return x == yall.x ? op > yall.op : x < yall.x;
    }
};
vector<RECT> rect;  // {x, y1, y2, op}
vector<ll> yall;
void add(ll x1, ll x2, ll y1, ll y2, int d = 1) {
    yall.push_back(y1);
    yall.push_back(y2);
    rect.push_back({ x1, y1, y2, d });
    rect.push_back({ x2, y1, y2, -d });
}

/// ----------------线段树----------------
struct SMT {
    int pcnt;
    static int L, R, rt;
    struct info {
        ll typ, mrk;
        int l, r;
    } t[N << 6];

    void init(int l, int r) {
        pcnt = 0, rt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void push_up(int p, int cl, int cr) {
        if (t[p].mrk) t[p].typ = yall[cr + 1] - yall[cl]; // 标记永久化 yall是离散化后的数组
        else t[p].typ = t[ls].typ + t[rs].typ;
    }

    void modify(int l, int r, int d, int& p = rt, int cl = L, int cr = R) {
        if (!p) p = ++pcnt;
        if (l <= cl && cr <= r) return t[p].mrk += d, push_up(p, cl, cr);
        if (l <= mid) modify(l, r, d, lson);
        if (mid < r)  modify(l, r, d, rson);
        return push_up(p, cl, cr);
    }

    ll query(int l = L, int r = R, int& p = rt, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p].typ;
        if (r <= mid) return query(l, r, lson);
        if (mid < l)  return query(l, r, rson);
        return query(l, r, lson) + query(l, r, rson);
    }
};
int SMT::L, SMT::R, SMT::rt;
SMT smt;

void eachT() {
    int k = read(), n = read();

    smt.init(0, 2 * n);

    ll x = 0, y = 0;
    for (int i = 0; i < n; ++i) {
        char op; do op = getchar(); while (op != 'N' && op != 'S' && op != 'E' && op != 'W');
        int d = read();

        if (op == 'N') add(x, x + k, y, y + k + d), y += d;
        if (op == 'S') add(x, x + k, y - d, y + k), y -= d;
        if (op == 'E') add(x, x + k + d, y, y + k), x += d;
        if (op == 'W') add(x - d, x + k, y, y + k), x -= d;
    }
    sort(rect.begin(), rect.end());
    sort(yall.begin(), yall.end());

    ll res = 0, lst = 0;
    for (auto& [x, y1, y2, op] : rect) {
        y1 = lower_bound(yall.begin(), yall.end(), y1) - yall.begin();
        y2 = lower_bound(yall.begin(), yall.end(), y2) - yall.begin();
        res += (x - lst) * smt.query();
        lst = x;

        smt.modify(y1, y2 - 1, op);
    }

    printf("%lld\n", res);
}

SMT9. 可持久化线段树

int rt[N];
ll a[N];
int L, R, pcnt;
struct SMT {
    struct info {
        ll sum, mrk;
        int l, r;
    } t[N << 6];

    void init(int l, int r) {
        pcnt = 0;
        L = l, R = r;
    }

    void init(int p) {
        t[p] = { 0, 0, 0, 0 };
    }

#define ls t[p].l
#define rs t[p].r
#define mid ((cl+cr)>>1)
#define len (min(cr,r)-max(cl,l)+1)  // 不同于普通线段树的(cr-cl+1)
#define lson ls,cl,mid
#define rson rs,mid+1,cr

    void build(int& p, int cl = L, int cr = R) {
        p = ++pcnt, init(p);
        if (cl == cr) return t[p].sum = a[cl], void();
        build(lson), build(rson);
        t[p].sum = t[ls].sum + t[rs].sum;
        return;
    }

    void modify(int l, int r, ll d, int q, int& p, int cl = L, int cr = R) {
        t[p = ++pcnt] = t[q];   // 持久化须新建节点
        t[p].sum += d * len;    // 没有push_up 直接修改sum
        if (l <= cl && cr <= r) return t[p].mrk += d, void();
        if (l <= mid) modify(l, r, d, t[q].l, lson);
        if (mid < r)  modify(l, r, d, t[q].r, rson);
        return;    // 标记永久化不能push_up(p)
    }

    ll query(int l, int r, int& p, int cl = L, int cr = R) {
        if (l <= cl && cr <= r) return t[p].sum;
        ll res = t[p].mrk * len;   // 永久标记直接加上
        if (l <= mid) res += query(l, r, lson);
        if (mid < r)  res += query(l, r, rson);
        return res;   // 这里采用了老式写法
    }

    int kth(int k, int& q, int& p, int cl = L, int cr = R) {
        if (cl >= cr) return cl;
        int s = t[t[p].l].sum - t[t[q].l].sum;
        if (k <= s) return kth(k, t[q].l, lson);
        else return kth(k - s, t[q].r, rson);
    }
} smt;

SMT9.0 静态区间第 k 小

int main() {
    int n = read();
    
    smt.init(1, 2e5);
    smt.build(rt[0]);
    for (int i = 1; i <= n; ++i) {
        int x = read();
        smt.modify(x, x, 1, rt[i - 1], rt[i]);
    }

    for (int q = read(); q--; ) {
        int l = read(), r = read(), k = read();
        int ans = smt.kth(k, rt[l - 1], rt[r]);
        printf("%d\n", ans);
    }
}

SMT9.1 历史版本区间加，区间和

To the moon

int main() {
    int n = read(), q = read();

    smt.init(1, n);

    for (int i = 1; i <= n; ++i) {
        a[i] = read();
    }
    smt.build(rt[0]);

    int now = 0;
    while (q--) {
        char op = getchar();
        if (op == 'C') { // 区间修改 
            int l = read(), r = read(), d = read();
            ++now;
            smt.modify(l, r, d, rt[now - 1], rt[now]);
        }
        else if (op == 'Q') { // 查询当前版本 
            int l = read(), r = read();
            printf("%lld\n", smt.query(l, r, rt[now]));
        }
        else if (op == 'H') { // 查询历史版本
            int l = read(), r = read(), old = read();
            printf("%lld\n", smt.query(l, r, rt[old]));
        }
        else if (op == 'B') { // 版本回溯
            now = read();
        }
    }
}

SMT9.2 历史版本区间赋值，区间加

void modify(int l, int r, ll d, int q, int& p, int cl = L, int cr = R) {
    t[p = ++pcnt] = t[q];   // 持久化须新建节点
    t[p].sum = d * len;     // 没有push_up 直接修改sum
    if (l <= cl && cr <= r) return t[p].mrk = d, void();
    if (l <= mid) modify(l, r, d, t[q].l, lson);
    if (mid < r)  modify(l, r, d, t[q].r, rson);
    return;    // 标记永久化不能push_up(p)
}

凸包

问题 (插入直线, 询问最小值 7)
给定$n$ 条直线, 按顺序执行以下$q$ 个询问:
$a, b$：插入直线$y = ax + b$。
$p$：求最小的$y$ 使得$y = x \cdot p$。
问题可以转化为插入点$(a, b)$, 求$(- p, -1)$ 和其中某个点的最大点积。

假设没有插入操作:
答案一定是凸包上的点。分成上下两个凸包后，答案是凸的，可以通过二分得到答案。

二进制分组:
对于$n$ 个点, 根据二进制表示$n = 2^k_0 + 2^{k_1} + \cdots$, 分别维护$2^k$ 个点形成的凸包。插入新的点时增加 1 个点形成的凸包, 类似二进制进位加法, 当存在两个$2^k$ 个点形成凸包时, 合并成一个$2^{k+1}$ 个点形成凸包, 直到没有相同大小的凸包。插入均摊复杂度为$\Theta(\log n)$, 询问复杂度为$\Theta(\log^2 n)$。GCC 实现 list.sort 时使用二进制分组。对于 AC 自动机等不能在线插入的结构可以使用二进制分组实现在线插入。

李超线段树

问题 (插入线段, 询问最小值 9)
给定$n$ 条直线, 按顺序执行以下$q$ 个询问:
$l, r, a, b$：插入线段$y = ax + b$, 线段 x 轴区间为$[l, r)$.
$p$：求最小的$y$ 使得$y = x \cdot p$。

使用线段树的结构, 每个结点保存一条线段, 询问结果为单点和其所有祖先线段的最小值。
在结点插入线段时, 和原来线段比较, 至少有一条线段在其一半的区间完全在另一条线段下方, 将这条线段保存在结点中。
对另一条线段, 如果在其中一半可能比另一条线段小, 则递归插入该线段。
离散化询问的坐标, 插入复杂度为$\Theta(\log^2 n)$, 询问复杂度为$\Theta(\log n)$。

其他数据结构

• 有用的：带权并查集、Treap
• 没有用的：Splay 和 动态树、KD tr

分块、莫队

莫队 基于 分块，是一种解决区间查询等问题的 离线 算法，适用于能够在 $\Theta(1)$ 内将答案从 $[l,r]$ 转移到 $[l-1,r]$、$[l+1,r]$、$[l,r-1]$、$[l,r+1]$ 这四个与之紧邻的区间的答案的问题。时间复杂度$\Theta(n\sqrt{ n })$。

只需修改 add() 和 del() 函数。

例 询问区间颜色个数：

void eachT() {
    int n = read();

    vector<int> arr(n + 1);
    vector<int> alls;
    for (int i = 1; i <= n; ++i) {
        arr[i] = read();
        alls.push_back(arr[i]);
    }
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());
    for (int i = 1; i <= n; ++i) {
        arr[i] = lower_bound(alls.begin(), alls.end(), arr[i]) - alls.begin();
    }

    static int B = sqrt(n);
    struct QUE {
        int ql, qr, id;
        bool operator<(const QUE& b) const {
            return ql / B != b.ql / B ? ql < b.ql : (ql / B & 1 ? qr < b.qr : qr > b.qr);
        }
    };

    int q = read();
    vector<QUE> que(q);
    for (int i = 0; i < q; ++i) {
        que[i].ql = read(), que[i].qr = read();
        que[i].id = i;
    }
    sort(que.begin(), que.end());

    vector<int> cnt(n);
    int now = 0;
    auto add = [&](int p) {
        if (cnt[arr[p]] == 0) now++;
        cnt[arr[p]]++;
    };
    auto del = [&](int p) {
        cnt[arr[p]]--;
        if (cnt[arr[p]] == 0) now--;
    };

    int cl = 1, cr = 0;
    vector<int> res(q);
    for (auto& [ql, qr, id] : que) {
        while (cl > ql) add(--cl);
        while (cr < qr) add(++cr);
        while (cl < ql) del(cl++);
        while (cr > qr) del(cr--);
        res[id] = now;
    }

    for (int i = 0; i < q; ++i) {
        printf("%d\n", res[i]);
    }
}

例 询问区间每种元素出现次数的平方和：

vector<int> cnt(n);
int now = 0;
auto add = [&](int p) {
    now -= cnt[arr[p]] * cnt[arr[p]];
    cnt[arr[p]]++;
    now += cnt[arr[p]] * cnt[arr[p]];
};
auto del = [&](int p) {
    now -= cnt[arr[p]] * cnt[arr[p]];
    cnt[arr[p]]--;
    now += cnt[arr[p]] * cnt[arr[p]];
};

三维莫队

constexpr int N = 1e6 + 8;
int B;

struct QUE {
    int ql, qr, qt, id;
    bool operator < (const QUE& b) const {
        return ql / B == b.ql / B ? (qr / B == b.qr / B ? qt < b.qt : qr < b.qr) : ql < b.ql;
    }
} que[N];

struct UPD {
    int pos, c;
} upd[N];

int res, arr[N], ans[N];
int cnt[N];

void add(int x) {
    if (cnt[x] == 0) res++;
    ++cnt[x];
    return;
}

void del(int x) {
    --cnt[x];
    if (cnt[x] == 0) res--;
    return;
}

void update(int x, int qt) { // update() from ct to qt
    // upd[qt].pos in [ql, qr]
    if (que[x].ql <= upd[qt].pos && upd[qt].pos <= que[x].qr) {
        del(arr[upd[qt].pos]);
        add(upd[qt].c);
    }
    std::swap(arr[upd[qt].pos], upd[qt].c);  // change the color
    return;
}

void eachT() {
    int n = read(), q = read();
    B = pow(n, 0.666);

    for (int i = 1; i <= n; ++i) {
        arr[i] = read();
    }

    int cntq = 0, cntr = 0;
    for (int i = 1; i <= q; ++i) {
        std::string op;
        std::cin >> op;

        if (op[0] == 'Q') {
            ++cntq;
            que[cntq].ql = read();
            que[cntq].qr = read();
            que[cntq].qt = cntr;
            que[cntq].id = cntq;
        }
        else {
            ++cntr;
            upd[cntr].pos = read();
            upd[cntr].c = read();
        }
    }
    std::sort(que + 1, que + cntq + 1);

    int cl = 1, cr = 0, ct = 0;
    for (int i = 1; i <= cntq; ++i) {
        auto& [ql, qr, qt, id] = que[i];
        while (cl > ql) add(arr[--cl]);
        while (cl < ql) del(arr[cl++]);
        while (cr > qr) del(arr[cr--]);
        while (cr < qr) add(arr[++cr]);
        while (ct < qt) update(i, ++ct);
        while (ct > qt) update(i, ct--);
        ans[id] = res;
    }

    for (int i = 1; i <= cntq; ++i) {
        printf("%d\n", ans[i]);
    }
}

区间直线加, 区间最小值
问题 (区间直线加, 区间最小值 13)
给定长度为$n$ 的整数序列$a_0, a_1, ..., a_{n-1}$, 执行以下$q$ 个询问:
$l, r, b, c$：对$i \in [l, r)$,$a_i$ 修改为$a_i + b \cdot i + c$。
$l, r$：输出$\min(a_l, a_{l+1}, ..., a_{r-1})$。

May Holidays
问题 (May Holidays 14)
给定大小为$n$ 的树, 第$i$ 个点有权值$t_i$, 初始时没有离开, 执行$q$ 个询问:
$i$：若$i$ 离开, 则$i$ 回来; 否则离开。回答有多少个点$i$ 没有离开, 但后代中有超过$t_i$ 个点离开。

Manhattan 旅行商问题
问题 (Manhattan 旅行商问题)
给定平面值域为$[0, n]$ 的$q$ 个整点$(l_i, r_i)$, 求$0, 1, ..., q-1$ 的排列$p$, 使得$\sum_{i=1}^{q-1} |l_{p_{i-1}} - l_{p_i}| + |r_{p_{i-1}} - r_{p_i}|$ 尽可能小。
我们总有$\Theta(n\sqrt{q})$ 的解, 只需要将点按$(\lfloor l_i / B \rfloor, r_i)$ 排序。对于$\lfloor l_i / B \rfloor$ 相同的相邻点, 两个维度的总移动距离分别为$\Theta(qB)$ 和$\Theta(n^2 / B)$。对于$\lfloor l_i / B \rfloor$ 不同的相邻点, 总移动距离为$\Theta(n^2 / B)$。取$B = n^{2/3} q^{-1/3}$ 即可。

静态区间不同值个数
问题 (静态区间不同值个数 15)
给定长度为$n$ 的整数序列$a_0, a_1, ..., a_{n-1}$, 执行以下$q$ 个询问:
$l, r$：输出$a_l, a_{l+1}, ..., a_{r-1}$ 中不同值个数。

树上路径不同值个数
问题 (树上路径不同值个数 16)
给定$n$ 个结点的树, 每个结点有值$a_i$, 执行以下$q$ 个询问:
$u, v$：输出$a_{p_0}, a_{p_1}, ..., a_{p_k}$ 中不同值个数, 其中$p_0 = u, p_1, ..., p_k = v$ 是树上简单路径。

单点修改, 区间不同值个数
问题 (静态区间不同值个数 17)
给定长度为$n$ 的整数序列$a_0, a_1, ..., a_{n-1}$, 执行以下$q$ 个询问:
$p, x$：将$a_p$ 修改为$x$。
$l, r$：输出$a_l, a_{l+1}, ..., a_{r-1}$ 中不同值个数。

静态区间众数
问题 (静态区间众数 18)
给定长度为$n$ 的整数序列$a_0, a_1, ..., a_{n-1}$, 执行以下$q$ 个询问:
$l, r$：输出$a_l, a_{l+1}, ..., a_{r-1}$ 的任意一个众数。

静态区间逆序数
问题 (静态区间逆序数 19)
给定长度为$n$ 的整数序列$a_0, a_1, ..., a_{n-1}$, 执行以下$q$ 个询问:
$l, r$：输出$a_l, a_{l+1}, ..., a_{r-1}$ 的逆序数。

笛卡尔树

vector ls(n + 1, -1), rs(n +  1, -1);
vector<int> st(n + 1);
int top = 0;
// stk 维护笛卡尔树中节点对应到序列中的下标 
for (int i = 0; i < n; i++) 
{ 
	int k = top; // top 表示操作前的栈顶，k 表示当前栈顶
	while (k > 0 && w[stk[k]] > w[i]) k--; // 维护右链上的节点 
	if (k) rs[stk[k]] = i; // 栈顶元素.右儿子 := 当前元素 
	if (k < top) ls[i] = stk[k + 1]; // 当前元素.左儿子 := 上一个被弹出的元素 
	stk[++k] = i; // 当前元素入栈 top = k; 
}