下面是过的代码，用的漂浮法，从USACO上那个矩形切割得到的灵感
#include "stdio.h"
#include "string.h"

int x[10001];
int y[10001];
int n;
int ans[10001];
void cover(int l,int r,int k,int c){
	while(k<n&&(r<x[k]||l>y[k])){
		k++;
	}
	if(k>=n){
		ans[c]+=r-l+1;
		return;
	}
	if(l<x[k]){
		cover(l,x[k]-1,k+1,c);
		l=x[k];
	}
	if(r>y[k]){
		cover(y[k]+1,r,k+1,c);
		r=y[k];
	}
}
int main(){
	int t,i,j;
	int sum;
	scanf("%d",&t);
	while(t--){
		sum=0;
		memset(ans,0,sizeof(ans));
		scanf("%d",&n);
		for(i=0;i<n;i++){
			scanf("%d%d",&x[i],&y[i]);
		}
		for(i=n-1;i>=0;i--){
			cover(x[i],y[i],i+1,i);
		}
		for(i=0;i<n;i++){
			if(ans[i]>0)
				sum++;
		}
		printf("%d\n",sum);
	}
	return 0;

}

• 下面是挂的代码，用线段树+离散化，RUNTIme error求解～～ (2071) ccyjava 2010-11-20 11:51:26
  • Re:下面是挂的代码，用线段树+离散化，RUNTIme error求解～～ (25) point3251 2011-02-13 15:19:35