CDQ分治解决一类偏序问题

CDQ解决一类偏序问题


偏序问题的时间复杂度的理论上限为\(O(n^2)\)的,因此,我们追求的解决方案要在这个时间复杂度之下。
时间上限复杂度的做法就是对每一维用bitset维护小于它的值,一共有n维,时间复杂度为\(O^2\),最后求并得出个数。

三维偏序统计

counting star

ac code

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const int MAX_Q = 50004;
const int MAX_Z = 100005;
struct Ope {
int x, y, z;
int ty, id;
Ope (int xx, int yy, int zz, int tt, int ii) : x(xx), y(yy), z(zz), ty(tt), id(ii) {}
Ope () {}
};
bool cmp(Ope a, Ope b) {
if (a.x == b.x) return a.id < b.id;
return a.x < b.x;
}
bool cmp2(Ope a, Ope b) {
if (a.y == b.y) return a.id < b.id;
return a.y < b.y;
}
vector<Ope> ope, ope2, ope3;
int tree[MAX_Z];
int ans[MAX_Q];
bool isQuery[MAX_Q];
void update(int x, int a) {
while (x < MAX_Z) {
tree[x] += a;
x += (x & (-x));
}
}
int query(int x) {
int res = 0;
while (x) {
res += tree[x];
x -= (x & (-x));
}
return res;
}
void countStar() {
for (int i = 0; i < ope3.size(); i++) {
if (ope3[i].ty == 0) update(ope3[i].z, 1);
else {
int t = query(ope3[i].z);
ans[ope3[i].id] += t * ope3[i].ty;
}
}
for (int i = 0; i < ope3.size(); i++)
if (ope3[i].ty == 0) update(ope3[i].z, -1);
}
void CDQ2(int L, int R) {
if (L >= R) return;
int mid = (L + R) >> 1;
CDQ2(L, mid);
ope3.clear();
for (int i = L; i <= mid; i++)
if (ope2[i].ty == 0) ope3.push_back(ope2[i]);
for (int i = mid + 1; i <= R; i++)
if (ope2[i].ty != 0) ope3.push_back(ope2[i]);
sort(ope3.begin(), ope3.end(), cmp2);
countStar();
CDQ2(mid + 1, R);
}
void CDQ(int L, int R) {
if (L >= R) return;
int mid = (L + R) >> 1;
CDQ(L, mid);
ope2.clear();
for (int i = L; i <= mid; i++)
if (ope[i].ty == 0) ope2.push_back(ope[i]);
for (int i = mid + 1; i <= R; i++)
if (ope[i].ty != 0) ope2.push_back(ope[i]);
sort(ope2.begin(), ope2.end(), cmp);
CDQ2(0, ope2.size() - 1);
CDQ(mid + 1, R);
}
int T, Q;
vector<int> allZ;//离散化
int main() {
scanf("%d", &T);
while (T--) {
memset(isQuery, 0, sizeof(isQuery));
memset(ans, 0, sizeof(ans));
ope.clear();
allZ.clear();
memset(tree, 0, sizeof(tree));
scanf("%d", &Q);
for (int i = 0; i < Q; i++) {
int a;
scanf("%d", &a);
if (a == 1) {
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
ope.push_back(Ope(x, y, z, 0, i));
allZ.push_back(z);
}
else {
isQuery[i] = 1;
int xa, ya, za, xb, yb, zb;
scanf("%d%d%d%d%d%d", &xa, &ya, &za, &xb, &yb, &zb);
ope.push_back(Ope(xa - 1, ya - 1, za - 1, -1, i));
ope.push_back(Ope(xa - 1, ya - 1, zb, 1, i));
ope.push_back(Ope(xa - 1, yb, za - 1, 1, i));
ope.push_back(Ope(xa - 1, yb, zb, -1, i));
ope.push_back(Ope(xb, ya - 1, za - 1, 1, i));
ope.push_back(Ope(xb, ya - 1, zb, -1, i));
ope.push_back(Ope(xb, yb, za - 1, -1, i));
ope.push_back(Ope(xb, yb, zb, 1, i));
allZ.push_back(za - 1);
allZ.push_back(zb);
}
}
sort(allZ.begin(), allZ.end());
vector<int>::iterator it = unique(allZ.begin(), allZ.end());
allZ.resize(distance(allZ.begin(), it));
for (int i = 0; i < ope.size(); i++)
ope[i].z = lower_bound(allZ.begin(), allZ.end(), ope[i].z) - allZ.begin() + 1;
CDQ(0, ope.size() - 1);
for (int i = 0; i < Q; i++)
if (isQuery[i]) printf("%d\n", ans[i]);
}
return 0;
}

未解决的问题

文章目录
  1. 1. 三维偏序统计
    1. 1.1. ac code
  2. 2. 未解决的问题
{{ live2d() }}