首页 > ACM题库 > HDU-杭电 > HDU 3458-Rectangles Too!-线段树-[解题报告]HOJ
2014
03-23

HDU 3458-Rectangles Too!-线段树-[解题报告]HOJ

Rectangles Too!

问题描述 :

A rectangle in the Cartesian plane is speci ed by a pair of coordinates (x1 , y1) and (x2 , y2) indicating its lower-left and upper-right corners, respectively (where x1 ≤ x2 and y1 ≤ y2). Given a pair of rectangles,A = ((xA1 , yA1 ), (xA2 ,yA2 )) and B = ((xB1 , yB1 ), (xB2 , yB2 )), we write A ≤ B (i.e., A "precedes" B), if xA2 < xB1 and yA2 < yB1 :In this problem, you are given a collection of rectangles located in the two-dimension Euclidean plane. Find the length L of the longest sequence of rectangles (A1,A2,…,AL) from this collection such that A1 ≤ A2 ≤ … ≤ AL.

输入:

The input fi le will contain multiple test cases. Each test case will begin with a line containing a single integer n (where 1 ≤ n ≤ 100000), indicating the number of input rectangles. The next n lines each contain four integers xi1 ,yi1 ,xi2 ,yi2 (where -1000000 ≤ xi1 ≤ xi2 ≤ 1000000, -1000000 ≤ yi1 ≤ yi2 ≤ 1000000, and 1 ≤ i ≤ n), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by asingle line containing the integer 0.

输出:

The input fi le will contain multiple test cases. Each test case will begin with a line containing a single integer n (where 1 ≤ n ≤ 100000), indicating the number of input rectangles. The next n lines each contain four integers xi1 ,yi1 ,xi2 ,yi2 (where -1000000 ≤ xi1 ≤ xi2 ≤ 1000000, -1000000 ≤ yi1 ≤ yi2 ≤ 1000000, and 1 ≤ i ≤ n), indicating the lower left and upper right corners of a rectangle. The end-of-file is denoted by asingle line containing the integer 0.

样例输入:

3
1 5 2 8
3 -1 5 4
10 10 20 20
2
2 1 4 5
6 5 8 10
0

样例输出:

2
1

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define ull unsigned __int64
#define ll __int64
//#define ull unsigned long long
//#define ll long long
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define middle (l+r)>>1
#define MOD 1000000007
#define esp (1e-8)
const int INF=0x3F3F3F3F;
const double DINF=10000.00;
//const double pi=acos(-1.0);
const int N=100010;
int n,m;
int X[N<<1],mmax[N<<4],dp[N];
struct rct{
	int x1,y1,x2,y2;
	void write(){
		scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
	}
	bool operator < (const rct& p) const {
		return y1 < p.y1;
	}
}a[N];
struct node{
	int pos,id;
	node(){}
	node(int _pos,int _id) : pos(_pos),id(_id){}
	bool operator < (const node& p) const {
		return a[id].y2 > a[p.id].y2;
	}
}nd;

void PushUp(int rt){
	mmax[rt]=max(mmax[rt<<1],mmax[rt<<1|1]);
}

void Update(int l,int r,int rt,int p,int c){
	if(l==r){mmax[rt]=max(mmax[rt],c);return;}
	int mid=middle;
	if(p<=mid) Update(lson,p,c);
	else Update(rson,p,c);
	PushUp(rt);
}

int Query(int l,int r,int rt,int L,int R){
	if(L<=l && r<=R) return mmax[rt];
	int mid=middle,ret=0;
	if(L<=mid) ret=max(ret,Query(lson,L,R));
	if(mid<R) ret=max(ret,Query(rson,L,R));
	return ret;
}

int bs(int key,int size,int A[]){
	int l=0,r=size-1,mid;
	while(l<=r){
		mid=middle;
		if(key>A[mid]) l=mid+1;
		else if(key<A[mid]) r=mid-1;
		else return mid;
	}return -1;
}

int main(){
	//freopen("1.in","r",stdin);
	//freopen("1.out","w",stdout);
	int i,j,k,ret;
	//int T,cas;scanf("%d",&T);for(cas=1;cas<=T;cas++)
	while(~scanf("%d",&n)){
		if(!n) break;
		for(i=m=0;i<n;i++){
			a[i].write(),dp[i]=1;
			X[m++]=a[i].x1;X[m++]=a[i].x2;
		}
		sort(X,X+m);
		for(i=k=1;i<m;i++) if(X[i]!=X[i-1]) X[k++]=X[i];
		sort(a,a+n);
		priority_queue<node>pq;
		memset(mmax,0,sizeof(mmax));
		for(i=ret=0;i<n;i++){
			while(!pq.empty()){
				nd=pq.top();
				if(a[nd.id].y2<a[i].y1){
					pq.pop();
					Update(0,k,1,nd.pos+1,dp[nd.id]);
				}else break;
			}
			dp[i]=Query(0,k,1,0,bs(a[i].x1,k,X))+1;
			pq.push(node(bs(a[i].x2,k,X),i));
			ret=max(ret,dp[i]);
		}
		printf("%d\n",ret);
	}
	return 0;
}

参考:http://blog.csdn.net/gotoac/article/details/7564668