2025 Summer Day3

Content： Data structs

Date：2025.7.19

内容

三维偏序问题
CDQ分治
整体二分
分块
莫队算法

具体内容

三维偏序问题

问题描述

给定一些三元组 $(a_i, b_i, c_i)$ ，询问对于三元组 $(a_j, b_j, c_j)$ ，有多少个三元组满足 $a_i \le a_j$ 且 $b_i \le b_j$ 且 $c_i \le c_j$ 。

首先对于这个问题，我们考虑先去重，然后排序。排序规则如下：

如果 $a_i \ne a_j$ ，则返回 $a_i < a_j$
如果 $b_i \ne b_j$ ，则返回 $b_i < b_j$
否则返回 $c_i < c_j$

这样我们就把 $a_i < a_j$ 的条件去掉了。

接下来我们考虑分治，定义函数 $solve(l, r)$ 表示当前解决到了区间 $[l, r]$ ，取其中点 $mid$ ，将原序列的问题转化为三个部分：

$j < i \le mid$ ，由 $solve(l, mid)$ 解决。
$mid < j < i$ ，由 $solve(mid + 1, r)$ 解决。
$j \le mid < i$ ，即被 $mid$ 分成了两个部分。

对于第三种情况，我们需要解决的是如下问题：

问题描述

在区间 $[l,r]$ 中，有多少对二元组 $(i, j)$ （其中 $i \ne j$ ）满足 $b_i < b_j$ 且 $c_i < c_j$ 。

可见问题转化为了二维偏序问题，用线段树解决就可以。

整体二分

普通的二分操作是直接对于每个询问二分答案，判断答案是否合法。整体二分的思路是将所有询问一起二分，根据二分的答案对询问进行分类，再逐步求解。

洛谷 P3332 题目描述

你需要维护 n 个可重整数集，集合的编号从 1 到 n。
这些集合初始都是空集，有 m 个操作：

1 l r c：表示将 c 加入到编号在 $[l,r]$ 内的集合中
2 l r c：表示查询编号在 $[l,r]$ 内的集合的并集中，第 c 大的数是多少。

注意可重集的并是不去除重复元素的，如 $\set{1,1,4} \cup \set{5,1,4}=\set{1,1,4,5,1,4}$ 。

我们还是定义 $solve(l, r, ql, qr)$ 表示当前答案区间为 $[l, r]$ ，处理的操作区间为 $[ql, qr]$ ，取答案中点 $mid$ 。将操作分为如下四类

如果当前操作是修改（ $op = 1$ $o p = 1$ ）
- 如果 $c \le mid$ ：归为 $A$ 类，由左递归处理。
如果 $c > mid$ ：归为 $B$ 类，由右递归处理，且用树状数组维护当前比 $mid$ 大的数的个数（差分）。
如果当前操作是查询（ $op = 2$ $o p = 2$ ）
- 如果 $c \le mid$ ：归为 $A$ 类，由左递归处理。
- 如果 $c > mid$ ：归为 $B$ 类，由右递归处理，并调整 $c$ 的值，以保证结果正确性。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e6 + 5;
6
struct Node {
7
  int l, r, k;
8
} q[N];
9
int pos[N], cnt[N], a[N], ans = 0, rec[N];
10
int n, m;
11

