一些简单的偏序维护问题

2020-02-14

综述

拜读了毒瘤的数据结构课件, 深受启发, 甚是谔谔, 当即感觉自己之前一直在玩泥巴.

初学数据结构, 恳请指正.

什么是偏序

其实这一点也不重要

对于一个非空集上的二元关系, 如果其满足自反性, 反对称性, 传递性, 那么称这个二元关系就是这个集合上的偏序.

一个简单的例子: 实数集上的小于等于关系是一个偏序关系.

偏序维护

现在我们有一个具有很多属性的元素, 比如有 $a_i, b_i, c_i, \ldots$

接下来对每个属性给出一些限制, 对满足这些限制的元素进行一些操作, 像 $L_1 \leq a_i \leq R_1, L_2 \leq b_i \leq R_2, L_3 \leq c_i \leq R_3, \ldots$

这就是在维护偏序了, 有时候也把 “属性” 称作 “维度”.

一些维护方法 & 例题

反正我之前是先推出一个 poly log 的数据结构做法

然后想办法去 log，到一个可以接受的复杂度

from lxl 某次洛谷网课

先是两个离线方法.

CDQ 分治

强烈推荐 __stdcall 的 CDQ 分治教程.

简单来说, CDQ 分治做了这样一件事情: 把操作离线下来, 分成两部分, 递归解决; 考虑把这两部分合并, 就要考虑左半部分操作对右半部分的影响, 然后合并.

Luogu P3810【模板】三维偏序

是一道经典题, 考虑 CDQ 分治, 先将第一维排序, CDQ 分治过程中按第二维排序, 使用树状数组统计第三维答案.

有一个细节: 可能存在相同元素, 按题意来讲这些完全相同的元素互相有贡献, 但是在 CDQ 分治的过程中只能统计左半部分对右半部分的贡献, 所以需要去重, 对重复不同次数的元素给定一个不同的权值.

时间复杂度: $O (n\log n \log k)$

代码实现

> 点击显示 / 隐藏 
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
// Luogu P3810
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 1e5+5, MAXM = 2e5+5;

struct Item {
    int idx, a, b, c, w;
    Item(int _i = 0, int _a = 0, int _b = 0, int _c = 0, int _w = 0):
        idx(_i), a(_a), b(_b), c(_c), w(_w) { }
    bool operator < (const Item& rhs) const {
        return (a == rhs.a)? ((b == rhs.b)? c < rhs.c: b < rhs.b): a < rhs.a;
    }
    bool operator== (const Item& rhs) const {
        return !(*this < rhs) && !(rhs < *this);
    }
} A[MAXN], tmp[MAXN];

int n, m, nA, K;
int Ans[MAXN], f[MAXN];

namespace BIT {
    int C[MAXM];

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

    inline void Mdy(const int& pos, const int& d) {
        for (int i = pos; i <= K; i += lowbit(i)) C[i] += d;
    }
    inline int Qry(const int& pos) {
        int ret = 0;
        for (int i = pos; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
}

void CDQ(const int& L, const int& R) {
    if (L >= R) return;
    int Mid = (L + R) / 2, p = L, q = Mid+1;
    CDQ(L, Mid), CDQ(Mid+1, R);
    for (int i = L; i <= R; ++i) {
        // 在右半部分排满时移动左半部分
        if ((p <= Mid && A[p].b <= A[q].b) || q > R)
            BIT::Mdy(A[p].c, A[p].w), tmp[i] = A[p++];
        else Ans[A[q].idx] += BIT::Qry(A[q].c), tmp[i] = A[q++];
    }
    // 清空树状数组
    for (int i = L; i <= Mid; ++i) BIT::Mdy(A[i].c, -A[i].w);
    for (int i = L; i <= R; ++i) A[i] = tmp[i];
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(K);
    for (int a, b, c, i = 1; i <= n; ++i)
        read(a), read(b), read(c), A[i] = Item(i, a, b, c, 1);
    // solve
    sort(A+1, A+1+n);
    for (int i = 1; i <= n; ++i) {
        int j = i;
        while (j < n && A[i] == A[j+1]) ++j;
        A[++nA] = A[i], A[nA].w = j - i + 1;
        i = j;
    }
    CDQ(1, nA);
    // output
    for (int i = 1; i <= nA; ++i) f[Ans[A[i].idx] + A[i].w] += A[i].w;
    for (int i = 1; i <= n; ++i) printf("%d\n", f[i]);
    return 0;
}

Luogu P3374【模板】树状数组 1

CDQ 分治可以顶替复杂的高级数据结构.

我们可以把初始值看作在 $0$ 的基础上单点修改, 把查询看作两次询问前缀和, 这样每个操作有时间, 对应操作位置, 权值三个属性.

时间这一维按给定顺序有序, CDQ 分治过程中按操作位置维护权值和即可, 注意在操作位置相同时, 按照先修改后查询的顺序统计.

代码实现

> 点击显示 / 隐藏 
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
// Luogu P3374
// DeP
#include <cctype>
#include <cstdio>

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc(); 
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 500005;

struct Ask {
    int opt, pos; LL val;
    bool operator < (const Ask& rhs) const {
        return pos < rhs.pos || (pos == rhs.pos && opt < rhs.opt);
    }
} Q[MAXN * 3], tmp[MAXN * 3];

int n, m, qidx, aidx;
LL A[MAXN], Ans[MAXN];

void CDQ(int L, int R) {
    if (L == R) return;
    int Mid = (L + R) / 2;
    CDQ(L, Mid), CDQ(Mid+1, R);
    LL sum = 0;
    int p = L, q = Mid+1;
    for (int i = L; i <= R; ++i) {
    	if ((p <= Mid && Q[p] < Q[q]) || q > R) {
    	    if (Q[p].opt == 1) sum += Q[p].val;
    	    tmp[i] = Q[p++];
    	} else {
    	    if (Q[q].opt == 2) Ans[Q[q].val] -= sum;
    	    if (Q[q].opt == 3) Ans[Q[q].val] += sum;
    	    tmp[i] = Q[q++];
    	}
    }
    for (int i = L; i <= R; ++i) Q[i] = tmp[i];
}

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.in", "r", stdin);
#endif
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(A[i]);
        Q[++qidx] = (Ask){ 1, i, A[i] };
    }
    for (int i = 1; i <= m; ++i) {
        int opt, L, R; LL val;
        read(opt); read(L);
        switch (opt) {
            case 1:
                read(val);
                Q[++qidx] = (Ask){ opt, L, val };
                break;
            case 2:
                read(R);
                Q[++qidx] = (Ask){ opt, L-1, ++aidx };
                Q[++qidx] = (Ask){ opt+1, R, aidx };
                break;
            default: puts("ERROR");
        }
    }
    CDQ(1, qidx);
    for (int i = 1; i <= aidx; ++i) printf("%lld\n", Ans[i]);
	return 0;
}

HDU 5126 stars

对于四维的情况, CDQ 分治可以嵌套使用. 但是 CDQ 套 CDQ 套 CDQ… 就和树套树套树… 一样没用, 不如直接写 bitset

这是一个三维数点问题, 因为要考虑操作时间的影响就是四维偏序了, 在此我使用 CDQ 套 CDQ 解决.

还是参考 __stdcall 的 CDQ 套 CDQ 教程, 把第二维按左右两部分重标号, 依此为根据统计答案.

空间内数点可仿照平面内数点的思路, 统计前缀和按坐标点容斥计算就好了.

