|
|
題目鏈接：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;
}
|