ST Table

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

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

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

标准 RMQ，复杂度Θ(nlog⁡log⁡n)−Θ(1)\Theta(n \log \log n) - \Theta(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
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，复杂度为Θ(nlog⁡n)−Θ(1)\Theta(n \log n) - \Theta(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
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 问题的其它解决方法：

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

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

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

BIT 树状数组

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 权值树状数组 × 二维偏序

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

(aj,bj)≺(ai,bi)  =def  aj⋚ai  and  bj⋚bi(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j\lesseqgtr a_i\;\text{and}\; b_j\lesseqgtr b_i

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

模板

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

分析：这定义了偏序关系

(aj,bj)≺(ai,bi)  =def  aj ⩽ai  and  bj⩽bi(a_j,b_j)\prec(a_i,b_i) \;\xlongequal{def}\; a_j\ \leqslant a_i\;\text{and}\; b_j \leqslant b_i

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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,aj)≺(i,ai)  =def  j<i  and  aj>ai(j,a_j)\prec(i,a_i) \;\xlongequal{def}\; j\lt i\;\text{and}\; a_j\gt a_i

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}

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

1
2
3
4
5
6
7
8
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

更一般的情形

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

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

例题

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

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

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

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

BIT.2 高阶前缀和

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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 区间修改和区间查询

即线段树模板题。

类似地，利用差分，

sk=∑i=1kai=∑i=1k∑j=1ibj=∑i=1k∑j=ikbi=(k+1)∑i=1kbi−∑i=1kibis_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 分别维护序列{bi}\lbrace b_i\rbrace、{ibi}\lbrace ib_i\rbrace 的前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 高阶前缀和

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

sk=a0∑i=1kbi+a1∑i=1kibi+a2∑i=1ki2bi+⋯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=3m=3 时，sk=(k2+3k+2)∑i=1kbi+(−2k−3)∑i=1kibi+∑i=1ki2bis_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

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

suv=∑i=1u∑j=1vaij=∑i=1u∑j=1v∑k=1i∑l=1jbkl=∑i=1u∑j=1v∑k=iu∑l=jvbij=∑i=1u∑j=1v(u−i+1)(v−j+1)bij=(u+1)(v+1)∑i=1u∑j=1vbij−u∑i=1u∑j=1vjbij −v∑i=1u∑j=1vibij+∑i=1u∑j=1vijbij\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 分别维护序列{bij}\lbrace b_{ij}\rbrace、{ibij}\lbrace ib_{ij}\rbrace、{jbij}\lbrace jb_{ij}\rbrace、{ijbij}\lbrace ijb_{ij}\rbrace 的前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 的跳转方式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 维护是一样的。但在当信息不可减且可转化为询问后缀时，能够不翻转序列地维护修改和查询。

二维数点

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
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) 用于维护满足 结合律 的区间信息，支持在Θ(log⁡n)\Theta(\log n) 的时间内  区间修改  和  区间查询。

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

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

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

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

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

SMT1. 单点修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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 区间最大子段和

给定长度为nn 的整数序列aa，有qq 个询问：

  • 1,l,r1, l, r：输出al,al+1,...,ar−1a_l, a_{l+1}, ..., a_{r-1} 中的最大子段和。
  • 2,p,x2, p, x：将apa_p 修改为xx。Link
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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 一次函数区间复合函数求值

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

给定长度为nn 的由一次函数形成的序列fi=aix+bif_{i}=a_{i}x+b_{i}，有qq 个询问：

  • p,a,bp, a, b：将fpf_p 修改为fp(x)=ax+bf_p(x) = ax + b。
  • l,r,xl, r, x：求fr−1(...fl+1(fl(x))) mod 998244353f_{r-1}(...f_{l+1}(f_l(x))) \bmod 998244353。