12
bool cmp(Node a, Node b) {
13
  if (pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
14
  if (pos[a.l] & 1) return a.r > b.r;
15
  return a.r < b.r;
16
}
17

18
void add(int x) {
19
  cnt[a[x]]++;
20
  if (cnt[a[x]] == 1) ans++;
21
}
22

23
void del(int x) {
24
  cnt[a[x]]--;
25
  if (cnt[a[x]] == 0) ans--;
26
}
27

28
int main() {
29
  cin >> n;
30

31
  int block = sqrt(n);
32

33
  for (int i = 1; i <= n; i++) {
34
    cin >> a[i];
35
    pos[i] = (i - 1) / block + 1;
36
  }
37

38
  cin >> m;
39

40
  for (int i = 1; i <= m; i++) {
41
    cin >> q[i].l >> q[i].r;
42
    q[i].k = i;
43
  }
44

45
  sort(q + 1, q + m + 1, cmp);
46

47
  int L = 1, R = 0;
48

49
  for (int i = 1; i <= m; i++) {
50
    while (L < q[i].l) {
51
      del(L);
52
      L++;
53
    }
54
    while (R > q[i].r) {
55
      del(R);
56
      R--;
57
    }
58
    while (L > q[i].l) {
59
      L--;
60
      add(L);
61
    }
62
    while (R < q[i].r) {
63
      R++;
64
      add(R);
65
    }
66

67
    rec[q[i].k] = ans;
68
  }
69

70
  for (int i = 1; i <= m; i++) cout << rec[i] << endl;
71

72
  return 0;
73
}

莫队算法

莫队

莫队算法即为优美的暴力，根据分块对询问排序，然后维护双指针统计答案。

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e6 + 5;
6
struct Node {
7
  int l, r, k;
8
}q[N];
9
int pos[N], cnt[N], a[N], ans = 0, rec[N];
10
int n, m;
11

12
bool cmp(Node a, Node b) {
13
  if(pos[a.l] != pos[b.l]) return pos[a.l] < pos[b.l];
14
  if(pos[a.l] & 1) return a.r > b.r;
15
  return a.r < b.r;
16
}
17

18
void add(int x) {
19
  cnt[a[x]] ++;
20
  if(cnt[a[x]] == 1) ans ++;
21
}
22

23
void del(int x) {
24
  cnt[a[x]] --;
25
  if(cnt[a[x]] == 0) ans --;
26
}
27

28
int main() {
29
  cin >> n;
30

31
  int block = sqrt(n);
32

33
  for(int i = 1; i <= n; i ++) {
34
    cin >> a[i];
35
    pos[i] = (i - 1) / block + 1;
36
  }
37

38
  cin >> m;
39

40
  for(int i = 1; i <= m; i ++) {
41
    cin >> q[i].l >> q[i].r;
42
    q[i].k = i;
43
  }
44

45
  sort(q + 1, q + m + 1, cmp);
46

47
  int L = 1, R = 0;
48

49
  for(int i = 1; i <= m; i ++) {
50
    while(L < q[i].l) {
51
      del(L);
52
      L ++;
53
    }
54
    while(R > q[i].r) {
55
      del(R);
56
      R --;
57
    }
58
    while(L > q[i].l) {
59
      L --;
60
      add(L);
61
    }
62
    while(R < q[i].r) {
63
      R ++;
64
      add(R);
65
    }
66

67
    rec[q[i].k] = ans;
68
  }
69

70
  for(int i = 1; i <= m; i ++) cout << rec[i] << endl;
71

72
  return 0;
73
}

带修莫队

在普通莫队的基础上维护修改操作的时间戳 $t$ ，每次移动左右端点时同时维护修改操作，根据询问的时间戳同步修改/撤销操作。

洛谷 P1903

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
const int N = 1e6 + 5;
6
int a[N], ans[N], pos[N];
7
int L[N], R[N];
8
int cnt[N];
9

10
struct query {
11
  int L, R, time, id;
12
} ask[N];
13

14
struct modify {
15
  int pos, color, last;
16
} c[N];
17

18
int cntq, cntc, n, m, block, num;
19
int times, now;
20

21
bool cmp(query a, query b) {
22
  bool ret = false;
23

24
  if (pos[a.L] ^ pos[b.L]) {
25
    ret = pos[a.L] < pos[b.L];
26
  } else if (pos[a.R] ^ pos[b.R]) {
27
    ret = pos[a.R] < pos[b.R];
28
  } else {
29
    ret = a.time < b.time;
30
  }
31

32
  return ret;
33
}
34

35
void add(int x) {
36
  int val = a[x];
37
  if (!cnt[val]) now++;
38
  cnt[val]++;
39
}
40

41
void del(int x) {
42
  int val = a[x];
43
  cnt[val]--;
44
  if (!cnt[val]) now--;
45
}
46

47
void change() {
48
  int P = c[times].pos;
49
  cnt[a[P]]--;
50
  if (!cnt[a[P]]) now--;
51

52
  int COL = c[times].color;
53
  if (!cnt[COL]) now++;
54
  cnt[COL]++;
55
}
56

57
int main() {
58
  cin >> n >> m;
59

60
  block = pow(n, 2.0 / 3.0);
61

62
  num = ceil((double)n / block);
63

64
  for (int i = 1; i <= num; i++) {
65
    L[i] = (i - 1) * block + 1;
66
    R[i] = i * block;
67
  }
68

69
  for (int i = 1; i <= num; i++) {
70
    for (int j = L[i]; j <= R[i]; j++) {
71
      pos[j] = i;
72
    }
73
  }
74

75
  for (int i = 1; i <= n; i++) {
76
    cin >> a[i];
77
  }
78

79
  for (int i = 1; i <= m; i++) {
80
    string opt;
81
    cin >> opt;
82

83
    if (opt[0] == 'Q') {
84
      cntq++;
85

86
      cin >> ask[cntq].L >> ask[cntq].R;
87

88
      ask[cntq].time = cntc;
89
      ask[cntq].id = cntq;
90
    } else if (opt[0] == 'R') {
91
      cntc++;
92

93
      cin >> c[cntc].pos >> c[cntc].color;
94
    }
95
  }
96

97
  sort(ask + 1, ask + cntq + 1, cmp);
98

99
  int left = 1, right = 0;
100
  times = 0;
101
  now = 0;
102

103
  for (int i = 1; i <= cntq; i++) {
104
    int ql = ask[i].L, qr = ask[i].R, qt = ask[i].time;
105

106
    while (left < ql) del(left++);
107
    while (left > ql) add(--left);
108
    while (right < qr) add(++right);
109
    while (right > qr) del(right--);
110

111
    while (times < qt) {
112
      times++;
113
      if (ql <= c[times].pos && c[times].pos <= qr) {
114
        change();
115
      }
116

117
      swap(a[c[times].pos], c[times].color);
118
    }
119

120
    while (times > qt) {
121
      if (ql <= c[times].pos && c[times].pos <= qr) {
122
        change();
123
      }
124
      swap(a[c[times].pos], c[times].color);
125
      times--;
126
    }
127

128
    ans[ask[i].id] = now;
129
  }
130

131
  for (int i = 1; i <= cntq; i++) {
132
    cout << ans[i] << endl;
133
  }
134

135
  return 0;
136
}

回滚莫队

即每次操作后都将左指针回退到分块的左端点，然后再进行下一次操作。