我终于自己发现哪里错了～～～
这个题目是涉及到点，线段树处理的是段，要变换一下。。。
看了N久线段树，终于知道一般的线段树怎么写了～～～～～
代码如下
#include "stdio.h"
#include "math.h"
#include "algorithm"
using namespace std;
struct {
	int l,r;
	int cnt;
	int line;
	int lb,rb;
	int sum;
	int getmid(){
		return (l+r)/2;
	}
}st[30000];//横线段的线段树

struct SS{
	int l,r;
	int h;
	int s;
}ss[15000];//横线段
int pos[15000];//横坐标
int k;//横坐标的个数
int bin(int c);
bool cmp(struct SS&a,struct SS&b){
	return a.h<b.h;
}

void build(int a,int b,int ind){
	st[ind].l=a;
	st[ind].r=b;
	st[ind].cnt=0;
	st[ind].sum=0;
	st[ind].line=0;
	st[ind].lb=st[ind].rb=0;
	if(a==b)
		return ;
	int mid=st[ind].getmid();
	build(a,mid,ind*2);
	build(mid+1,b,ind*2+1);
}
void update(int ind){
	if(st[ind].cnt){
		st[ind].sum=pos[st[ind].r+1]-pos[st[ind].l];//在计算和时，还原点值，所以+1
	}else if(st[ind].l==st[ind].r){
		st[ind].sum=0;
	}
	else{
		st[ind].sum=st[ind*2].sum+st[ind*2+1].sum;
	}
}
void updateline(int ind){
	if(st[ind].cnt)
		st[ind].lb=st[ind].rb=st[ind].line=1;
	else if(st[ind].l==st[ind].r)
		st[ind].lb=st[ind].rb=st[ind].line=0;
	else{
		st[ind].lb=st[ind*2].lb;
		st[ind].rb=st[ind*2+1].rb;
		st[ind].line=st[ind*2].line+st[ind*2+1].line-st[ind*2].rb*st[ind*2+1].lb;
	}
}
void insert(int a,int b,int c,int ind){
	if(a<=st[ind].l&&st[ind].r<=b){
		st[ind].cnt+=c;
	}else{
		int mid=st[ind].getmid();
		if(a<=mid)
			insert(a,b,c,ind*2);
		if(b>mid)
			insert(a,b,c,ind*2+1);
	}
	update(ind);
	updateline(ind);
}
int bin(int c){
	int p,q;
	p=0;
	q=k-1;
	while(p<=q){
		int mid=(p+q)/2;
		if(pos[mid]==c)
			return mid;
		if(pos[mid]<c)
			p=mid+1;
		else
			q=mid-1;
	}
	return -1;
}
int main(){
	int n,m;
	int x1,x2;
	int cx=-1;
	
		scanf("%d",&n);
		
		cx++;
		int i,j;
		m=0;
		for(i=0;i<n;i++){
			int a,b,c,d;
			scanf("%d%d%d%d",&a,&b,&c,&d);
			pos[m]=ss[m].l=ss[m+1].l=a;
			ss[m].h=b;
			ss[m].s=1;
			pos[m+1]=ss[m].r=ss[m+1].r=c;
			ss[m+1].h=d;
			ss[m+1].s=-1;
			m+=2;
		}
		sort(pos,pos+m);
		sort(ss,ss+m,cmp);
		for(i=0,k=0;i<m;i++){
			if(i==0||pos[i]!=pos[i-1]){
				pos[k++]=pos[i];
			}
		}
		build(0,k-1,1);
		int ret=0;
		int last=0;
		for(i=0;i<m-1;i++){
			
			x1=bin(ss[i].l);
			x2=bin(ss[i].r)-1;//求出离散化后的点对应的序号，换成段的序号要-1
			if(x2<x1){//两个点重复时，特殊处理！
				ret+=abs(st[1].sum-last);
				ret+=(st[1].line*2*(ss[i+1].h-ss[i].h));
				last=st[1].sum;
				continue;
			}
			insert(x1,x2,ss[i].s,1);
			ret+=abs(st[1].sum-last);
			ret+=(st[1].line*2*(ss[i+1].h-ss[i].h));
			last=st[1].sum;
		}
		ret+=st[1].sum;
		
		printf("%d\n",ret);
	
	return 0;
}

• Re:攒~~~ (2915) CalmDown 2010-12-01 18:24:25