挺神仙的一道题,考场上打的30分的思路,作死没打线段树打的珂朵莉树,然后和暴力一个分......(其实考完后发现改过来也只得了十分,啊我内心平衡了.)
听说这道题四分树(二维线段树)可以得到不少的分,上一届学长不少都是(O(n^2))碾过去的。
这里来说一下正解吧，个人感觉做这道题最起码要会扫描线
借用扫描线的思路,我们可以考虑在每一个线段树的节点里面维护什么东西,我们给每种颜色以其出现的先后顺序编号,由于这道题的编号大的颜色会覆盖编号小的颜色,我们需要知道该区间之中还没有计入答案的最大的颜色(maxv),当前区间可以看到的最小的颜色(minv),如果后者大于前者,这个颜色显然是无法记录的.同时为了动态维护当前完全覆盖当前区间的所有颜色以更新前面的两个东西,对于每个节点我们需要开一个(set),记录完全覆盖当前区间的所有颜色,于是我们可以获得更新他们的方法.
前者好理解,后者就是现在两个子树里面取(min),但是如果这种颜色没有完全覆盖这个区间的颜色的最大值大的话就会被覆盖了.这样就完成了更新.
完成了上述维护之后就好说了,先扫描线常规操作离散化一下,再以此取出根节点可以看到的尚未被标记的最大的颜色,标记之后再次向下更新,扫描完之后统计一下被标记的一共有几种颜色就可以了.(严重谴责学长下发的(std),根本看不懂(QAQ))
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#define sit std::set<int>::iterator
#define lson (t << 1)
#define rson (t << 1 | 1)
#define mid ((l + r) >> 1)
const int N = 5e6 + 10;
struct Node {
int x, up, down, id, pos;
bool operator < (const Node &a)const {
return a.x > x;
}
} a[N];
int num[N], top, tag[N];
using std::lower_bound;
struct Tree { //维护每一个线段树节点
int maxv, minv;
std::set<int> s;
} tree[N];
void build(int t, int l, int r) {
tree[t].maxv = -1;//-1表示区间里面看不到未标记的颜色
if(l == r) return;
build(lson, l, mid);
build(rson, mid + 1, r);
}
void pushup(int t) {//按照上式更新,注意set是否为空
tree[t].maxv = std::max(tree[lson].maxv, tree[rson].maxv);
if(!tree[t].s.empty()) tree[t].maxv = std::max(tree[t].maxv, *--tree[t].s.end());
tree[t].minv = std::min(tree[lson].minv, tree[rson].minv);
if(!tree[t].s.empty()) tree[t].minv = std::max(tree[t].minv, *--tree[t].s.end());
if(tree[t].minv > tree[t].maxv) {//被覆盖
tree[t].maxv = -1;
}
else if(tag[tree[t].maxv]) tree[t].maxv = -1;//看到过
}
void Add(int t, int l, int r, int cl, int cr, int num) {//加入新颜色
if(cl <= l && r <= cr) {
tree[t].s.insert(num);
pushup(t);
return;
}
if(cr <= mid) Add(lson, l, mid, cl, cr, num);
else if(cl > mid) Add(rson, mid + 1, r, cl, cr, num);
else {
Add(lson, l, mid, cl, cr, num);
Add(rson, mid + 1, r, cl, cr, num);
}
pushup(t);
}
void Erase(int t, int l, int r, int el, int er, int num) {//去掉老颜色
if(el <= l && r <= er) {
sit it = tree[t].s.lower_bound(num);
tree[t].s.erase(it);
pushup(t);
return;
}
if(er <= mid) Erase(lson, l, mid, el, er, num);
else if(el > mid) Erase(rson, mid + 1, r, el, er, num);
else {
Erase(lson, l, mid, el, er, num);
Erase(rson, mid + 1, r, el, er, num);
}
pushup(t);
}
void update(int t, int l, int r, int ul, int ur) {//每标记完一个颜色之后更新一下
if(ul <= l && r <= ur) {
pushup(t);
return;
}
if(ur <= mid) update(lson, l, mid, ul, ur);
else if(ul > mid) update(rson, mid + 1, r, ul, ur);
else {
update(lson, l, mid, ul, ur);
update(rson, mid + 1, r, ul, ur);
}
pushup(t);
}
int L[N], R[N];
int main() {
freopen("excel.in", "r", stdin);
freopen("excel.out", "w", stdout);
int n;
scanf("%d", &n);
tag[0] = 1;
for(int i = 1; i <= n; ++i) {
int x, y, aa, bb;
scanf("%d%d%d%d", &x, &y, &aa, &bb);
a[i * 2 - 1] = (Node){x, bb - 1, y, i, 1};
a[i * 2] = (Node){aa, bb - 1, y, i, -1};
num[++top] = y;
num[++top] = bb - 1;
}
std::sort(a + 1, a + n * 2 + 1);
std::sort(num + 1, num + top + 1);
top = std::unique(num + 1, num + top + 1) - num - 1;
build(1, 1, top);
for(int i = 1; i <= n * 2; ++i) {
int up = lower_bound(num + 1, num + top + 1, a[i].up) - num;
int down = lower_bound(num + 1, num + top + 1, a[i].down) - num;
if(a[i].pos == 1) {
Add(1, 1, top, down, up, a[i].id);
L[a[i].id] = down;
R[a[i].id] = up;
}
else {
Erase(1, 1, top, down, up, a[i].id);
}
if(a[i].x != a[i + 1].x) {
while(tree[1].maxv != -1) {
tag[tree[1].maxv] = 1;
update(1, 1, top, L[tree[1].maxv], R[tree[1].maxv]);
}
}
}
int ans = 0;
for(int i = 0; i <= n; ++i) {//统计答案
if(tag[i]) {
ans++;
}
}
printf("%d
", ans);
return 0;
}