InputOutput
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][l,r] 的aa 和bb，即fr(...fl+1(fl(x)))=ax+bf_{r}(...f_{l+1}(f_l(x)))=ax+b；
  • 修改 单点修改，无需懒标记；
  • 合并 结合复合函数fr(fl(x))=ar(alx+bl)+br=(aral)x+(arbl+br)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})，注意复合具有方向性！即不满足交换律，fr(fl(x))≠fl(fr(x))f_{r}(f_{l}(x)) \neq f_{l}(f_{r}(x))。
1
2
3
4
5
6
7
8
9
10
11
12
13
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. 区间修改、懒标记

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
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→Sf : S \rightarrow S 满足对任意x,y∈Sx, y \in S,f(op(x,y))=op(f(x),f(y))f(\text{op}(x, y)) = \text{op}(f(x), f(y)), 称ff 为SS 的自同态。SS 所有自同态的集合记为End(S)\text{End}(S)。所以这也叫半群区间自同态作用，区间求积（？

给定长度为nn 的整数序列aa，有qq 个询问：

  • 0,l,r,b,c0, l, r, b, c：对所有i∈[l,r)i \in [l, r), 将aia_i 修改为ai×b+ca_i \times b + c。
  • 1,l,r,b1, l, r, b：对所有i∈[l,r)i \in [l, r), 将aia_i 修改为ai×ba_i \times b。
  • 2,l,r,c2, l, r, c：对所有i∈[l,r)i \in [l, r), 将aia_i 修改为ai+ca_i + c。
  • 3,l,r3, l, r：求∑i=lr−1ai mod 571373\sum_{i=l}^{r-1} a_i \bmod 571373。Link

区间乘、区间加：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 - 序列操作

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

  1. I a b c 表示将[a,b][a,b] 这一段区间的元素集体增加cc；
  2. R a b表示将[a,b][a,b] 区间内所有元素变成相反数；
  3. Q a b c 表示询问[a,b][a,b] 这一段区间中选择cc 个数相乘的所有方案的和 mod 19940417\bmod 19940417 的值。
InputOutput
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⩽50000n \leqslant 50000，q⩽50000q \leqslant 50000，初始∣ai∣⩽109|a_{i}|\leqslant 10^9，I 操作中∣c∣⩽109|c| \leqslant 10^9，Q 操作中1⩽c⩽min⁡(b−a+1,20)1 \leqslant c \leqslant \min(b-a+1,20)。

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

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

p.fc=∑i=020l.fi⋅r.fc−ip.f_{c}=\sum_{i=0}^{20}l.f_{i}\cdot r.f_{c-i}

1
2
3
4
5
6
7
8
9
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;
}

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

  • 根据上一题的结论，懒标记的下传应当先乘再加；
  • 区间×d\times d 后，选择cc 个数相乘的所有方案的和fc←fc×dcf_{c}\leftarrow f_{c}\times d^{c}，子节点的两种懒标记都×d\times d；
  • 区间+d+d 后，选择cc 个数相乘的所有方案的和的变化比较复杂，假设我们选出的数是a1,a2,…,aca_{1},a_{2},\dots, a_{c}，原先对答案的贡献是Sc=∏i=1caiS_{c}=\prod\limits_{i=1}^{c} a_{i}，区间+d+d 后，对答案的贡献是Sc′=∏i=1c(ai+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}$$ 预处理组合数，根据递推式二重循环即可。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
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 区间加，区间平方和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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 };
    }
};

例：区间方差

S2=1n∑(xi−xˉ)2=1n∑xi2−xˉ2S^{2}=\dfrac{1}{n}\sum(x_{i}-\bar{x})^{2}=\dfrac{1}{n}\sum x_{i}^{2}-\bar{x}^{2}

SMT2.3 区间赋值，区间和

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

  • 操作11：关上从ll 到rr（含边界）范围内的所有灯；
  • 操作22：打开从ll 到rr（含边界）范围内的所有灯。

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

