和平共处

题目链接：PR #5 C

题目大意

有 n 个黑点 m 个白点，黑点一开始都在，白点按一定顺序加入。
问每次加入之后，你要选一些点删去（只是假设删去，并没有真正删去），使得不存在一个黑点在白点的左下方。
问你每次加入之后，最少要删多少个点。

思路

首先考虑白点都加入了要怎么搞，就是要删哪些，或者留那些。
那比如选了一个黑点，它右上方就不会有白点，那它右上方的黑点就可以全部保留。
那我们不难想象出最后的样子，一个阶梯状作为分解，而且是左上右下的那种。
上面包括阶梯线上的黑色+下面不包括阶梯的白色就是我们能保留的。

那一个显然的事情是随着白色点的加入，这个阶梯只会往右上移动。
那就是单调的，我们可以用整体二分来弄（一个分界线确定之后，它两边的点只会分别在 < m i d <mid <mid 和 > m i d >mid >mid 有是否贡献的不确定性）

那我们就继续考虑要怎么求一次的分界线。
考虑从左往右看，每个黑色的地方看是否要从当前的高度降到他这个高度。
那降不降就看那个缩小的区间中，黑白点的数量。
考虑黑白点进行一个匹配，黑色跟右上方的点匹配， 理解为作用抵消，然后没有匹配的话肯定是黑色多，折。
那如果两个都在先下面（注意上面是白色所以上面不能压线），那我们肯定优先不要在这里往下（因为我们是尽量不往下的）。
那如果黑色的在下面，白色的在上面，那我们就要黑色往下了，不然就不优了。

不过会发现匹配不可以随便匹配。
思考会发现应该从后往前贪心的匹配，黑点每次选还没有匹配的右边的第一个比它高的白点跟它匹配。

代码

#include<set>#include<cstdio>#include<vector>#include<algorithm>#define INF 0x3f3f3f3f3f3f3f3fusing namespace std;const int N = 2e5 + 100;struct dian {int x, y, op;};int n, m, ans[N], nxt[N];vector <dian> p;bool cmp(dian x, dian y) {if (x.x != y.x) return x.x < y.x;if (x.y != y.y) return x.y < y.y;return x.op < y.op;}void slove(int l, int r, vector <dian> &p, int an) {if (l > r) return ;int mid = (l + r) >> 1;set <pair<int, int> > s;for (int i = 0; i < p.size(); i++) nxt[i] = -1;for (int i = p.size() - 1; i >= 0; i--) {if (p[i].op) {if (p[i].op <= mid) s.insert(make_pair(p[i].y, i));}else {set <pair<int, int> > ::iterator it = s.lower_bound(make_pair(p[i].y, -1));if (it == s.end()) continue;nxt[(*it).second] = i; nxt[i] = (*it).second;s.erase(it);}}vector <dian> pl, pr; int Up = INF, lcnt = 0, rcnt = 0;for (int i = 0; i < p.size(); i++) {if (p[i].op) {if (p[i].op <= mid) {if (p[i].y < Up) pl.push_back(p[i]), rcnt++;else pr.push_back(p[i]);}else pr.push_back(p[i]);}else {if (nxt[i] == -1 || p[nxt[i]].y >= Up) Up = min(Up, p[i].y);if (p[i].y >= Up) pr.push_back(p[i]), lcnt++;else pl.push_back(p[i]);}}ans[mid] = n + mid - (an + lcnt + rcnt);slove(l, mid - 1, pl, an + lcnt);slove(mid + 1, r, pr, an + rcnt);}int main() {scanf("%d", &n);for (int i = 1; i <= n; i++) {dian x; scanf("%d %d", &x.x, &x.y); x.op = 0;p.push_back(x);}scanf("%d", &m);for (int i = 1; i <= m; i++) {dian x; scanf("%d %d", &x.x, &x.y); x.op = i;p.push_back(x);}sort(p.begin(), p.end(), cmp);slove(1, m, p, 0);for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);return 0;}