|
|
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3458
  /**//*
 题意：
给定n(1<= n <= 100000)个矩形，问最长的递增矩形序列。矩形A和B
A = ((xA1 , yA1 ), (xA2 ,yA2 )) 和 B = ((xB1 , yB1 ), (xB2 , yB2 )),
如果xA2 < xB1 and yA2 < yB1 则 A <= B，问最长L1 <= L2  <= Ln的长度。
解法：
二维线段树
思路：
首先将矩形按左下角x坐标排序，相同的按y坐标排序，接下来就是对于矩形
A，能否在(xA1 - 1, yA1 - 1)到负无穷之间找到一个先前矩形序列的最大值，如
果能就将当前矩形接在其后形成新的最大值，这里涉及到了两个操作，一个是询问
，然后是插入，询问的是二维区间的最大值，插入的时候是在二维区间的点操作，
所以很容易想到用二维线段树来维护每次操作，这题需要注意的是点比较离散，而
且询问不是随意的给出的，而且一开始二维空间是没有值的，所以不需要预先建树
，事实证明，预先建树会耗费很大的时间，完全是不必要的。先来谈谈插入操作，
我们没有预先建树，所以根结点一开始的下标定为-1，这样在插入的时候如果发现
根结点的下标为-1，就生成一个新的结点（只需要将计数器赋值给根结点的编号即
可），然后将根结点的四个儿子全部标记为-1，表示并没有创建儿子，递归四个儿
子，做同样的操作，直到只剩一个点的时候。然后是询问，询问时如果询问区间和
访问到的结点区间没有交集自然是直接返回，还有一个剪枝，就是如果当前结点还
未生成（标记值为-1）说明之前并没有在以它为根结点的子树中插入值，也直接返
回。最后一种情况是当前结点为根的子树的最大值已经小于等于当前的最大值，也
直接返回即可。
二维线段树的思想类似ZJU 2859 Matrix Searching，只不过一个求的是最大值
，一个是最小值。
 */
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define maxn 100010*4
struct Tree {
int Max;
int son[4];
  void clear() {
int i;
for(i = 0; i < 4; i++)
son[i] = -1;
Max = 0;
 }
}T[4*maxn];
int Tree_Id;
struct Rectangle {
int x0, x1, y0, y1;
Rectangle(){}
Rectangle(int _x0, int _x1, int _y0, int _y1) {
x0 = _x0; x1 = _x1;
y0 = _y0; y1 = _y1;
}
};
vector < Rectangle > Rec;
bool cmp(Rectangle a, Rectangle b) {
return a.x0 < b.x0 || (a.x0 == b.x0 && a.y0 < b.y0);
}
int Max(int a, int b) {
return a > b ? a : b;
}
int Min(int a, int b) {
return a < b ? a : b;
}
void Query(int root, int sx, int ex, int sy, int ey, int x0, int x1, int y0, int y1, int& Max) {
if(sx > x1 || ex < x0 || sy > y1 || ey < y0 || root == -1 || T[root].Max <= Max)
return ;
if(sx <= x0 && x1 <= ex && sy <= y0 && y1 <= ey) {
if(T[root].Max > Max)
Max = T[root].Max;
return ;
}
int lmidx = (x0 + x1) >> 1;
int lmidy = (y0 + y1) >> 1;
int rmidx = (lmidx < x1) ? lmidx+1 : lmidx;
int rmidy = (lmidy < y1) ? lmidy+1 : lmidy;
Query(T[root].son[0], sx, ex, sy, ey, x0, lmidx, y0, lmidy, Max);
Query(T[root].son[1], sx, ex, sy, ey, x0, lmidx, rmidy, y1, Max);
Query(T[root].son[2], sx, ex, sy, ey, rmidx, x1, y0, lmidy, Max);
Query(T[root].son[3], sx, ex, sy, ey, rmidx, x1, rmidy, y1, Max);
}
void Insert(int& root, int x, int y, int x0, int x1, int y0, int y1, int val) {
if(x < x0 || x > x1 || y < y0 || y > y1)
return ;
if(root == -1) {
root = Tree_Id++;
T[root].clear();
}
if(val > T[root].Max)
T[root].Max = val;
if(x0 == x && x == x1 && y0 == y && y == y1) {
return ;
}
int lmidx = (x0 + x1) >> 1;
int lmidy = (y0 + y1) >> 1;
int rmidx = (lmidx < x1) ? lmidx+1 : lmidx;
int rmidy = (lmidy < y1) ? lmidy+1 : lmidy;
Insert(T[root].son[0], x, y, x0, lmidx, y0, lmidy, val);
Insert(T[root].son[1], x, y, x0, lmidx, rmidy, y1, val);
Insert(T[root].son[2], x, y, rmidx, x1, y0, lmidy, val);
Insert(T[root].son[3], x, y, rmidx, x1, rmidy, y1, val);
}
int n;
int main() {
int i;
int MaxX, MaxY, MinX, MinY;
while(scanf("%d", &n) != EOF && n) {
Rec.clear();
MaxX = MaxY = INT_MIN;
MinX = MinY = INT_MAX;
for(i = 0; i < n; i++) {
int x0, x1, y0, y1;
scanf("%d %d %d %d", &x0, &y0, &x1, &y1);
Rec.push_back(Rectangle(x0, x1, y0, y1));
MinX = Min(x0, MinX); MinY = Min(y0, MinY);
MaxX = Max(x1, MaxX); MaxY = Max(y1, MaxY);
}
MinX -= 2; MinY -= 2; MaxX += 2; MaxY += 2;
sort(Rec.begin(), Rec.end(), cmp);
Tree_Id = 0;
int ans = 1;
int root = -1;
for(i = 0; i < Rec.size(); i++) {
int Max = 0;
Query(root, MinX, Rec[i].x0-1, MinY, Rec[i].y0-1, MinX, MaxX, MinY, MaxY, Max);
Insert(root, Rec[i].x1, Rec[i].y1, MinX, MaxX, MinY, MaxY, Max + 1);
if(Max + 1 > ans)
ans = Max + 1;
}
printf("%d\n", ans);
}
return 0;
}
|