链接
难度：\(\texttt{省选/NOI-}\)
有 \(n\) 个矩形，左下角为 \((x1,y1)\)，右上角为 \((x2,y2)\)，问被其他的矩形包含的矩形有多少个。
数据范围：\(1\le n\le200000,x1<x2,y1<y2,x,y互不相同\ \mathtt{1s\sim 3s\ 125MB}\)。
CDQ 萌新受到了很大的震撼。
发现这个题其实是个四维偏序，但是问的是是否可行，其实是可以用三维 CDQ 解决的。
以 \(x1\) 为第一维，\(y1\) 为第二维（这应该挺好想到），那只需要考虑 \(x2\) 和 \(y2\) 的关系了。
维护后缀 \(x\) 的最大高度 \(y\) 最大值，若是属于左半部分则把 \(y2\) 扔到 \(x2\) 的位置更新最大值，若是询问则查询 \(\ge x2\) 的位置的最大值，若 \(>y2\) 则说明有解。
大致说明：因为第一维为 \(x1\)，所以可得左半部分 \(x1<\) 右半部分 \(x1\)，又因第二维为 \(y1\)，能保证遍历时肯定为 \(y1\) 递增，每次更新是由左半部分其 \(x1\) 会更小所以更新后缀没有问题，至于询问前面已提到 \(x1\) 已满足条件那 \(x2\) 找后缀相当于找的就是能包含该矩形的最大高度 \(y\)，若 \(y>y2\) 则满足条件。
# include <bits/stdc++.h>
using namespace std;
const int N = 200000;
struct node {
int x1, y1, x2, y2, id;
} a [N + 10], p [N + 10];
int mx [N + 10 << 2];
void update (int k, int l, int r, int x, int y) {
if (l == r) {
mx [k] = y;
return ;
}
int mid = l + r >> 1;
if (x <= mid) {
update (k << 1, l, mid, x, y);
}
else {
update (k << 1 | 1, mid + 1, r, x, y);
}
mx [k] = max (mx [k << 1], mx [k << 1 | 1]);
return ;
}
int query (int k, int l, int r, int x) {
if (l == r) {
return mx [k];
}
int mid = l + r >> 1;
if (x <= mid) {
return max (query (k << 1, l, mid, x), mx [k << 1 | 1]);
}
return query (k << 1 | 1, mid + 1, r, x);
}// 其实可以转化为前缀 max 改用树状数组
int tag [N + 10];
int n;
int ans [N + 10];
void CDQ (int l, int r) {
if (l == r) {
return ;
}
int mid = l + r >> 1;
CDQ (l, mid);
CDQ (mid + 1, r);
for (int i = l; i <= mid; ++ i) {
tag [a [i] .id] = 1;
}
for (int i = l; i <= r; ++ i) {
p [i] = a [i];
}
sort (p + l, p + 1 + r, [&] (node a, node b) {
return a .y1 < b .y1;
});
for (int i = l; i <= r; ++ i) {
if (tag [p [i] .id]) {
update (1, 1, n, p [i] .x2, p [i] .y2);
}
else if (query (1, 1, n, p [i] .x2) > p [i] .y2) {
ans [p [i] .id] = 1;
}
}
for (int i = l; i <= mid; ++ i) {
update (1, 1, n, a [i] .x2, 0);
tag [a [i] .id] = 0;
}
return ;
}
int x [N + 10];
int main () {
scanf ("%d", & n);
for (int i = 1; i <= n; ++ i) {
scanf ("%d %d %d %d", & a [i] .x1, & a [i] .y1, & a [i] .x2, & a [i] .y2);
a [i] .id = i;
x [i] = a [i] .x2;
}
sort (x + 1, x + 1 + n);
int m = unique (x + 1, x + 1 + n) - x - 1;
for (int i = 1; i <= n; ++ i) {
a [i] .x2 = lower_bound (x + 1, x + 1 + n, a [i] .x2) - x;
}
sort (a + 1, a + 1 + n, [&] (node a, node b) {
return a .x1 < b .x1;
});
CDQ (1, n);
int tot = 0;
for (int i = 1; i <= n; ++ i) {
tot += ans [i];
}
printf ("%d\n", tot);
return 0;
}