[CF983D]Arkady and Rectangles[线段树+可删堆/set]

题意

你有一个无限大的绘图板,开始颜色是\(0\) , 你将进行\(n\) 次绘图,第\(i\) 次绘图会将左下角为 \((x_1, y_1)\),右上角为\((x_2, y_2)\) 的矩形涂成颜色\(i\). 问你最后能看到的颜色数量 ( 包括 0 ).

\(n\le 10^5\)

分析

• \(kd-tree\) 不好维护可行面积，所以考虑扫描线套线段树。

• 我们可以给每种颜色一个权值(出现的时间)表示他被看到的难易程度，出现时间越晚的颜色越容易被看到。

• 线段树上维护当前可以被看到的 未出现 的颜色中权值最大的颜色 \(Max\)，每次取出根节点维护的值并打上标记，表示已经看到过。

• 但是有可能 \(Max\) 被当前区间的某个已经出现的颜色全部遮住了，所以还需要维护标记 \(Min\) ，意义如下：

  我们记 \(mx_p\) 表示所有覆盖位置 \(p\) 的已出现权值的最大值， \(Min=\min_\limits{p\in[l,r]}\{mx_p\}\) 。

• 再用一个 \(set​\) 维护出现在整个区间中的最大的颜色是多少，显然其他的颜色不是被他覆盖就是不能覆盖它。

• 节点维护:

  \(Max=max({Max}_l,{Max}_r,maxv)\) ，\(maxv\) 表示出现在 \(set\) 中的最大权值(如果还没有被看到)

  \(Min=max(min({Min}_l,{Min}_r),maxv)\) ，\(maxv\) 表示出现在 \(set​\) 中的最大权值(如果已经出现了)

• 所以如果区间的 \(Max < Min\) 表示不存在未出现的颜色可以被看到。

• 总时间复杂度为 \(O(nlog^2n)\)。

代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

#define rep(i, a, b) for(int i = a; i <= b; ++i)

#define pb push_back

#define re(x) memset(x, 0, sizeof x)

inline int gi() {

    int x = 0,f = 1;

    char ch = getchar();

    while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar();}

    while(isdigit(ch)) { x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}

    return x * f;

}

template <typename T> inline void Max(T &a, T b){if(a < b) a = b;}

template <typename T> inline void Min(T &a, T b){if(a > b) a = b;}

const int N = 2e5 + 7;

int n, ndc, vc;

int V[N], mx[N << 2], mi[N << 2], xl[N], xr[N], yl[N], yr[N];

bool vis[N];

#define Ls o << 1

#define Rs o << 1 | 1

struct qs {

	int p, l, r, opt;

	bool operator <(const qs &rhs) const {

		if(p != rhs.p) return p < rhs.p;

		return opt < rhs.opt;

	}

}q[N];

struct Heap {

	priority_queue<int>A, B;

	void ins(int x){ A.push(x);}

	void del(int x){ B.push(x);}

	int top() {

		while(!B.empty() && A.top() == B.top()) A.pop(), B.pop();

		return A.empty() ? 0 : A.top();

	}

}col[N << 2];

void pushup(int l, int r, int o) {

	if(l ^ r) {

		mi[o] = min(mi[Ls], mi[Rs]);

		mx[o] = max(mx[Ls], mx[Rs]);

	}else mi[o] = mx[o] = 0;

	if(col[o].top()) {

		int x = col[o].top();

		if(vis[x]) Max(mi[o], x);

		else Max(mx[o], x);

		if(mi[o] > mx[o]) mx[o] = 0;

	}

}

void modify(int L, int R, int l, int r, int o, int v) {

	if(L <= l && r <= R) {

		if(v > 0) col[o].ins(v);

		if(v < 0) col[o].del(-v);

		pushup(l, r, o);

		return;

	}int mid = l + r >> 1;

	if(L <= mid) modify(L, R, l, mid, Ls, v);

	if(R > mid)  modify(L, R, mid + 1, r, Rs, v);

	pushup(l, r, o);

}

int main() {

	n = gi();

	rep(i, 1, n) {

		xl[i] = gi(), yl[i] = gi(), xr[i] = gi(), yr[i] = gi();

		q[++ndc] = (qs){ xl[i], yl[i], yr[i] - 1, i};

		q[++ndc] = (qs){ xr[i], yl[i], yr[i] - 1, -i};

		V[++vc] = yl[i];

		V[++vc] = yr[i];

	}

	sort(V + 1, V + 1 + vc);

	sort(q + 1, q + 1 + ndc);

	vc = unique(V + 1, V + 1 + vc) - V - 1;

	rep(i, 1, n) {

		yl[i] = lower_bound(V + 1, V + 1 + vc, yl[i]) - V;

		yr[i] = upper_bound(V + 1, V + 1 + vc, yr[i] - 1) - V - 1;

	}

	rep(i, 1, ndc) {

		q[i].l = lower_bound(V + 1, V + 1 + vc, q[i].l) - V;

		q[i].r = upper_bound(V + 1, V + 1 + vc, q[i].r) - V - 1;

	}

	for(int i = 1, j = 1; i <= ndc; i = j) {

		for(;j <= ndc && q[j].p == q[i].p; ++j)

			modify(q[j].l, q[j].r, 1, vc, 1, q[j].opt);

		while(mx[1]) {

			int x = mx[1];vis[x] = 1;

			modify(yl[x], yr[x], 1, vc, 1, 0);

		}

	}

	int ans = 1;

	rep(i, 1, n) if(vis[i]) ++ans;

	printf("%d\n", ans);

	return 0;

}