这是我新发现的一个比 darkBZOJ 不知道快到哪里去的OJ,就是它的题面还要靠人工一点点修正。真是一个伟大的目标
Sol
有一个月没更博了...
首先暴力的搞法就是枚举每一个左下角,然后暴力看哪一些点可以贡献成为右上角
现在主要的问题在于确定右上角,那么来看看右上角都有哪些特点。
我们先设我们现在处理的左下角 $A$ 点在 $(x_1, y_1)$ 的位置
首先,假如有一列候选的右上角的点,它们的恒左边相同,此时只有最下面的点可以成为右上角。这一点比较显然。
现在考虑其他的点对 $A$ 点的影响,借 yyb 的图用一下
此时对于 $C$ 点来说,没有受到 $A$,$B$ 两点的贡献限制。但是很显然 $B$ 受到了 $A$ 的限制。可以看出来,一个点的横坐标如果比另外一个点的要大,它就会影响那些点的贡献。
那么应该用cdq分治搞的想法应该就出来了。首先肯定要对 $x$ 轴坐标排序。然后按照 $y$ 轴坐标从大到小的顺序一次加入处理。对左右两边同时开单调栈,保证 $x$ 轴坐标的单调性。右边的从小到大,左边的从大到小,那么这样就保证了每一个左侧点对在单调栈中前面一个元素影响。也就是说,假如上面那个图不这样做,假如 A B C对于当前的区间都在同一侧, B 可能就会对 A C两个点计算重复的部分。这样用单调栈维护顺序就不会了。
关于每次选入的点,单调栈上二分是常见操作了吧
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int SIZE = 5e5 + 5;
int n; LL ans;
int stal[SIZE], star[SIZE];
struct node {
int x, y;
bool operator< (const node &a) const {
return x < a.x;
}
} a[SIZE];
namespace GTR {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (c < 48 || c > 57) b ^= c == '-', c = fetch();
while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
return b ? a : -a;
}
} using GTR::read;
int cmp(node a, node b) {
return a.y > b.y;
}
void cdq(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
std::sort(a + l, a + mid + 1, cmp); std::sort(a + mid + 1, a + r + 1, cmp);
int ql = 0, qr = mid + 1, top = 0;
for (int i = l; i <= mid; ++ i) {
while (qr <= r && a[qr].y > a[i].y) {
while (top && a[star[top]].x > a[qr].x) -- top;
star[++ top] = qr ++;
}
while (ql && a[stal[ql]].x < a[i].x) -- ql;
stal[++ ql] = i;
if (ql == 1) ans += top;
else {
int xl = 1, xr = top, res = top + 1;
while (xl <= xr) {
int mi = (xl + xr) >> 1;
if (a[star[mi]].y > a[stal[ql - 1]].y) xl = mi + 1;
else res = mi, xr = mi - 1;
}
ans += top - res + 1;
}
}
}
int main() {
n = read();
for (int i = 1; i <= n; ++ i) a[i].x = read(), a[i].y = read();
std::sort(a + 1, a + n + 1);
cdq(1, n);
printf("%lld\n", ans);
return 0;
}