poj 1177 picture 线段树

调了两天。。。最后那天晚上线段树按[1,2)写的很容易就对了。。

/*
ID:autoacd1
PROG:picture
LANG:C++
*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MAX 21000
#include<cmath>
using namespace std;
struct wbysr
{
int x1,y1,x2,y2,d;
}x[10000+4],y[10000+4];
int n,i,ans_x=0,ans_y=0,ori=0;
int l[4*MAX],r[4*MAX],f[4*MAX],len[4*MAX];
bool cmp_x(wbysr a1,wbysr a2)
{
return (a1.y1>a2.y1)||(a1.y1==a2.y1&&a1.d>a2.d);
}
bool cmp_y(wbysr a1,wbysr a2)
{
return(a1.x1>a2.x1)||(a1.x1==a2.x1&&a1.d>a2.d);
}
void build(int x,int la,int ra)
{
l[x]=la;
r[x]=ra;
f[x]=0;
len[x]=0;
if(la==ra-1)
return;
int mid=(la+ra)/2;
build(2*x,la,mid);
build(2*x+1,mid,ra);
}
void insert(int x,int la,int ra,int num)
{
if(ra<=l[x]||la>=r[x])
return;
if(l[x]>=la&&r[x]<=ra&&f[x]+num>=0)
{
f[x]+=num;
if(f[x]>0)
len[x]=r[x]-l[x];
else
{
if(l[x]<r[x]-1)
len[x]=len[2*x]+len[2*x+1];
else
len[x]=0;
}
return;
}
f[2*x]+=f[x];
f[2*x+1]+=f[x];
f[x]=0;
if(f[2*x])
len[2*x]=r[2*x]-l[2*x];
/*	else
{
if(l[2*x]<r[2*x]-1)
len[2*x]=len[2*2*x]+len[2*(2*x)+1];
else
len[2*x]=0;
}	*/
if(f[2*x+1])
len[2*x+1]=r[2*x+1]-l[2*x+1];
/*	else
{
if(l[2*x+1]<r[2*x+1]-1)
len[2*x+1]=len[2*(2*x+1)]+len[2*(2*x+1)+1];
else
len[(2*x+1)]=0;
}*/
insert(2*x,la,ra,num);
insert(2*x+1,la,ra,num);
if(f[x])
len[x]=r[x]-l[x];
else
len[x]=len[2*x]+len[2*x+1];
return;
}
int main()
{
{
//freopen("1.out","w",stdout);
//
freopen("picture.in","r",stdin);
//
freopen("picture.out","w",stdout);
cin>>n;
for(i=1;i<=2*n;i+=2)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
//	/*
x1+=10005;
x2+=10005;
y2+=10005;
y1+=10005;
//
*/
//x
x[i].x1=x1;
x[i].y1=y1;
x[i].x2=x2;
x[i].y2=y1;
x[i].d=-1;
i++;
x[i].x1=x1;
x[i].y1=y2;
x[i].x2=x2;
x[i].y2=y2;
x[i].d=1;
//y
i--;
y[i].x1=x1;
y[i].y1=y1;
y[i].x2=x1;
y[i].y2=y2;
y[i].d=-1;
i++;
y[i].x1=x2;
y[i].y1=y1;
y[i].x2=x2;
y[i].y2=y2;
y[i].d=1;
i--;
}
//x!!!
sort(x+1,x+1+n+n,cmp_x);
build(1,1,MAX+4);
for(i=1;i<=2*n;i++)
{
//cout<<"-------------------------------------------"<<i<<endl;
insert(1,x[i].x1,x[i].x2,x[i].d);
if(x[i].y1!=x[i+1].y1||x[i].d!=x[i+1].d)
{
ans_x+=abs(len[1]-ori);
ori=len[1];
}
//
cout<<"___"<<x[i].x1<<' '<<x[i].x2<<' '<<x[i].d<<' '<<len[1]<<' '<<ans_x<<endl;
/*
cout<<"-________________________________"<<endl;
for(int j=1;j<=136;j++)
cout<<j<<"
"<<l[j]<<"
"<<r[j]<<"
"<<len[j]<<"
"<<f[j]<<endl;
//
*/
}
//
cout<<"_____"<<ans_x<<endl;
//y!!!
memset(l,0,sizeof(l));
memset(r,0,sizeof(r));
memset(f,0,sizeof(f));
memset(len,0,sizeof(len));
sort(y+1,y+1+n+n,cmp_y);
build(1,1,MAX+4);
for(i=1;i<=2*n;i++)
{
//cout<<"-------------------------------------------"<<i<<endl;
insert(1,y[i].y1,y[i].y2,y[i].d);
if(y[i].x1!=y[i+1].x1||y[i].d!=y[i+1].d)
{
ans_y+=abs(len[1]-ori);
ori=len[1];
}
//
cout<<"_____"<<y[i].y1<<' '<<y[i].y2<<' '<<y[i].d<<' '<<len[1]<<' '<<ans_y<<endl;
/*
cout<<"-________________________________"<<endl;
for(int j=1;j<=49;j++)
cout<<j<<"
"<<l[j]<<"
"<<r[j]<<"
"<<len[j]<<"
"<<f[j]<<endl;
*/
}
//
cout<<"_____"<<ans_y<<endl;
cout<<ans_x+ans_y<<endl;
}
return 0;
}

最后

以上就是清爽鸡为你收集整理的poj 1177 picture 线段树的全部内容，希望文章能够帮你解决poj 1177 picture 线段树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。