题意：
在 r×c 的网格上有 n 个点。求至少包含一个点的矩形个数。
r,c≤40000,n≤100000 所有点随机生成。
题解：
无论是正向用单调栈查找矩形，还是反向查找不包含点的矩形复杂度都是 O(rc) 的（谁想卡常吗？ 233）
下面我们考虑这个问题的反面：不包含任何点的矩形个数（下面将这些点称为障碍点。）
但是这道题的特殊性质在于障碍点个数较少，且随机。
（然而对着这两个性质看并看不出来什么东西。。。）
考虑这个问题的经典解法：
考虑每一行作为矩形的下边界时对答案的贡献，显然我们只需要考虑每一列向上一直到障碍点的格子对答案的贡献。
可以发现只需要确定左上和右上点，就可以唯一确定矩形。
因为一对点 (A,B) 合法当且仅当它们在同一行且与底边围成的矩形中不含障碍点。
这时我们发现，可以将这些格子分成若干个小矩形（需要一张图来表述），则每一个小矩形内每一行的格子两两组合均合法。则对答案贡献为 ( 对于 w×h 的矩形 )2w(w−1)h.
如果将相邻的矩形相连，可以发现它是个二叉树结构，且左右儿子为一个障碍点左右的矩形。
因为障碍点随机，则可以证（脑）明（补）二叉树的树高均摊 O(logn).
那么我们只需要在向下扫描的时候维护这棵二叉树即可。
考虑每次将枚举的边下移时，首先肯定将根矩形的高度 ++。
然后对于这一行的每一个障碍点分别更新树结构，同时更新答案。每次更新是 O(height) 的，所以总复杂度 O(nlogn)
考虑如何更新树结构，考虑所有包含障碍点所在列的矩形（显然形成了一条链），将它们拆成两个矩形，然后与父节点相连。
这里可以发现，拆分后有一侧的矩形一定能够与其子矩形合并成一个大矩形，可以将它们合并。（不知道这不加能不能过。。）
除此之外，还可以使用 Treap 来维护这样的矩形。
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
| int x[MAXN], y[MAXN], r, c, n;
namespace solver1 {
struct Node {
int l, r, h;
Node *ls, *rs;
long long cal() {
return (long long) (r - l + 1) * (r - l + 2) / 2 * h;
}
}tree[MAXN << 1];
int tail = 1, root = 1;
std::queue <int> q;
int newnode() {
if (q.empty()) {
return ++tail;
} else {
int u = q.front(); q.pop(); return u;
}
}
void delnode(int u) {
memset(tree + u, 0, sizeof (tree[u]));
q.push(u);
}
long long tot = 0;
std::vector <int> pts[MAXN];
void update(int p) {
int tmp = root;
std::vector <int> seq;
while (1) {
seq.push_back(tmp);
if (tree[tmp].ls && tree[tmp].ls -> l <= p && p <= tree[tmp].ls -> r) {
tmp = tree[tmp].ls - tree;
} else if (tree[tmp].rs && tree[tmp].rs -> l <= p && p <= tree[tmp].rs -> r) {
tmp = tree[tmp].rs - tree;
} else {
break;
}
}
Node *lp, *rp;
{
int cur = seq[seq.size() - 1];
tot -= tree[cur].cal();
if (tree[cur].l < p) {
int nw = newnode();
tree[nw].ls = tree[cur].ls;
lp = tree + nw;
tree[nw].l = tree[cur].l, tree[nw].r = p - 1;
tree[nw].h = tree[cur].h;
tot += tree[nw].cal();
} else {
lp = 0;
}
if (tree[cur].r > p) {
int nw = newnode();
tree[nw].rs = tree[cur].rs;
rp = tree + nw;
tree[nw].l = p + 1, tree[nw].r = tree[cur].r;
tree[nw].h = tree[cur].h;
tot += tree[nw].cal();
} else {
rp = 0;
}
delnode(cur);
}
for (int i = seq.size() - 2; i >= 0; i--) {
int cur = seq[i];
tot -= tree[cur].cal();
if (tree + seq[i + 1] == tree[cur].ls) {
if (lp) {
tot -= lp -> cal();
lp -> h += tree[cur].h;
tot += lp -> cal();
}
if (tree[cur].r > p) {
tree[cur].l = p + 1;
tree[cur].ls = rp;
tot += tree[cur].cal();
rp = tree + cur;
} else {
rp = 0;
}
} else {
if (tree[cur].l < p) {
tree[cur].r = p - 1;
tree[cur].rs = lp;
tot += tree[cur].cal();
lp = tree + cur;
} else {
lp = 0;
}
if (rp) {
tot -= rp -> cal();
rp -> h += tree[cur].h;
tot += rp -> cal();
}
}
}
root = newnode();
tree[root].l = 1, tree[root].r = c;
tree[root].ls = lp;
tree[root].rs = rp;
}
void main() {
for (int i = 1; i <= n; i++) {
pts[x[i]].push_back(y[i]);
}
long long ans = (long long) c * (c + 1) / 2 * r * (r + 1) / 2;
tree[root].l = 1, tree[root].r = c;
for (int i = 1; i <= r; i++) {
tree[root].h++;
tot += (long long) c * (c + 1) / 2;
for (int j = 0; j < (int) pts[i].size(); j++) {
update(pts[i][j]);
}
ans -= tot;
}
printf("%lld\n", ans);
}
}
|
