1389.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"memory.h"
#include"algorithm"
using std::sort;

int x[2010],y[2010];
int n,index_y[2010],index_x[2010],to_y[2010];
int tree[2048*2],cover[2048*2];

int cmp_x(int a,int b)
{return x[a]<x[b];}
int cmp_y(int a,int b)
{return y[a]<y[b];}

int init()
{int i;

for(i=0;;i++)
{cin>>x[2*i]>>y[2*i]>>x[2*i+1]>>y[2*i+1];
if(x[2*i]==-1)break;
index_x[2*i]=2*i;index_x[2*i+1]=2*i+1;
index_y[2*i]=2*i;index_y[2*i+1]=2*i+1;
}
n=i;
if(n==0)return 0;

sort(&index_x[0],&index_x[2*n],cmp_x);
sort(&index_y[0],&index_y[2*n],cmp_y);

for(i=0;i<2*n;i++){to_y[index_y[i]]=i;}

memset(tree,0,2048*sizeof(int));
memset(cover,0,2048*sizeof(int));

return 1;
}

int a,b,key;

void insert(int root,int begin,int end)
{if(begin==end||b<=begin||end<=a)return;
 
if(a<=begin&&end<=b){
		if(key==0){tree[root]++;cover[root]=y[index_y[end]]-y[index_y[begin]];}
		else {tree[root]--;
				if(tree[root]==0){if(root*2+1<2048*2)cover[root]=cover[root*2+1]+cover[root*2+2];
								else cover[root]=0;}
			}
			return;}

insert(root*2+1,begin,(begin+end)/2);
insert(root*2+2,(begin+end)/2,end);

if(tree[root]==0)cover[root]=cover[root*2+1]+cover[root*2+2];

}

void doit()
{int i;
long s=0;

for(i=0;i<2*n;i++)
{key=index_x[i]%2;
if(i)s+=cover[0]*(x[index_x[i]]-x[index_x[i-1]]);
a=to_y[index_y[to_y[index_x[i]]]-key];
b=to_y[index_y[to_y[index_x[i]]]-key+1];
insert(0,0,n*2-1);
}

cout<<s<<endl;
}

int main()
{while(init())doit();
return 0;
}