时间复杂度大概是 $O(n \log ^3 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
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
// HDU 5126
// DeP
#include <cctype>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 5e5+5;

struct Ask {
    int opt, idx, x, y, z, part;
} Q[MAXN], tmp2d[MAXN], tmp3d[MAXN];

int n, qidx, aidx;
int A[MAXN], B[MAXN << 1], nB;
int Ans[MAXN];

namespace BIT {
    int C[MAXN << 1];

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

    inline void Mdy(const int& pos, const int& val) {
        for (int i = pos; i <= nB; i += lowbit(i)) C[i] += val;
    }
    inline int Qry(const int& pos) {
        int ret = 0;
        for (int i = pos; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
}

void CDQ3d(int L, int R) {
    if (L >= R) return;
    int Mid = (L + R) / 2, p = L, q = Mid+1;
    CDQ3d(L, Mid), CDQ3d(Mid+1, R);
    for (int i = L; i <= R; ++i) {
        if ((p <= Mid && tmp2d[p].y <= tmp2d[q].y) || q > R) {
            // 只考虑两次归并都排布在左半部分的元素的贡献
            if (tmp2d[p].opt == 0 && tmp2d[p].part == 0)
                BIT::Mdy(tmp2d[p].z, 1);
            tmp3d[i] = tmp2d[p++];
        } else {
            // 只统计两次归并都排布在右半部分的元素的答案
            if (tmp2d[q].opt != 0 && tmp2d[q].part == 1)
                Ans[tmp2d[q].idx] += tmp2d[q].opt * BIT::Qry(tmp2d[q].z);
            tmp3d[i] = tmp2d[q++];
        }
    }
    for (int i = L; i <= Mid; ++i)
        if (tmp2d[i].opt == 0 && tmp2d[i].part == 0)
            BIT::Mdy(tmp2d[i].z, -1);
    for (int i = L; i <= R; ++i) tmp2d[i] = tmp3d[i];
}

void CDQ2d(int L, int R) {
    if (L >= R) return;
    int Mid = (L + R) / 2, p = L, q = Mid+1;
    CDQ2d(L, Mid), CDQ2d(Mid+1, R);
    for (int i = L; i <= R; ++i) {
        // 重标号: 左半部分标为 0, 右半部分标为 1
        if ((p <= Mid && Q[p].x <= Q[q].x) || q > R) {
            Q[p].part = 0;
            tmp2d[i] = Q[p++];
        } else {
            Q[q].part = 1;
            tmp2d[i] = Q[q++];
        }
    }
    for (int i = L; i <= R; ++i) Q[i] = tmp2d[i];
    CDQ3d(L, R);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    int Ti; read(Ti);
    while (Ti--) {
        // init
        qidx = nB = 0;
        // input
        read(n);
        for (int i = 1; i <= n; ++i) {
            static int opt, x1, y1, z1, x2, y2, z2;
            read(opt), read(x1), read(y1), read(z1);
            switch (opt) {
                case 1:
                    Q[++qidx] = (Ask){ 0, i, x1, y1, z1, 0 };
                    Ans[i] = -1, B[++nB] = z1;
                    break;
                case 2:
                    read(x2), read(y2), read(z2);
                    --x1, --y1, --z1;
                    // 容斥
                    Q[++qidx] = (Ask){ 1, i, x2, y2, z2, 0 };
                    Q[++qidx] = (Ask){-1, i, x1, y1, z1, 0 };
                    Q[++qidx] = (Ask){-1, i, x1, y2, z2, 0 };
                    Q[++qidx] = (Ask){-1, i, x2, y1, z2, 0 };
                    Q[++qidx] = (Ask){-1, i, x2, y2, z1, 0 };
                    Q[++qidx] = (Ask){ 1, i, x2, y1, z1, 0 };
                    Q[++qidx] = (Ask){ 1, i, x1, y2, z1, 0 };
                    Q[++qidx] = (Ask){ 1, i, x1, y1, z2, 0 };
                    Ans[i] = 0, B[++nB] = z1, B[++nB] = z2;
                    break;
                default: fprintf(stderr, "ERR\n");
            }
        }
        // solve
        sort(B+1, B+1+nB);
        nB = unique(B+1, B+1+nB) - B - 1;
        // 这一维要丢到 BIT 里, 于是离散化
        for (int i = 1; i <= qidx; ++i)
            Q[i].z = lower_bound(B+1, B+1+nB, Q[i].z) - B;
        CDQ2d(1, qidx);
        // output
        for (int i = 1; i <= n; ++i)
            if (~Ans[i]) printf("%d\n", Ans[i]);
    }
    return 0;
}

整体二分

对于一个询问, 例如区间第 K 小, 有一个朴素的想法: 每次二分答案的值域, 看当前二分值是否恰好在区间的排名为 K.

这样看起来很慢, 于是可以将所有操作视为一个整体进行二分, 每次给定一个答案区间和一个操作区间, 这就是整体二分了.

Luogu P3834【模板】可持久化线段树 1（主席树）

可持久化线段树 $\times$ 静态区间第 k 小 $\checkmark$

算是整体二分的经典问题了. 直接使用之前说过的思路, 整体二分即可.

具体地说, 对于原序列上的数, 按当前二分的值域进行划分; 而对于操作, 则统计当前操作对应区间内数的个数, 以当前操作第 k 小为依据进行划分.

代码实现

> 点击显示 / 隐藏 
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
// Luogu P3834
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 2e5+5;

struct Ask {
    int opt, idx, L, R, k;
} Q[MAXN << 1], tmpL[MAXN << 1], tmpR[MAXN << 1];

int n, m, qidx;
int A[MAXN], B[MAXN], nB;
int Ans[MAXN];

namespace BIT {
    int C[MAXN];

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

    inline void Mdy(const int& pos, const int& val) {
        for (int i = pos; i <= n; i += lowbit(i)) C[i] += val;
    }

    inline int Qry(const int& pos) {
        int ret = 0;
        for (int i = pos; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
    inline int Qry(const int& L, const int& R) { return Qry(R) - Qry(L-1); }
}

void divide(int L, int R, const int& opL, const int& opR) {
    if (opL > opR) return;
    if (L == R) {
        for (int i = opL; i <= opR; ++i)
            if (Q[i].opt == 1) Ans[Q[i].idx] = L;
        return;
    }
    int Mid = (L + R) / 2, p = 0, q = 0;
    for (int i = opL; i <= opR; ++i) {
        if (Q[i].opt == 0) {
            if (Q[i].R <= Mid)
                BIT::Mdy(Q[i].L, Q[i].k), tmpL[++p] = Q[i];
            else tmpR[++q] = Q[i];
        } else {
            int w = BIT::Qry(Q[i].L, Q[i].R);
            if (Q[i].k <= w) tmpL[++p] = Q[i];
            else Q[i].k -= w, tmpR[++q] = Q[i];
        }
    }
    for (int i = 1; i <= p; ++i)
        if (tmpL[i].opt == 0) BIT::Mdy(tmpL[i].L, -tmpL[i].k);
    for (int i = 1; i <= p; ++i) Q[opL+i-1] = tmpL[i];
    for (int i = 1; i <= q; ++i) Q[opL+p+i-1] = tmpR[i];
    divide(L, Mid, opL, opL + p - 1), divide(Mid+1, R, opL + p, opR);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(A[i]), B[++nB] = A[i];
    // solve
    sort(B+1, B+1+nB);
    nB = unique(B+1, B+1+nB) - B - 1;
    for (int i = 1; i <= n; ++i) {
        A[i] = lower_bound(B+1, B+1+nB, A[i]) - B;
        Q[++qidx] = (Ask){ 0, -1, i, A[i], 1 };
    }
    for (int i = 1; i <= m; ++i) {
        static int L, R, k;
        read(L), read(R), read(k);
        Q[++qidx] = (Ask){ 1, i, L, R, k };
    }
    divide(1, nB, 1, qidx);
    // output
    for (int i = 1; i <= m; ++i) printf("%d\n", B[Ans[i]]);
    return 0;
}

Luogu P3242 [HNOI2015] 接水果

通过对路径两端点的 dfs 序的讨论, 路径之间的相互包含可以看作是在二维矩阵中数点, 放在这道题中就是二维矩阵中查询第 k 小了.

类似的转化还有子树内距离小于等于的点, 将 DFS 序看作一维, 深度看作另一维…

这东西可以写可持久化树套树, 我…

我当然是把矩阵拆成扫描线, 然后整体二分进行统计.

代码实现

> 点击显示 / 隐藏 
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
173
174
175
176
177
178
179
180
181
182
183
// Luogu P3242
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 4e4+5, MAXM = 5 * MAXN;

struct Ask {
    int opt, idx, u, L, R, k, val;
    bool operator < (const Ask& rhs) const {
        return u < rhs.u || (u == rhs.u && opt < rhs.opt);
    }
} Q[MAXM], tmpL[MAXM], tmpR[MAXM];

int n, m, qc, qidx;
int st[MAXN], ed[MAXN];
int Ans[MAXN], B[MAXN], nB;

namespace Graph {
    struct Edge { int nxt, to; } edges[MAXN << 1];
    int head[MAXN], eidx;

    inline void init() { memset(head, -1, sizeof head), eidx = 1; }
    inline void AddEdge(int from, int to) {
        edges[++eidx] = (Edge){ head[from], to };
        head[from] = eidx;
    }
}

namespace HLD {
    using namespace Graph;
    int size[MAXN], depth[MAXN], pre[MAXN], son[MAXN];
    int topfa[MAXN], dfs_clock;

    void dfs1(int u, int fa) {
        depth[u] = depth[fa] + 1;
        pre[u] = fa, size[u] = 1, son[u] = -1;
        for (int v, i = head[u]; ~i; i = edges[i].nxt) {
            if ((v = edges[i].to) == fa) continue;
            dfs1(v, u), size[u] += size[v];
            if (son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
        }
    }

    void dfs2(int u, int top) {
        topfa[u] = top, st[u] = ++dfs_clock;
        if (~son[u]) dfs2(son[u], top);
        for (int v, i = head[u]; ~i; i = edges[i].nxt)
            if ((v = edges[i].to) != pre[u] && v != son[u]) dfs2(v, v);
        ed[u] = dfs_clock;
    }

    int LCA(int u, int v) {
        while (topfa[u] != topfa[v]) {
            if (depth[topfa[u]] < depth[topfa[v]]) swap(u, v);
            u = pre[topfa[u]];
        }
        return depth[u] > depth[v]? v: u;
    }

    int findson(int u, int v) {
        while (topfa[u] != topfa[v]) {
            if (pre[topfa[u]] == v) return topfa[u];
            u = pre[topfa[u]];
        }
        return son[v];
    }

    void solve(int root = 1) { dfs1(root, 0), dfs2(root, root); }
}

namespace BIT {
    int C[MAXN];

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

    inline void Mdy(const int& pos, const int& val) {
        for (int i = pos; i <= n; i += lowbit(i)) C[i] += val;
    }
    inline void Mdy(const int& L, const int& R, const int& val) {
        Mdy(L, val), Mdy(R+1, -val);
    }

    inline int Qry(const int& pos) {
        int ret = 0;
        for (int i = pos; i; i -= lowbit(i)) ret += C[i];
        return ret;
    }
}

void divide(int L, int R, const int& opL, const int& opR) {
    if (opL > opR) return;
    if (L == R) {
        for (int i = opL; i <= opR; ++i)
            if (Q[i].opt == 1) Ans[Q[i].idx] = B[L];
        return;
    }
    int Mid = (L + R) / 2, p = 0, q = 0;
    for (int i = opL; i <= opR; ++i) {
        if (Q[i].opt == 0) {
            if (Q[i].k <= Mid)
                BIT::Mdy(Q[i].L, Q[i].R, Q[i].val), tmpL[++p] = Q[i];
            else tmpR[++q] = Q[i];
        } else {
            int w = BIT::Qry(Q[i].L);
            if (Q[i].k <= w) tmpL[++p] = Q[i];
            else Q[i].k -= w, tmpR[++q] = Q[i];
        }
    }
    for (int i = 1; i <= p; ++i)
        if (tmpL[i].opt == 0) BIT::Mdy(tmpL[i].L, tmpL[i].R, -tmpL[i].val);
    for (int i = 1; i <= p; ++i) Q[opL + i - 1] = tmpL[i];
    for (int i = 1; i <= q; ++i) Q[opL + p + i - 1] = tmpR[i];
    divide(L, Mid, opL, opL + p - 1), divide(Mid+1, R, opL + p, opR);
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // init
    Graph::init();
    // input
    read(n), read(m), read(qc);
    for (int u, v, i = 1; i < n; ++i)
        read(u), read(v), Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    // solve
    HLD::solve();
    for (int u, v, w, i = 1; i <= m; ++i) {
        read(u), read(v), read(w);
        if (st[u] > st[v]) swap(u, v);
        B[++nB] = w;
        if (HLD::LCA(u, v) == u) {
            int z = HLD::findson(v, u);
            if (st[z] > 1) {
                Q[++qidx] = (Ask){ 0, -1, 1, st[v], ed[v], w, 1 };
                Q[++qidx] = (Ask){ 0, -1, st[z], st[v], ed[v], w, -1 };
            }
            if (ed[z] < n) {
                Q[++qidx] = (Ask){ 0, -1, st[v], ed[z]+1, n, w, 1 };
                Q[++qidx] = (Ask){ 0, -1, ed[v]+1, ed[z]+1, n, w, -1 };
            }
        } else {
            Q[++qidx] = (Ask){ 0, -1, st[u], st[v], ed[v], w, 1 };
            Q[++qidx] = (Ask){ 0, -1, ed[u]+1, st[v], ed[v], w, -1 };
        }
    }
    sort(B+1, B+1+nB);
    nB = unique(B+1, B+1+nB) - B - 1;
    for (int i = 1; i <= qidx; ++i)
        Q[i].k = lower_bound(B+1, B+1+nB, Q[i].k) - B;
    for (int u, v, k, i = 1; i <= qc; ++i) {
        read(u), read(v), read(k);
        if (st[u] > st[v]) swap(u, v);
        Q[++qidx] = (Ask){ 1, i, st[u], st[v], -1, k, 0 };
    }
    sort(Q+1, Q+1+qidx);
    divide(1, nB, 1, qidx);
    // output
    for (int i = 1; i <= qc; ++i) printf("%d\n", Ans[i]);
    return 0;
}

遇到毒瘤出题人强制在线就挂了 = =, 所以还需要一些在线解决问题的科技.

可持久化

刚开始学可持久化的时候感觉这个好高级啊, 后来感觉…

这不就是个数据结构的前缀和吗 = =

Luogu P3834【模板】可持久化线段树 1（主席树）

建权值线段树, 动态开点.

按照初始序列建可持久化线段树, 每个位置对应的线段树, 就是包含这个位置前缀信息的线段树了.

具体地说, 先建出一个空树, 然后对于每个位置, 在上一个位置的基础上拓展, 尽量利用之前以及储存过的信息, 再建出一颗新树. 这样每次新增的节点数为 $O(\log n)$, 总共建出 $n$ 颗线段树, 总空间复杂度为 $O(n \log n + n \log n)$.

这样对于每个询问 $[L, R]$, 按照前缀和的基本思想, 在 $L-1, R$ 两颗树上进行二分就好了, 即记录当前二分到的两颗树的左子树 size 之差 (因为是求第 $k$ 小), 然后分类讨论移动到左子树还是右子树.

时间复杂度: $O(n \log 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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
// Luogu P3834
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 2e5+5;

int n, m, nB;
int A[MAXN], B[MAXN], rt[MAXN];

namespace SGT {
    struct Node { int lc, rc, sum; } dat[MAXN << 5];
    int nidx;

    void build(int& nd, int L, int R) {
        nd = ++nidx;
        if (L == R) return;
        int Mid = (L + R) / 2;
        build(dat[nd].lc, L, Mid), build(dat[nd].rc, Mid+1, R);
    }

    int Mdy(int nd, int L, int R, const int& val) {
        int nxt = ++nidx;
        dat[nxt] = dat[nd], ++dat[nxt].sum;
        if (L == R) return nxt;
        int Mid = (L + R) / 2;
        if (val <= Mid) dat[nxt].lc = Mdy(dat[nxt].lc, L, Mid, val);
        else dat[nxt].rc = Mdy(dat[nxt].rc, Mid+1, R, val);
        return nxt;
    }

    int Qry(int x, int y, int L, int R, const int& k) {
        if (L == R) return L;
        int d = dat[dat[y].lc].sum - dat[dat[x].lc].sum, Mid = (L + R) / 2;
        if (k <= d) return Qry(dat[x].lc, dat[y].lc, L, Mid, k);
        return Qry(dat[x].rc, dat[y].rc, Mid+1, R, k - d);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(A[i]), B[i] = A[i];
    // solve
    sort(B+1, B+1+n);
    nB = unique(B+1, B+1+n) - B - 1;
    for (int i = 1; i <= n; ++i) A[i] = lower_bound(B+1, B+1+nB, A[i]) - B;
    SGT::build(rt[0], 1, nB);
    for (int i = 1; i <= n; ++i) rt[i] = SGT::Mdy(rt[i-1], 1, nB, A[i]);
    // output
    while (m--) {
        static int L, R, K;
        read(L), read(R), read(K);
        printf("%d\n", B[SGT::Qry(rt[L-1], rt[R], 1, nB, K)]);
    }
    return 0;
}

Luogu P3168 [CQOI2015] 任务查询系统

刚才是单点修改, 区间求和, 而现在是区间修改, 单点求和, 那么差分即可解决.

尝试了不先建出空树的写法, 感觉还行 ?

对时间建权值线段树, 把每次区间操作差分, 挂在对应的时间点上, 记录最后操作对应的节点为当前时间点的节点, 对于询问直接在对应时间点的树上二分即可.

代码实现

> 点击显示 / 隐藏 
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
// Luogu P3168
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 2e5+5, MAXV = 1e7;

int n, m;
int rt[MAXN], pos[MAXN];
vector<int> A[MAXN];

namespace PSGT {
#define Mid ((L + R) / 2)
    struct Node { int lc, rc, size; LL sum; } dat[MAXN << 6];
    int nidx;

    inline int Abs(int v) { return v > 0? v: -v; }
    int Mdy(int nd, int L, int R, const int& val) {
        int nxt = ++nidx;
        dat[nxt] = dat[nd], dat[nxt].size += (val < 0? -1: 1), dat[nxt].sum += val;
        if (L == R) return nxt;
        if (Abs(val) <= Mid) dat[nxt].lc = Mdy(dat[nxt].lc, L, Mid, val);
        else dat[nxt].rc = Mdy(dat[nxt].rc, Mid+1, R, val);
        return nxt;
    }

    LL Qry(int nd, int L, int R, const int& k) {
        if (L == R) return k * L;
        int d = dat[dat[nd].lc].size;
        if (k <= d) return Qry(dat[nd].lc, L, Mid, k);
        return Qry(dat[nd].rc, Mid+1, R, k - d) + dat[dat[nd].lc].sum;
    }
#undef Mid
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(m), read(n);
    for (int i = 1; i <= m; ++i) {
        static int L, R, val;
        read(L), read(R), read(val);
        A[L].push_back(val), A[R+1].push_back(-val);
    }
    // solve
    int nidx = 0;
    for (int i = 1; i <= n; ++i) {
        for (size_t k = 0; k < A[i].size(); ++k)
            ++nidx, rt[nidx] = PSGT::Mdy(rt[nidx-1], 1, MAXV, A[i][k]);
        pos[i] = nidx;
    }
    // output
    while (n--) {
        static int x, a, b, c, k, nd; static LL pre = 1;
        read(x), read(a), read(b), read(c);
        k = 1 + (a * pre + b) % c, nd = pos[x];
        if (PSGT::dat[rt[nd]].size > k) printf("%lld\n", pre = PSGT::Qry(rt[nd], 1, MAXV, k));
        else printf("%lld\n", pre = PSGT::dat[rt[nd]].sum);
    }
    return 0;
}

K-D Tree

解决 K 维问题 !

K-D Tree 类似于二叉搜索树, 建树选择一个维度对当前元素进行分割, 采用合适选择方法和优秀实现, 建树的时间复杂度为 $O(n \log n)$. 详情请 OI Wiki.

考虑到 K-D Tree 的结构, 插入采用类似替罪羊树的平衡方法, 如果有一个节点某一子树的大小超过限制, 就直接重构这个以这一节点为根的子树.

查询直接仿照二叉搜索树了, 注意到 K-D Tree 某些情况下可以剪枝, 可以多维护一些信息来排除掉一些子树.

可以证明, 在 $k$ 维情况下, 单次查询时间复杂度为 $O(n ^ {1 - \frac{1}{k}} + \log n )$.

不过值得注意的是, 这里的查询是类似于矩阵查询的偏序维护, 来个平面最近点对单次操作还是最劣 $O(n)$.

Luogu P4148 简单题

感觉 K-D Tree 的模板题, 没什么好说的, 把 K-D Tree 的操作汇总就好了.

然而我重构写挂了调了好久…

代码实现

> 点击显示 / 隐藏 
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
// Luogu P4148
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 2e5+5;
const double alpha = 0.725;

int n, nidx, root;
int x1, y1, x2, y2;
struct Point { int x, y, val; } A[MAXN];

namespace KDT {
    int ch[2][MAXN], d[MAXN], g[MAXN], t;
    int size[MAXN], datSum[MAXN], mnL[MAXN], mxR[MAXN], mnD[MAXN], mxU[MAXN];

    inline bool cmp1(const int& a, const int& b) { return A[a].x < A[b].x; }
    inline bool cmp2(const int& a, const int& b) { return A[a].y < A[b].y; }

    inline void maintain(int nd) {
        const int &lc = ch[0][nd], &rc = ch[1][nd];
        size[nd] = 1, datSum[nd] = A[nd].val;
        mnL[nd] = mxR[nd] = A[nd].x, mnD[nd] = mxU[nd] = A[nd].y;
        if (lc) {
            size[nd] += size[lc], datSum[nd] += datSum[lc];
            mnL[nd] = min(mnL[nd], mnL[lc]), mxR[nd] = max(mxR[nd], mxR[lc]);
            mnD[nd] = min(mnD[nd], mnD[lc]), mxU[nd] = max(mxU[nd], mxU[lc]);
        }
        if (rc) {
            size[nd] += size[rc], datSum[nd] += datSum[rc];
            mnL[nd] = min(mnL[nd], mnL[rc]), mxR[nd] = max(mxR[nd], mxR[rc]);
            mnD[nd] = min(mnD[nd], mnD[rc]), mxU[nd] = max(mxU[nd], mxU[rc]);
        }
    }

    int build(int L, int R) {
        if (L > R) return 0;
        int Mid = (L + R) / 2;
        double avx = 0, avy = 0, x = 0, y = 0;
        for (int i = L; i <= R; ++i) avx += A[g[i]].x, avy += A[g[i]].y;
        avx /= (R - L + 1.0), avy /= (R - L + 1.0);
        for (int i = L; i <= R; ++i) {
            x += (A[g[i]].x - avx) * (A[g[i]].x - avx);
            y += (A[g[i]].y - avy) * (A[g[i]].y - avy);
        }
        if (x > y)
            nth_element(g+L, g+Mid, g+R+1, cmp1), d[g[Mid]] = 1;
        else
            nth_element(g+L, g+Mid, g+R+1, cmp2), d[g[Mid]] = 2;
        ch[0][g[Mid]] = build(L, Mid-1), ch[1][g[Mid]] = build(Mid+1, R);
        return maintain(g[Mid]), g[Mid];
    }

    void dfs(int nd) {
        if (!nd) return;
        if (ch[0][nd]) dfs(ch[0][nd]);
        g[++t] = nd;
        if (ch[1][nd]) dfs(ch[1][nd]);
    }

    void rebuild(int& nd) {
        t = 0, dfs(nd), nd = build(1, t);
    }

    inline bool canrb(int nd) {
        return alpha * size[nd] <= max(size[ch[0][nd]], size[ch[1][nd]]);
    }

    void Ins(int& nd, const int& pos) {
        if (!nd) { nd = pos, maintain(nd); return; }
        if (d[nd] == 1) {
            if (A[pos].x <= A[nd].x) Ins(ch[0][nd], pos);
            else Ins(ch[1][nd], pos);
        } else {
            if (A[pos].y <= A[nd].y) Ins(ch[0][nd], pos);
            else Ins(ch[1][nd], pos);
        }
        maintain(nd);
        if (canrb(nd)) rebuild(nd);
    }

    int Qry(int nd) {
        if (!nd || x1 > mxR[nd] || x2 < mnL[nd] || y1 > mxU[nd] || y2 < mnD[nd])
            return 0;
        if (x1 <= mnL[nd] && mxR[nd] <= x2 && y1 <= mnD[nd] && mxU[nd] <= y2)
            return datSum[nd];
        if (x1 <= A[nd].x && A[nd].x <= x2 && y1 <= A[nd].y && A[nd].y <= y2)
            return Qry(ch[0][nd]) + Qry(ch[1][nd]) + A[nd].val;
        return Qry(ch[0][nd]) + Qry(ch[1][nd]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("11.in", "r", stdin);
#endif
    read(n);
    int opt, val, lastans = 0;
    while (read(opt), opt != 3) {
        if (opt == 1) {
            read(x1), read(y1), read(val);
            x1 ^= lastans, y1 ^= lastans, val ^= lastans;
            A[++nidx] = (Point){ x1, y1, val };
            KDT::Ins(root, nidx);
        }
        if (opt == 2) {
            read(x1), read(y1), read(x2), read(y2);
            x1 ^= lastans, y1 ^= lastans, x2 ^= lastans, y2 ^= lastans;
            printf("%d\n", lastans = KDT::Qry(root));
        }
    }
    return 0;
}

Luogu P5471 [NOI2019] 弹跳

如果直接用 K-D Tree 建图, 如果用四分树甚至可以 AC, 可以收获 88 pts 的好成绩

卡卡常可以卡过? 为什么不尝试更快的做法呢…

这个写法似乎在 UOJ 被叉掉了 (

那么怎么做呢? 考虑模拟 Dijkstra 的过程, 把这个 K-D Tree 当成堆使用, 记录子树内最小路径长度 (用于更新答案), 以及最大路径长度 (用于剪枝).

具体地说, 因为每个点的最短距离只会被更新一次, 所以 K-D Tree 要维护

  1. 当前子树覆盖矩阵范围
  2. 当前节点到起点的最短路, 视作当前点的权值
  3. 子树内最小权值, 用于查找节点及更新答案
  4. 当前节点是否被更新过, 换言之, 在 Dijkstra 维护的点集中是否被删去

另外有一个剪枝: 维护一个子树内最大权值, 这样在修改值 (也就是一个矩阵内更新最小值) 的时候遇到 “最大值比修改值还要小” 的情况就可以剪枝.

还有一些细节, 在修改整块矩阵的时候打一个类似于线段树的标记, 以及对于已删除节点值的情况要注意分类讨论.

代码实现

> 点击显示 / 隐藏 
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
173
174
// Luogu P5471
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 7e4+5, MAXM = 15e4, MAXD = 2;
const int INF = 0x3f3f3f3f;

struct Point {
    int x[MAXD], idx;
    int& operator[] (const int& i) { return x[i]; }
} A[MAXN];

int n, m, W, H;
int pos[MAXN];

namespace KDT {
    int ch[2][MAXN], mn[MAXD][MAXN], mx[MAXD][MAXN];
    bool vis[MAXN];
    int tag[MAXN], datMin[MAXN], datMax[MAXN], datVal[MAXN];

    inline void maintain(const int& nd) {
        const int &lc = ch[0][nd], &rc = ch[1][nd];
        if (vis[nd]) {
            datMin[nd] = INF, datMax[nd] = -INF;
            for (int d = 0; d < MAXD; ++d) mn[d][nd] = INF, mx[d][nd] = -INF;
        } else {
            datMin[nd] = datMax[nd] = datVal[nd];
            for (int d = 0; d < MAXD; ++d) mn[d][nd] = mx[d][nd] = A[nd][d];
        }
        if (lc) {
            datMin[nd] = min(datMin[nd], datMin[lc]);
            datMax[nd] = max(datMax[nd], datMax[lc]);
            for (int d = 0; d < MAXD; ++d) {
                mn[d][nd] = min(mn[d][nd], mn[d][lc]);
                mx[d][nd] = max(mx[d][nd], mx[d][lc]);
            }
        }
        if (rc) {
            datMin[nd] = min(datMin[nd], datMin[rc]);
            datMax[nd] = max(datMax[nd], datMax[rc]);
            for (int d = 0; d < MAXD; ++d) {
                mn[d][nd] = min(mn[d][nd], mn[d][rc]);
                mx[d][nd] = max(mx[d][nd], mx[d][rc]);
            }
        }
    }

    void pushTag(const int& nd, const int& val) {
        if (val >= datMax[nd] || val >= tag[nd]) return;
        datMax[nd] = tag[nd] = val;
        datMin[nd] = min(datMin[nd], val);
        if (!vis[nd]) datVal[nd] = min(datVal[nd], val);
    }
    void pushdown(int nd) {
        if (!nd || tag[nd] == INF) return;
        const int &lc = ch[0][nd], &rc = ch[1][nd];
        if (lc) pushTag(lc, tag[nd]);
        if (rc) pushTag(rc, tag[nd]);
        tag[nd] = INF;
    }

    inline bool cmp0(const Point& a, const Point& b) { return a.x[0] < b.x[0]; }
    inline bool cmp1(const Point& a, const Point& b) { return a.x[1] < b.x[1]; }

    int build(int L, int R) {
        if (L > R) return 0;
        int Mid = (L + R) / 2;
        double avx = 0, avy = 0, x = 0, y = 0;
        for (int i = L; i <= R; ++i) avx += A[i][0], avy += A[i][1];
        avx /= (R - L + 1.0), avy /= (R - L + 1.0);
        for (int i = L; i <= R; ++i) {
            x += (avx - A[i][0]) * (avx - A[i][0]);
            y += (avy - A[i][1]) * (avy - A[i][1]);
        }
        if (x > y) nth_element(A + L, A + Mid, A + R + 1, cmp0);
        else nth_element(A + L, A + Mid, A + R + 1, cmp1);
        pos[Mid] = A[Mid].idx;
        tag[Mid] = INF, datVal[Mid] = (pos[Mid] == 1)? 0: INF;
        ch[0][Mid] = build(L, Mid-1), ch[1][Mid] = build(Mid+1, R);
        return maintain(Mid), Mid;
    }

    void Mdy(int nd, const int& val,
            const int& L, const int& R, const int& D, const int& U) {
        pushdown(nd);
        if (datMax[nd] <= val) return;
        if (L > mx[0][nd] || R < mn[0][nd] || D > mx[1][nd] || U < mn[1][nd]) return;
        if (L <= mn[0][nd] && mx[0][nd] <= R && D <= mn[1][nd] && mx[1][nd] <= U)
            return pushTag(nd, val);
        if (!vis[nd] && L <= A[nd][0] && A[nd][0] <= R && D <= A[nd][1] && A[nd][1] <= U)
            datVal[nd] = min(datVal[nd], val);
        if (ch[0][nd]) Mdy(ch[0][nd], val, L, R, D, U);
        if (ch[1][nd]) Mdy(ch[1][nd], val, L, R, D, U);
        maintain(nd);
    }

    int Qry(int nd, const int& val) {
        pushdown(nd);
        if (!vis[nd] && datVal[nd] == val) {
            vis[nd] = true;
            return maintain(nd), nd;
        }
        if (ch[0][nd] && datMin[ch[0][nd]] == val) {
            int ret = Qry(ch[0][nd], val);
            return maintain(nd), ret;
        } else {
            int ret = Qry(ch[1][nd], val);
            return maintain(nd), ret;
        }
    }
}

namespace Graph {
    struct Edge { int L, R, D, U, w; }; 
    vector<Edge> G[MAXN];
    int dist[MAXN];

    inline void AddEdge(int from, int L, int R, int D, int U, int w) {
        G[from].push_back((Edge){ L, R, D, U, w });
    }

    void Dijkstra() {
        int root = KDT::build(1, n);
        for (int i = 1; i <= n; ++i) {
            int nd = KDT::Qry(root, KDT::datMin[root]);
            int u = pos[nd];
            dist[u] = KDT::datVal[nd];
            for (size_t k = 0; k < G[u].size(); ++k) {
                const Edge& e = G[u][k];
                KDT::Mdy(root, dist[u] + e.w, e.L, e.R, e.D, e.U);
            }
        }
        for (int i = 2; i <= n; ++i) printf("%d\n", dist[i]);
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m), read(W), read(H);
    for (int i = 1; i <= n; ++i)
        A[i].idx = i, read(A[i][0]), read(A[i][1]);
    for (int i = 1; i <= m; ++i) {
        static int p, w, L, R, D, U;
        read(p), read(w), read(L), read(R), read(D), read(U);
        Graph::AddEdge(p, L, R, D, U, w);
    }
    // solve
    Graph::Dijkstra();
    return 0;
}

树套树

字面意思, 嵌套数据结构.

带有巨大常数, 占用大量空间.

Luogu P3380【模板】二逼平衡树（树套树）

采用线段树套平衡树的方法, 为了好写一些, 内层平衡树我选择了 无旋 Treap.

  1. $k$ 在区间内的排名

    把区间丢到线段树上处理, 把区间拆分后得到的排名相加即可. 单次操作时间复杂度 $O(\log^2 n)$

    注意一些细节: 数值 $k$ 可能在区间内的贡献可能被计算多次, 所以每次查询内层平衡树时把得到的排名 $-1$, 最后得出答案时再把自己加上.

  2. 查询区间内排名为 $k$ 的值

    这个问题在普通的平衡树上可以通过二分解决, 但是在多棵平衡树的情况下进行二分好像很困难…

    所以直接采用二分值域的方式, 判断当前二分的值是否在区间内排名为 $k$, 单次操作时间复杂度 $O(\log ^3 n)$.

    (好像在多个 Trie 上二分很可做, 或者用树状数组套 Trie 来维护, 可以做到 $O(\log ^2 n)$, 还没写过, 值得尝试)

  3. 修改某一位值上的数值

    在线段树上跑一遍单点修改的操作, 沿途把原来的值删除, 再把修改的值加入就好了. 时间复杂度 $O(\log^2 n)$.

  4. 查询 $k$ 在区间内的前驱

  5. 查询 $k$ 在区间内的后继

    也是把区间丢到线段树上, 注意把前驱取 $\max$, 后缀取 $\min$. 时间复杂度 $O(\log^2 n)$

代码实现

只有靠 O2 才勉强续命的样子.

> 点击显示 / 隐藏 
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
173
174
// Luogu P3380
// DeP
#include <ctime>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 5e4+5;

int n, m;
int A[MAXN];

namespace Treap {
    const int MAXN = ::MAXN << 5;
    int ch[2][MAXN], size[MAXN], rnd[MAXN], val[MAXN], nidx;

    inline void maintain(int nd) {
        size[nd] = 1;
        if (ch[0][nd]) size[nd] += size[ch[0][nd]];
        if (ch[1][nd]) size[nd] += size[ch[1][nd]];
    }

    inline int newnode(int v) {
        return val[++nidx] = v, size[nidx] = 1, rnd[nidx] = rand(), nidx;
    }

    void split(int nd, const int& k, int& x, int& y) {
        if (!nd) return void( x = y = 0 );
        if (val[nd] <= k) x = nd, split(ch[1][nd], k, ch[1][nd], y);
        else y = nd, split(ch[0][nd], k, x, ch[0][nd]);
        maintain(nd);
    }
    int merge(int x, int y) {
        if (!x || !y) return x + y;
        if (rnd[x] < rnd[y]) return ch[1][x] = merge(ch[1][x], y), maintain(x), x;
        return ch[0][y] = merge(x, ch[0][y]), maintain(y), y;
    }

    inline void insert(int& root, int v) {
        static int x, y; x = y = 0;
        split(root, v, x, y), root = merge(merge(x, newnode(v)), y);
    }
    inline void remove(int& root, int v) {
        static int x, y, z; x = y = z = 0;
        split(root, v, x, z), split(x, v-1, x, y);
        y = merge(ch[0][y], ch[1][y]), root = merge(merge(x, y), z);
    }

    inline int Rnk(int& root, int v) {
        static int x, y, ret; x = y = ret = 0;
        return split(root, v-1, x, y), ret = size[x] + 1, root = merge(x, y), ret;
    }
    inline int Kth(int nd, int k) {
        while (nd) {
            int t = ch[0][nd]? size[ch[0][nd]] + 1: 1;
            if (k == t) return nd;
            if (k > t) k -= t, nd = ch[1][nd];
            else nd = ch[0][nd];
        }
        abort();
    }

    inline int Pre(int& root, int v) {
        static int x, y, ret; x = y = ret = 0;
        return split(root, v-1, x, y), ret = x? val[Kth(x, size[x])]: -INT_MAX, root = merge(x, y), ret;
    }
    inline int Suf(int& root, int v) {
        static int x, y, ret; x = y = ret = 0;
        return split(root, v, x, y), ret = y? val[Kth(y, 1)]: INT_MAX, root = merge(x, y), ret;
    }

    void dfs(int u) {
        if (ch[0][u]) dfs(ch[0][u]);
        printf("%d ", val[u]);
        if (ch[1][u]) dfs(ch[1][u]);
    }
}

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
#define Mid ((L + R) / 2)
    int rt[MAXN << 2];

    void build(int nd, int L, int R) {
        for (int i = L; i <= R; ++i) Treap::insert(rt[nd], A[i]);
        if (L == R) return;
        build(lc, L, Mid), build(rc, Mid+1, R);
    }

    void Mdy(int nd, int L, int R, const int& pos, const int& val) {
        Treap::remove(rt[nd], A[pos]), Treap::insert(rt[nd], val);
        if (L == R) return;
        if (pos <= Mid) Mdy(lc, L, Mid, pos, val);
        else Mdy(rc, Mid+1, R, pos, val);
    }

    int Rnk(int nd, int L, int R, const int& opL, const int& opR, const int& val) {
        if (opL <= L && R <= opR) return Treap::Rnk(rt[nd], val) - 1;
        if (opR <= Mid) return Rnk(lc, L, Mid, opL, opR, val);
        if (opL > Mid) return Rnk(rc, Mid+1, R, opL, opR, val);
        return Rnk(lc, L, Mid, opL, opR, val) + Rnk(rc, Mid+1, R, opL, opR, val);
    }
    inline int Kth(const int& opL, const int& opR, const int& k) {
        int L = 0, R = 1e8, ret = -1;
        while (L <= R) {
            if (Rnk(1, 1, n, opL, opR, Mid) + 1 <= k) ret = Mid, L = Mid + 1;
            else R = Mid - 1;
        }
        return ret;
    }

    int Pre(int nd, int L, int R, const int& opL, const int& opR, const int& val) {
        if (opL <= L && R <= opR) return Treap::Pre(rt[nd], val);
        if (opR <= Mid) return Pre(lc, L, Mid, opL, opR, val);
        if (opL > Mid) return Pre(rc, Mid+1, R, opL, opR, val);
        return max(Pre(lc, L, Mid, opL, opR, val), Pre(rc, Mid+1, R, opL, opR, val));
    }
    int Suf(int nd, int L, int R, const int& opL, const int& opR, const int& val) {
        if (opL <= L && R <= opR) return Treap::Suf(rt[nd], val);
        if (opR <= Mid) return Suf(lc, L, Mid, opL, opR, val);
        if (opL > Mid) return Suf(rc, Mid+1, R, opL, opR, val);
        return min(Suf(lc, L, Mid, opL, opR, val), Suf(rc, Mid+1, R, opL, opR, val));
    }
#undef lc
#undef rc
#undef Mid
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    srand( time(nullptr) );
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) read(A[i]);
    // solve
    SGT::build(1, 1, n);
    // output
    while (m--) {
        static int opt, L, R, K;
        read(opt), read(L), read(R); if (opt != 3) read(K);
        switch (opt) {
            case 1: printf("%d\n", SGT::Rnk(1, 1, n, L, R, K) + 1); break;
            case 2: printf("%d\n", SGT::Kth(L, R, K)); break;
            case 3: SGT::Mdy(1, 1, n, L, R), A[L] = R; break;
            case 4: printf("%d\n", SGT::Pre(1, 1, n, L, R, K)); break;
            case 5: printf("%d\n", SGT::Suf(1, 1, n, L, R, K)); break;
            default: fprintf(stderr, "ERR\n");
        }
    }
    return 0;
}

Luogu P3332 [ZJOI2013] K 大数查询

大概是权值线段树套普通线段树 ?

话说这种直接给出操作的数据结构应该是几年前的画风吧 ?

首先对题意进行转化, 将加入的元素看作一个带有两种属性的元素, 那么操作 1 就是加入 $(l, c), (l+1, c), \ldots, (r, c)$ 这些点, 操作 2 就是查询第一个属性 $a$ 满足 $l \le a \le r$ 的点集中第 $k$ 大.

于是就可以很自然地联想到树套树了. 但是区间加入一个数的操作不好实现, 所以就有了一个朴素的想法: 在外层线段树上维护权值, 在内层维护位置.

现在的问题就很明朗了:

  • 对于操作 1: 在外层线段树单点插入一个值, 并在这个位置对应的线段树区间加 1, 表明这个位置加入值了.

    注意到代码中使用了 “标记永久化” 的技巧, 这样会比每次下传标记要快, 但是我要卡常为什么不直接写整体二分呢?

    单次操作时间复杂度 $O(\log^2 n)$.

  • 对于操作 2: 在外层线段树上二分, 和普通权值线段树的操作没什么大的差别, 只是查询子树大小的 $O(\log n)$ 而已…

    单次操作时间复杂度 $O(\log^2 n)$.

代码实现

活在 O2, 以及被整体二分吊打的空气之下 = =.

> 点击显示 / 隐藏 
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
// Luogu P3332
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

typedef long long LL;
const int MAXN = 5e4+5;

struct Ask {
    int opt, L, R; LL c;
} Q[MAXN];

int n, m;
LL B[MAXN], nB;

namespace DSGT {
    const int MAXN = ::MAXN * 17 * 17;
    int lc[MAXN], rc[MAXN], nidx;
    LL datSum[MAXN], tagAdd[MAXN];

    inline int calc(int l1, int r1, int l2, int r2) {
        if (max(l1, l2) > min(r1, r2)) return 0;
        return min(r1, r2) - max(l1, l2) + 1;
    }

    void Mdy(int nd, int L, int R, const int& opL, const int& opR) {
        // 标记永久化
        datSum[nd] += calc(L, R, opL, opR);
        if (opL <= L && R <= opR) return void( ++tagAdd[nd] );
        // 内层线段树需要动态开点, 空间复杂度 O(n log^2 n)
        if (!lc[nd]) lc[nd] = ++nidx;
        if (!rc[nd]) rc[nd] = ++nidx;
        int Mid = (L + R) / 2;
        if (opL <= Mid) Mdy(lc[nd], L, Mid, opL, opR);
        if (opR > Mid) Mdy(rc[nd], Mid+1, R, opL, opR);
    }

    LL Qry(int nd, int L, int R, const int& opL, const int& opR, const int& tag = 0) {
        // 标记永久化
        if (opL <= L && R <= opR) return datSum[nd] + tag * (R-L+1);
        int Mid = (L + R) / 2, ret = 0;
        if (opL <= Mid) ret += Qry(lc[nd], L, Mid, opL, opR, tag + tagAdd[nd]);
        if (opR > Mid) ret += Qry(rc[nd], Mid+1, R, opL, opR, tag + tagAdd[nd]);
        return ret;
    }
}

namespace SGT {
#define lc (nd<<1)
#define rc (nd<<1|1)
    int rt[MAXN << 2];
    
    void Mdy(int nd, int L, int R, const int& opL, const int& opR, const int& pos) {
        if (!rt[nd]) rt[nd] = ++DSGT::nidx;
        DSGT::Mdy(rt[nd], 1, n, opL, opR);
        if (L == R) return;
        int Mid = (L + R) / 2;
        if (pos <= Mid) Mdy(lc, L, Mid, opL, opR, pos);
        else Mdy(rc, Mid+1, R, opL, opR, pos);
    }

    int Kth(int nd, int L, int R, const int& opL, const int& opR, const LL& k) {
        if (L == R) return L;
        int Mid = (L + R) / 2;
        LL d = DSGT::Qry(rt[rc], 1, n, opL, opR);
        if (k <= d) return Kth(rc, Mid+1, R, opL, opR, k);
        return Kth(lc, L, Mid, opL, opR, k - d);
    }
#undef lc
#undef rc
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int i = 1; i <= m; ++i) {
        static int opt, L, R; static LL c;
        read(opt), read(L), read(R), read(c);
        Q[i] = (Ask){ opt, L, R, c };
        if (opt == 1) B[++nB] = c;
    }
    // solve
    sort(B+1, B+1+nB);
    nB = unique(B+1, B+1+nB) - B - 1;
    // 需要丢到权值线段树里, 随手离散化
    for (int i = 1; i <= m; ++i)
        if (Q[i].opt == 1) Q[i].c = lower_bound(B+1, B+1+nB, Q[i].c) - B;
    // output
    for (int i = 1; i <= m; ++i) {
        const Ask& q = Q[i];
        switch (q.opt) {
            case 1: SGT::Mdy(1, 1, nB, q.L, q.R, q.c); break;
            case 2: printf("%lld\n", B[SGT::Kth(1, 1, nB, q.L, q.R, q.c)]); break;
            default: fprintf(stderr, "ERR\n");
        }
    }
    return 0;
}

Luogu P3759 [TJOI2017] 不勤劳的图书管理员

带权动态逆序对.

题外话: 这题有点题意杀, 不过模拟一遍样例就好了

仍然使用上一题的转化思路, 题目所求即为 $n$ 个带有两种属性的元素 $(a_i, b_i)$ 中满足 $a_i < a_j$ 且 $b_i > b_j$ 的元素对权值和.

交换位置的操作可以看作删除两个元素后加入两个新元素, 所以问题的关键在于加入 / 删除元素对答案的影响.

每次查询一个元素 $(a, b)$ 的影响, 对这个元素有贡献的, 一定满足:

  • 第一维 $< a$, 第二维 $> b$

  • 第一维 $> a$, 第二维 $< b$

由于记录信息具有可减性, 采用树状数组套权值线段树实现.

代码实现

> 点击显示 / 隐藏 
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
// Luogu P3759
// DeP
#include <cctype>
#include <cstdio>
#include <cassert>
#include <algorithm>
using namespace std;

namespace IO {
    const int MAXSIZE = 1 << 18 | 1;
    char buf[MAXSIZE], *p1, *p2;

    inline int Gc() {
        return p1 == p2 &&
            (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
    }
    template<typename T> inline void read(T& x) {
        x = 0; int f = 0, ch = Gc();
        while (!isdigit(ch)) f |= ch == '-', ch = Gc();
        while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
        if (f) x = -x;
    }
}
using IO::read;

const int MAXN = 5e4+5, P = 1e9+7;

int n, m, ans;
int A[MAXN], v[MAXN];

namespace SGT {
    const int MAXN = ::MAXN * 16 * 16;
    struct Node {
        int size, sum;
        Node() { size = sum = 0; }
        Node(int _s, int _v): size(_s), sum(_v) { }
        Node operator + (const Node& rhs) const {
            return Node((size + rhs.size) % P, (sum + rhs.sum) % P);
        }
    } dat[MAXN];
    int lc[MAXN], rc[MAXN], nidx;

    int Mdy(int nd, int L, int R, const int& pos, const int& val, const int& type) {
        if (!nd) nd = ++nidx;
        dat[nd].size = (dat[nd].size + 1LL * type) % P;
        dat[nd].sum = (dat[nd].sum + 1LL * type * val) % P;
        if (L == R) return nd;
        int Mid = (L + R) / 2;
        if (pos <= Mid) lc[nd] = Mdy(lc[nd], L, Mid, pos, val, type);
        else rc[nd] = Mdy(rc[nd], Mid+1, R, pos, val, type);
        return nd;
    }

    Node Qry(int nd, int L, int R, const int& opL, const int& opR) {
        if (opL <= L && R <= opR) return dat[nd];
        if (!nd) return Node(0, 0);
        int Mid = (L + R) / 2;
        if (opR <= Mid) return Qry(lc[nd], L, Mid, opL, opR);
        if (opL > Mid) return Qry(rc[nd], Mid+1, R, opL, opR);
        return Qry(lc[nd], L, Mid, opL, opR) + Qry(rc[nd], Mid+1, R, opL, opR);
    }
}

namespace BIT {
    using SGT::Node;
    int rt[MAXN];

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

    inline void Mdy(const int& d1, const int& d2, const int& val, const int& type) {
        for (int i = d1; i <= n; i += lowbit(i))
            rt[i] = SGT::Mdy(rt[i], 1, n, d2, val, type);
    }

    inline int Qry(const int& d1, const int& d2, const int& val) {
        int ret = 0;
        for (int i = d1; i; i -= lowbit(i)) {
            Node tmp = SGT::Qry(rt[i], 1, n, d2, n);
            ret = (ret + tmp.sum + 1LL * val * tmp.size) % P;
        }
        for (int i = n; i; i -= lowbit(i)) {
            Node tmp = SGT::Qry(rt[i], 1, n, 1, d2);
            ret = (ret + tmp.sum + 1LL * val * tmp.size) % P;
        }
        for (int i = d1; i; i -= lowbit(i)) {
            Node tmp = SGT::Qry(rt[i], 1, n, 1, d2);
            ret = (ret - (tmp.sum + 1LL * val * tmp.size) % P + P) % P;
        }
        return ret;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.in", "r", stdin);
#endif
    // input
    read(n), read(m);
    for (int i = 1; i <= n; ++i) {
        read(A[i]), read(v[i]);
        ans = (ans + BIT::Qry(i, A[i], v[i])) % P;
        BIT::Mdy(i, A[i], v[i], 1);
    }
    // solve
    while (m--) {
        static int L, R;
        read(L), read(R);
        // remove
        ans = (ans - BIT::Qry(L, A[L], v[L]) + P) % P;
        BIT::Mdy(L, A[L], v[L], -1);
        ans = (ans - BIT::Qry(R, A[R], v[R]) + P) % P;
        BIT::Mdy(R, A[R], v[R], -1);
        swap(A[L], A[R]), swap(v[L], v[R]);
        // add
        BIT::Mdy(L, A[L], v[L], 1);
        ans = (ans + BIT::Qry(L, A[L], v[L])) % P;
        BIT::Mdy(R, A[R], v[R], 1);
        ans = (ans + BIT::Qry(R, A[R], v[R])) % P;
        printf("%d\n", ans);
    }
    return 0;
}

数据结构还是学不明白啊, 真是活该退役.png

UPD on 2020.2.27

参考资料

  1. nzhtl1477, 简单数据结构
  2. __stdcall, 简易 CDQ 分治教程 & 学习笔记
  3. Owen_codeisking, [学习笔记] CDQ 分治和整体二分
© 2019-2023 DepletedPrism's Blog - Powered by Hexo - Theme Chan