0%

CDQ分治 & 整体二分 学习笔记

qwq


CDQ 分治

能用 CDQ 分治 解决的问题都是离线问题。

主要思路是令 $solve(l, r)$ 为解决 $[l, r]$ 这区间内的询问,则先 $solve(l, mid), solve(mid + 1, r)$ ,再判断 $[l, mid]$ 这段区间对 $[mid + 1, r]$ 这段区间的影响。

不妨通过模板题来审视一下这个东西到底是啥。

三维偏序

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
#include <bits/stdc++.h>

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define F(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define endl '\n'

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int N = 200020;
struct flower {
int a, b, c, w, ans;
} t[N], t1[N];
bool cmp(const flower& x, const flower& y) {
return (x.a == y.a) ? ((x.b == y.b) ? x.c < y.c : x.b < y.b) : x.a < y.a;
} bool cmp2(const flower& x, const flower& y) { return x.b < y.b; }
int n, k;
int tot, num[N], c[N];
void update(int x, int v) {
for (; x <= k; x += x & -x) c[x] += v;
}
int query(int x) {
int ans = 0;
for (; x; x -= (x & -x)) ans += c[x];
return ans;
}
void solve(int l, int r) {
// 边界: l == r 而非 l > r
if (l == r) return ;
int mid = (l + r) >> 1;
solve(l, mid), solve(mid + 1, r);
sort (t + l, t + mid + 1, cmp2);
sort (t + mid + 1, t + r + 1, cmp2);
// 递归计算两部分答案

// 由于 a 已经严格小于,故现在要讨论都小于等于的情况
int pos = l;
F(i, mid + 1, r) {
while (pos <= mid && t[pos].b <= t[i].b)
update(t[pos].c, t[pos].w), ++pos;
t[i].ans += query(t[i].c);
}
while (pos != l) --pos, update(t[pos].c, -t[pos].w);
}
void solve() {
scanf ("%d%d", &n, &k);
F(i, 1, n)
scanf ("%d%d%d", &t1[i].a, &t1[i].b, &t1[i].c);
// 带 w 和 ans: 本身这个点实际上对应多少个点,以及当前这个点答案
sort (t1 + 1, t1 + n + 1, cmp);
int cnt = 0;
F(i, 1, n) {
++cnt;
if (t1[i].a != t1[i+1].a || t1[i].b != t1[i+1].b || t1[i].c != t1[i+1].c)
t[++tot] = t1[i], t[tot].w = cnt, cnt = 0;
// 注意cdq分治只能搞 < 的情况,等于要手动判
}
solve (1, tot);
F(i, 1, tot) num[t[i].ans + t[i].w - 1] += t[i].w;
F(i, 0, n-1) printf("%d\n", num[i]);
}





int main() {
ios::sync_with_stdio(false);
cout << fixed;

#ifdef LOCAL
double cl = clock();
#endif

int T = 1;
while (T--) solve();

#ifdef LOCAL
cerr << "Time elapsed: " << (clock() - cl) / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}

整体二分

能用整体二分解决的东西都是离线问题。

主体框架还是按时间轴来做,但是有一些小区别:整体二分是二分每个询问在哪个答案区间里。

也就是说我们令 $solve(l,r,L,R)$ 为解决 $[l, r]$ 这段区间内的修改以及询问,已知这段询问答案都在 $[L, R]$ 内。基本框架就是每次选取 $[L, R]$ 的中点 $mid$ ,判断这些询问哪些答案比 $mid$ 小,就放左边,否则放右边,继续递归。当 $L = R$ 时,就可以确定答案了。

下面我们以区间第 $k$ 小为例子,简述一下整体二分的写法。

区间第 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
102
#include <bits/stdc++.h>

#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define F(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)
#define endl '\n'

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }


const int N = 200010;
struct Node {
int opt, id, l, r, k;
Node(int opt = 0, int id = 0, int l = 0, int r = 0, int k = 0):
opt(opt), id(id), l(l), r(r), k(k){}
}t[N << 1], t1[N << 1], t2[N << 1]; int tot = 0;
int n, m, a[N], answer[N << 1];
int c[N];
void upd(int x, int v){
for (; x < N; x += x & -x) c[x] += v;
} int qry(int x) {
int ans = 0; for (; x; x -= x & -x) ans += c[x]; return ans;
}
void solve(int l, int r, int L, int R) {
if (l > r || L > R) return;
if (L == R) {
F(i, l, r) if (t[i].opt == 2) answer[t[i].id] = L;
return ;
}
int mid = (L + R) >> 1, cnt1 = 0, cnt2 = 0;
F(i, l, r) {
if (t[i].opt == 1) {
if (t[i].k <= mid)
t1[++cnt1] = t[i], upd(t[i].l, 1);
else t2[++cnt2] = t[i];
}
else {
int sum = qry(t[i].r) - qry(t[i].l - 1);
if (sum >= t[i].k) {
// 答案在左侧
t1[++cnt1] = t[i];
} else t[i].k -= sum, t2[++cnt2] = t[i];
}
}
int now_pos = l;
F(i, 1, cnt1) {
if (t1[i].opt == 1) upd(t1[i].l, -1);
t[now_pos++] = t1[i];
}
F(i, 1, cnt2) t[now_pos++] = t2[i];
solve(l, l + cnt1 - 1, L, mid);
solve(l + cnt1, r, mid + 1, R);
}
void solve() {
scanf ("%d%d", &n, &m);
F(i, 1, n) {
scanf ("%d", &a[i]);
++tot, t[tot] = (Node){1, tot, i, i, a[i]};
}
F(i, 1, m) {
++tot;
scanf("%d%d%d", &t[tot].l, &t[tot].r, &t[tot].k);
t[tot].opt = 2; t[tot].id = tot;
}
solve(1, tot, -1e9, 1e9);
F(i, n + 1, n + m) printf("%d\n", answer[i]);
}





int main() {

#ifdef LOCAL
double cl = clock();
#endif

int T = 1;
while (T--) solve();

#ifdef LOCAL
cerr << "Time elapsed: " << (clock() - cl) / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}