欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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));
    }
}
相关标签: 合并