Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1885 Accepted Submission(s): 946
题目链接:HDU 1264
连离散化都不用的水题,有一个坑点就是题目给的两个对角线坐标不一定是左下、右上这样一个顺序,或者也可能是副对角线上的点,需要判断一下
代码:
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=1e3+7;
struct seg
{
int l,mid,r;
int cnt,len;
};
struct Line
{
int l,r,h,flag;
bool operator<(const Line &t)const
{
return h<t.h;
}
};
seg T[N<<3];
Line xline[N<<1];
inline void pushup(int k)
{
if(T[k].cnt>0)
T[k].len=T[k].r-T[k].l+1;
else
{
if(T[k].l==T[k].r)
T[k].len=0;
else
T[k].len=T[LC(k)].len+T[RC(k)].len;
}
}
void build(int k,int l,int r)
{
T[k].l=l;
T[k].r=r;
T[k].mid=MID(l,r);
T[k].len=T[k].cnt=0;
if(l==r)
return ;
build(LC(k),l,T[k].mid);
build(RC(k),T[k].mid+1,r);
pushup(k);
}
void update(int k,int l,int r,int flag)
{
if(l<=T[k].l&&T[k].r<=r)
{
T[k].cnt+=flag;
pushup(k);
}
else
{
if(r<=T[k].mid)
update(LC(k),l,r,flag);
else if(l>T[k].mid)
update(RC(k),l,r,flag);
else
update(LC(k),l,T[k].mid,flag),update(RC(k),T[k].mid+1,r,flag);
pushup(k);
}
}
int main(void)
{
int n,i;
int xa,ya,xb,yb;
int cnt=0;
while (scanf("%d%d%d%d",&xa,&ya,&xb,&yb))
{
if(xa==-1&&xb==-1&&ya==-1&&yb==-1)
{
int ans=0;
build(1,0,N);
sort(xline,xline+cnt);
for (i=0; i<cnt-1; ++i)
{
update(1,xline[i].l,xline[i].r-1,xline[i].flag);
ans=ans+(xline[i+1].h-xline[i].h)*T[1].len;
}
printf("%d\n",ans);
cnt=0;
}
else if(xa==-2&&xb==-2&&ya==-2&&yb==-2)
{
int ans=0;
build(1,0,N);
sort(xline,xline+cnt);
for (i=0; i<cnt-1; ++i)
{
update(1,xline[i].l,xline[i].r-1,xline[i].flag);
int dh=(xline[i+1].h-xline[i].h);
ans=ans+dh*T[1].len;
}
printf("%d\n",ans);
cnt=0;
break;
}
else
{
if(xa>xb)
swap(xa,xb);
if(ya>yb)
swap(ya,yb);
xline[cnt++]=(Line){xa,xb,ya,1};
xline[cnt++]=(Line){xa,xb,yb,-1};
}
}
return 0;
}
HDU 1264 Counting Squares(线段树求面积的并)
原文:http://www.cnblogs.com/Blackops/p/6028711.html