peaceful coexistence

Topic link: PR #5 C

Topic to the effect

There are n black dots and m white dots. The black dots are all there at the beginning, and the white dots are added in a certain order.
After each addition, you have to select some points to delete (just suppose to delete, not actually delete), so that there is no black point in the lower left of the white point.
Ask you how many points to delete at least after each join.

train of thought

First of all, consider what to do if all the white spots are added, that is, which ones to delete, or which ones to keep.
For example, if a black dot is selected, there will be no white dot at the top right of it, and all the black dots at the top right of it can be kept.
Then it is not difficult for us to imagine the final appearance, a ladder-like decomposition, and it is the one with upper left and lower right.
The black above including the step line + the white below not including the step is what we can keep.

The one obvious thing is that with the addition of white dots, the ladder will only move up and to the right.
That is monotonous, we can use the overall dichotomy to get it (after a dividing line is determined, the points on both sides of it will only be in the < m i d <mid <mid and > m i d >mid >mid has uncertainty about contribution)

Then we continue to consider how to ask for a dividing line.
Consider looking from left to right, each black place to see if it is going to drop from the current height to his height.
Whether it falls or not depends on the number of black and white points in the narrowed range.
Consider black and white points for a match. Black matches with the upper right point, which is understood as offsetting the effect. If there is no match, there must be more black.
Then if both are down first (note that the top is white so the top cannot be pressed), then we must give priority not to go down here (because we try not to go down).
Then if the black is at the bottom and the white is at the top, then we have to put the black on the bottom, otherwise it will be inferior.

However, you will find that the matching cannot be matched casually.
If you think about it, you will find that you should match greedily from the back to the front. The black dot will match it with the first white dot that is higher than it on the right side that has not yet been matched.

the code

#include<set>
#include<cstdio>
#include<vector>
#include<algorithm>
#define INF 0x3f3f3f3f3f3f3f3f

using 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;
}