数据范围：1 ⩽ n⩽ 109,1 ⩽ m⩽ 3⋅105,1 ⩽ li,ri⩽ n,1 ⩽ ki⩽ 21  \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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 区间赋值、区间加，区间最值及其个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 给定nn 个点、nn 条双向边的环。有mm 对点对ai,bia_i,b_i，要求删掉尽可能多的边，使得删完后，每对ai,bia_i,b_i 仍联通。求出剩余边数的最小值。(CF1996G. Penacony)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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 需查询单点前缀和，一次询问复杂度Θ(log⁡2n)\Theta(\log^{2}n)；而线段树的分治结构 合并二分和查询的过程，实现Θ(log⁡n)\Theta(\log n) 的复杂度。

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

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

其中，序列的第kk 个前缀平均值定义为sk=1k∑i=1kais_k=\dfrac1k\sum\limits_{i=1}^{k}a_i，整体平均值为sns_n。

数据范围：1⩽n⩽5×105,1⩽q⩽105,0⩽ai,x,B⩽109,1⩽c⩽n1 \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)

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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 给定序列aa 和序列bb，长度均为nn。问有多少组(l,r)(l,r)，满足1⩽l⩽r⩽n1 \leqslant l \leqslant r \leqslant n 且

max⁡l⩽i⩽r{ai}=min⁡l⩽i⩽r{bi}\max\limits_{l \leqslant i \leqslant r}\lbrace a_{i} \rbrace = \min\limits_{l \leqslant i \leqslant r}\lbrace b_{i} \rbrace

数据范围：n⩽2×105n \leqslant 2\times 10^5，∣ai∣,∣bi∣⩽109|a_i|,|b_i| \leqslant 10^9。(CF689D - Friends and Subsequences)

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

  • p1p_{1} 为满足max⁡l⩽i⩽p1{ai}⩾min⁡l⩽i⩽p1{bi}\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 的最小的下标；
  • p2p_{2} 为满足max⁡l⩽i⩽p2{ai}>min⁡l⩽i⩽p2{bi}\max\limits_{l \leqslant i \leqslant p_{2}}\lbrace a_{i} \rbrace > \min\limits_{l \leqslant i \leqslant p_{2}}\lbrace b_{i} \rbrace 的最小的下标，也即p2−1p_{2}-1 为满足max⁡l⩽i⩽p2−1{ai}⩽min⁡l⩽i⩽p2−1{bi}\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⁡\log。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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 有nn 个商店，去第ii个商店购买物品需要花费aia_{i} 元，保证aa 序列为非增序列。两种操作：

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

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

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

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

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

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

  • 如果当前区间的最小值<y<y，则一个都买不起，返回；
  • 如果当前区间的和⩾y\geqslant y，全买，买了区间长度个，花费区间和的费用，更新这两个数值，返回；
  • 否则买其中一部分，继续递归。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
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 权值线段树

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

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

1
2
3
4
5
6
7
8
9
10
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 两个人用石头博弈，共nn 种石头，每种石头有两块，价值分别为ai, bia_{i},\ b_{i}。A 和 B 按照 ABBAABBAABBA 的顺序依次购买一块石头。

规定：

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

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

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

Step1 假博弈真贪心

这部分比较简单。

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

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

Step2 线段树

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

维护什么？

  • 每个数出现的次数 siz，常规的权值线段树。
  • 排名为ii 的数的总和，记为 sum[4]，其中 tr[p].sum[k] 表示节点pp 对应的区间[l,r][l,r] 中，排名为i, i≡k(mod4)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≡ki,\ i \equiv k 的总和加上右节点排名为i, i−m≡ki,\ i-m \equiv k 的总和相加，其中mm 是左节点的数的数量。
  • 对叶的操作：
    • 对于 siz，常规操作，tr[p].siz += d；
    • 对于 sum[4]，因为叶只有一个数，那排名就是 0，容易想到 tr[p].val[0] += x * d，但这样是错误的，原因是 相同的数也应当要排名，具体写法参见代码。

