|
|
題目鏈接：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坐標(biāo)排序，相同的按y坐標(biāo)排序，接下來就是對于矩形
A，能否在(xA1 - 1, yA1 - 1)到負(fù)無窮之間找到一個先前矩形序列的最大值，如
果能就將當(dāng)前矩形接在其后形成新的最大值，這里涉及到了兩個操作，一個是詢問
，然后是插入，詢問的是二維區(qū)間的最大值，插入的時候是在二維區(qū)間的點操作，
所以很容易想到用二維線段樹來維護每次操作，這題需要注意的是點比較離散，而
且詢問不是隨意的給出的，而且一開始二維空間是沒有值的，所以不需要預(yù)先建樹
，事實證明，預(yù)先建樹會耗費很大的時間，完全是不必要的。先來談?wù)劜迦氩僮鳎?br>我們沒有預(yù)先建樹，所以根結(jié)點一開始的下標(biāo)定為-1，這樣在插入的時候如果發(fā)現(xiàn)
根結(jié)點的下標(biāo)為-1，就生成一個新的結(jié)點（只需要將計數(shù)器賦值給根結(jié)點的編號即
可），然后將根結(jié)點的四個兒子全部標(biāo)記為-1，表示并沒有創(chuàng)建兒子，遞歸四個兒
子，做同樣的操作，直到只剩一個點的時候。然后是詢問，詢問時如果詢問區(qū)間和
訪問到的結(jié)點區(qū)間沒有交集自然是直接返回，還有一個剪枝，就是如果當(dāng)前結(jié)點還
未生成（標(biāo)記值為-1）說明之前并沒有在以它為根結(jié)點的子樹中插入值，也直接返
回。最后一種情況是當(dāng)前結(jié)點為根的子樹的最大值已經(jīng)小于等于當(dāng)前的最大值，也
直接返回即可。
二維線段樹的思想類似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;
}
|