HDU 1828 Picture (线段树扫描线)
程序员文章站
2022-06-02 13:39:31
...
题意:
给你一堆长方形,求周长和
思路:
懒得思考就当码农!!
我们正常扫一次,比如平行于x轴向上扫描,我们不断用pre减去目前总长,这样弄完就是平行于x轴的周长和,可是处理y轴的时候,我们不能单纯的每次每次加上两段y的差值,因为我们并不知道有几段y,正常做法是维护有多少段x,这样就知道了这个区间对应了多少段y。可是这涉及了区间合并,好麻烦。。。那么我们强行再平行y轴扫一次就好了!!!
代码看着很长,其实都是复制粘贴
错误及反思:
其实也不是很难的题,只是重写这题的时候实在懒得维护了,程序员果然是ctrl+c和ctrl+v
代码:
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N= 5010;
int segtree[N<<3],lazy[N<<3];
int n;
vector<int> id[2];
struct L
{
int x1,x2,y,ta;
}line[2][N<<1];
int get_id(int x,int y){return lower_bound(id[y].begin(),id[y].end(),x)-id[y].begin();}
bool cmp(L w,L e)
{
return w.y<e.y;
}
void pushup(int l,int r,int rt,int x)
{
if(lazy[rt]) segtree[rt]=id[x][r+1]-id[x][l];
else if(l==r) segtree[rt]=0;
else segtree[rt]=segtree[rt<<1]+segtree[rt<<1|1];
}
void update(int L,int R,int v,int l,int r,int rt,int x)
{
if(L<=l&&R>=r)
{
lazy[rt]+=v;
pushup(l,r,rt,x);
return ;
}
int m=(l+r)/2;
if(L<=m) update(L,R,v,lson,x);
if(R>m) update(L,R,v,rson,x);
pushup(l,r,rt,x);
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=0;i<n;i++)
{
scanf("%d%d%d%d",&line[0][i*2].x1,&line[0][i*2].y,&line[0][i*2].x2,&line[0][i*2+1].y);
line[0][i*2+1].x1=line[0][i*2].x1;
line[0][i*2+1].x2=line[0][i*2].x2;
line[0][i*2].ta=1;
line[0][i*2+1].ta=-1;
id[0].push_back(line[0][i*2].x1);
id[0].push_back(line[0][i*2].x2);
line[1][i*2].x1=line[0][i*2].y;
line[1][i*2].x2=line[0][i*2+1].y;
line[1][i*2].y=line[0][i*2].x1;
line[1][i*2].ta=1;
line[1][i*2+1].x1=line[0][i*2].y;
line[1][i*2+1].x2=line[0][i*2+1].y;
line[1][i*2+1].y=line[0][i*2].x2;
line[1][i*2+1].ta=-1;
id[1].push_back(line[1][i*2].x1);
id[1].push_back(line[1][i*2].x2);
}
sort(line[0],line[0]+2*n,cmp);
sort(line[1],line[1]+2*n,cmp);
sort(id[0].begin(),id[0].end()),id[0].erase(unique(id[0].begin(),id[0].end()),id[0].end());
sort(id[1].begin(),id[1].end()),id[1].erase(unique(id[1].begin(),id[1].end()),id[1].end());
int ans=0;
int pre=0;
for(int i=0;i<n*2-1;i++)
{
int l=get_id(line[0][i].x1,0);
int r=get_id(line[0][i].x2,0)-1;
update(l,r,line[0][i].ta,0,id[0].size()-1,1,0);
ans+=abs(pre-segtree[1]);
pre=segtree[1];
}
ans+=segtree[1];
memset(segtree,0,sizeof(segtree));
memset(lazy,0,sizeof(lazy));
pre=0;
for(int i=0;i<n*2-1;i++)
{
int l=get_id(line[1][i].x1,1);
int r=get_id(line[1][i].x2,1)-1;
update(l,r,line[1][i].ta,0,id[1].size()-1,1,1);
ans+=abs(pre-segtree[1]);
pre=segtree[1];
}
ans+=segtree[1];
printf("%d\n",ans);
id[0].clear();
id[1].clear();
memset(segtree,0,sizeof(segtree));
memset(lazy,0,sizeof(lazy));
}
}
上一篇: Merge 标签与布局优化
下一篇: 并查集的基本思想和实现
推荐阅读