如何查询？

  • 注意到查询只需要查询根节点rt\mathrm{rt}，所以只需写一个简略的函数：置值域为[−105,105][-10^{5},10^{5}]，这样，根节点的左儿子即是ai−bi⩽0a_{i} - b_{i} \leqslant 0，右儿子即是ai−bi>0a_{i} - b_{i} > 0，天然地将树分成了两块。根据 Step1 的推断，对于左儿子，查询 sum[0] + sum[3]，对于右儿子，视左儿子的节点个数分情况讨论，再将两者求和即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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] 表示节点pp 所在树的根节点 unix。递归地将两棵线段树的节点信息对应合并：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 将树上节点 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 的根设置为新根
    }
}

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

1
2
3
4
5
6
7
8
9
10
// 将树上节点 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 区间加，区间积，区间删除，并查集维护连通性

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

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

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

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

  • 操作 1, 2, 7 是基础写法。
  • 操作 3, 4：以 3 为例，把大于bb 的变成bb 等价于把大于bb 的都删除，即区间赋值，再插入这么多个bb，即权值线段树的插入，为了知道需要插入多少个，需先查询这段区间数的数量 siz。
  • 操作 5：权值线段树的 kthnum 模板函数。
  • 操作 6：需维护区间积，显然这个积会爆 LL，稍作转换，维护区间log⁡\log 和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
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×HW\times H 格点矩形区域（不含边框）内，点权之和最大值。(VJsum7F - 窗口的星星)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/// ---------------- 扫描线 ----------------
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 区间加，区间数的种类（标记永久化／拖拖）

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

数据范围：1⩽k⩽1041 \leqslant k \leqslant 10^4，1⩽n⩽1051 \leqslant n \leqslant 10^5，1⩽ai⩽1091 \leqslant a_i \leqslant 10^9。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/// ---------------- 扫描线 ----------------
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. 可持久化线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
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 小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 历史版本区间赋值，区间加

1
2
3
4
5
6
7
8
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)
给定nn 条直线, 按顺序执行以下qq 个询问:
a,ba, b：插入直线y=ax+by = ax + b。
pp：求最小的yy 使得y=x⋅py = x \cdot p。
问题可以转化为插入点(a,b)(a, b), 求(−p,−1)(- p, -1) 和其中某个点的最大点积。

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

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

李超线段树

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

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

其他数据结构

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

分块、莫队

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

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

例 询问区间颜色个数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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]);
    }
}

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

1
2
3
4
5
6
7
8
9
10
11
12
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]];
};

三维莫队

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
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)
给定长度为nn 的整数序列a0,a1,...,an−1a_0, a_1, ..., a_{n-1}, 执行以下qq 个询问:
l,r,b,cl, r, b, c：对i∈[l,r)i \in [l, r),aia_i 修改为ai+b⋅i+ca_i + b \cdot i + c。
l,rl, r：输出min⁡(al,al+1,...,ar−1)\min(a_l, a_{l+1}, ..., a_{r-1})。

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

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

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

树上路径不同值个数
问题 (树上路径不同值个数 16)
给定nn 个结点的树, 每个结点有值aia_i, 执行以下qq 个询问:
u,vu, v：输出ap0,ap1,...,apka_{p_0}, a_{p_1}, ..., a_{p_k} 中不同值个数, 其中p0=u,p1,...,pk=vp_0 = u, p_1, ..., p_k = v 是树上简单路径。

单点修改, 区间不同值个数
问题 (静态区间不同值个数 17)
给定长度为nn 的整数序列a0,a1,...,an−1a_0, a_1, ..., a_{n-1}, 执行以下qq 个询问:
p,xp, x：将apa_p 修改为xx。
l,rl, r：输出al,al+1,...,ar−1a_l, a_{l+1}, ..., a_{r-1} 中不同值个数。

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

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

笛卡尔树

1
2
3
4
5
6
7
8
9
10
11
12
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; 
}