[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;
}
上一篇:第五种方式,python使用组合来添加类方法和属性(二),以selenium的webdriver为例


下一篇:ios AudioQueueStart returns -50 录音失败问题