首页 > 代码库 > hdu1828(线段树+扫描线)

hdu1828(线段树+扫描线)

又知道了线段树的一种用法,除了单点更新,区间更新,还有这种在一段线段上标号但不往下推。 真是神奇

hdu1828

#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <queue>#include <map>#include <stdlib.h>using namespace std;#define N 5050struct RECT{    int x1,y1,x2,y2;}g[N];struct LINE{    int k,b,d;    int flag;}line[4*N];int ans=0;int n;int l[200000],r[200000],mark[200000],yb[200000],yd[200000],num[200000];int cmp(LINE x,LINE y){    return x.k<y.k;}void build(int tl,int tr,int s){    l[s]=tl; r[s]=tr;    mark[s]=0;yb[s]=0; yd[s]=0; num[s]=0;    if(tl==tr) return ;    int mid=(tl+tr)/2;    build(tl,mid,2*s);    build(mid+1,tr,2*s+1);}void up(int s){    if(mark[s]>0)    {        num[s]=1;        yb[s]=1;        yd[s]=1;    }    else    {        if(l[s]==r[s])        {            num[s]=0;            yb[s]=0;            yd[s]=0;        }        else        {            if(yd[2*s]==1&&yb[2*s+1]==1)                num[s]=num[2*s]+num[2*s+1]-1;            else num[s]=num[2*s]+num[2*s+1];            yb[s]=yb[2*s];            yd[s]=yd[2*s+1];        }    }}void update(int tl,int tr,int sign,int s){    if(tl==l[s]&&tr==r[s])    {        mark[s]+=sign;        up(s);        return ;    }    int mid=(l[s]+r[s])/2;    if(tr<=mid) update(tl,tr,sign,2*s);    else if(tl>mid) update(tl,tr,sign,2*s+1);    else    {        update(tl,mid,sign,2*s);        update(mid+1,tr,sign,2*s+1);    }    up(s);}void fuc(){    int cnt=0;    int mix=200000000,mxx=-200000000;    for(int i=0;i<n;i++)    {        line[cnt].k=g[i].y1;        line[cnt].b=g[i].x1;        line[cnt].d=g[i].x2-1;//注意可能为负的        line[cnt].flag=1;        cnt++;        mix=min(mix,g[i].x1);        mxx=max(mxx,g[i].x2-1);        line[cnt].k=g[i].y2;        line[cnt].b=g[i].x1;        line[cnt].d=g[i].x2-1;        line[cnt].flag=-1;        cnt++;    }    sort(line,line+cnt,cmp);    build(mix,mxx,1);    for(int i=0;i<cnt-1;i++)    {        update(line[i].b,line[i].d,line[i].flag,1);        ans += (line[i+1].k-line[i].k)*2*num[1];    }}int main(){    while(scanf("%d",&n)!=EOF)    {        for(int i=0;i<n;i++)        {            scanf("%d%d%d%d",&g[i].x1,&g[i].y1,&g[i].x2,&g[i].y2);            g[i].x1+=10011;            g[i].x2+=10011;            g[i].y1+=10011;            g[i].y2+=10011;        }        if(n==0)        {            printf("0\n");            continue;        }        ans=0;        fuc();        //        for(int i=0;i<n;i++)        {            swap(g[i].x1,g[i].y1);            swap(g[i].x2,g[i].y2);        }        fuc();        printf("%d\n",ans);    }    return 0;}

 

hdu1828(线段树+扫描线)