相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/03/438964732567423.png
官方题解:http://paste.ubuntu.com/24129177/
解题报告
这题当然可以用二维线段树做
不过显然KD-Tree更好写
但考场上T了两个点
加上一个如果子树最优解大于已知答案就不进入的剪枝后速度就成Rank 1了 QwQ
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200009;
int n,vout,itr[N];
struct Point{int x,y,a,b,mnx,mny,mxx,mxy,v,ori,ch[2];}p[N];
inline bool cmpx(const Point &A, const Point &B) {return A.x < B.x;}
inline bool cmpy(const Point &A, const Point &B) {return A.y < B.y;}
inline bool cmp(const int a, const int b) {return p[a].x < p[b].x || (p[a].x == p[b].x && p[a].y < p[b].y);}
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
class KD_Tree{
int root,ans_tmp;
public:
inline void init() {
n = read();
for (int i=1;i<=n;i++) {
p[i].mnx = p[i].mxx = p[i].x = read();
p[i].mny = p[i].mxy = p[i].y = read();
p[i].a = read(); p[i].b = read();
}
build(root, 1, n, 0);
}
inline void insert(int id, int v) {
insert(root, 1, n, id, v);
}
inline int query(int id) {
ans_tmp = 0;
query(root, 1, n, id, judge(id, root));
return ans_tmp;
}
private:
void build(int &w, int l, int r, bool t) {
if (l == r) w = l;
else if (l < r) {
int mid = l + r >> 1; w = mid;
if (t) nth_element(p+l, p+mid, p+r+1, cmpx);
else nth_element(p+l, p+mid, p+r+1, cmpy);
build(p[w].ch[0], l, mid-1, t^1);
build(p[w].ch[1], mid+1, r, t^1);
for (int i=0,s;i<2;i++) if (s = p[w].ch[i]) {
p[w].mnx = min(p[s].mnx, p[w].mnx);
p[w].mny = min(p[s].mny, p[w].mny);
p[w].mxx = max(p[s].mxx, p[w].mxx);
p[w].mxy = max(p[s].mxy, p[w].mxy);
}
}
}
inline bool Contain(int w, int id) {
if (!w) return 0;
else return p[w].mnx <= p[id].x && p[id].x <= p[w].mxx && p[w].mny <= p[id].y && p[id].y <= p[w].mxy;
}
void insert(int w, int l, int r, int id, int v) {
p[w].v = max(p[w].v, v);
if (l < r) {
int mid = l + r >> 1;
if (Contain(p[w].ch[0], id)) insert(p[w].ch[0], l, mid-1, id, v);
if (Contain(p[w].ch[1], id)) insert(p[w].ch[1], mid+1, r, id, v);
}
}
inline int judge(int i, int j) {
if (p[i].x <= p[j].mnx && p[i].y <= p[j].mny && p[j].mxx <= p[i].a && p[j].mxy <= p[i].b) return 2;
else return max(p[i].x, p[j].mnx) <= min(p[i].a, p[j].mxx) && max(p[i].y , p[j].mny) <= min(p[i].b, p[j].mxy);
}
void query(int w, int l, int r, int id, int ty) {
if (ty == 2) ans_tmp = max(ans_tmp, p[w].v);
else {
if (p[id].x <= p[w].x && p[w].x <= p[id].a && p[id].y <= p[w].y && p[w].y <= p[id].b) ans_tmp = max(ans_tmp, p[w].ori);
int mid = l + r >> 1, tmp;
if (p[w].ch[0] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[0]))) query(p[w].ch[0], l, mid-1, id, tmp);
if (p[w].ch[1] && p[w].val > ans_tmp && (tmp = judge(id, p[w].ch[1]))) query(p[w].ch[1], mid+1, r, id, tmp);
}
}
}kd;
int main() {
kd.init();
for (int i=1;i<=n;i++) itr[i] = i;
sort(itr+1, itr+1+n, cmp);
for (int j=n,v,i=itr[j];j;i=itr[--j]) {
v = kd.query(i);
kd.insert(i, ++v);
p[i].ori = v;
vout = max(v, vout);
}
printf("%d\n",vout);
return 0;
}