题意: 给定 n 个矩形, 求他们的并的周长
n<=5e3,abs(x[i])<=1e4
思路: From https://www.cnblogs.com/kuangbin/archive/2013/04/10/3013437.html
真实 "线段" 树
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- #include
- using namespace std;
- typedef long long ll;
- typedef unsigned int uint;
- typedef unsigned long long ull;
- typedef pair<int,int> PII;
- typedef vector VI;
- #define fi first
- #define se second
- #define MP make_pair
- #define N 11000
- #define M 7010
- #define eps 1e-8
- #define pi acos(-1)
- #define oo 1e9
- #define MOD 10007
- struct node
- {
- int l,r,cnt,num,c;
- bool lc,rc;
- }t[N<<2];
- struct Line
- {
- int x1,x2,y,f;
- }line[N];
- bool cmp(Line a,Line b)
- {
- return a.y<b.y;
- }
- int x[N];
- void build(int l,int r,int p)
- {
- t[p].l=x[l];
- t[p].r=x[r];
- t[p].cnt=t[p].num=t[p].c=0;
- t[p].lc=t[p].rc=false;
- if(l+1==r) return;
- int mid=(l+r)>>1;
- build(l,mid,p<<1);
- build(mid,r,p<<1|1);
- }
- void calc(int p)
- {
- if(t[p].c>0)
- {
- t[p].cnt=t[p].r-t[p].l;
- t[p].num=1;
- t[p].lc=t[p].rc=true;
- return;
- }
- if(t[p].l+1==t[p].r)
- {
- t[p].cnt=t[p].num=0;
- t[p].lc=t[p].rc=false;
- }
- else
- {
- t[p].cnt=t[p<<1].cnt+t[p<<1|1].cnt;
- t[p].lc=t[p<<1].lc;
- t[p].rc=t[p<<1|1].rc;
- t[p].num=t[p<<1].num+t[p<<1|1].num;
- if(t[p<<1].rc&&t[p<<1|1].lc) t[p].num--;
- }
- }
- void update(int l,int r,Line e,int p)
- {
- if(t[p].l==e.x1&&t[p].r==e.x2)
- {
- t[p].c+=e.f;
- calc(p);
- return;
- }
- int mid=(l+r)>>1;
- if(e.x2<=t[p<<1].r) update(l,mid,e,p<<1);
- else if(e.x1>=t[p<<1|1].l) update(mid,r,e,p<<1|1);
- else
- {
- Line tmp=e;
- tmp.x2=t[p<<1].r;
- update(l,mid,tmp,p<<1);
- tmp=e;
- tmp.x1=t[p<<1|1].l;
- update(mid,r,tmp,p<<1|1);
- }
- calc(p);
- }
- int main()
- {
- //freopen("poj1177.in","r",stdin);
- //freopen("poj1177.out","w",stdout);
- int n;
- while(scanf("%d",&n)!=EOF)
- {
- int cnt=0;
- for(int i=0;i<=n-1;i++)
- {
- int x1,y1,x2,y2;
- scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
- line[cnt].x1=x1;
- line[cnt].x2=x2;
- line[cnt].y=y1;
- line[cnt].f=1;
- x[cnt++]=x1;
- line[cnt].x1=x1;
- line[cnt].x2=x2;
- line[cnt].y=y2;
- line[cnt].f=-1;
- x[cnt++]=x2;
- }
- sort(line,line+cnt,cmp);
- sort(x,x+cnt);
- int m=unique(x,x+cnt)-x;
- build(0,m-1,1);
- int ans=0;
- int last=0;
- for(int i=0;i<cnt-1;i++)
- {
- update(0,m-1,line[i],1);
- ans+=t[1].num*2*(line[i+1].y-line[i].y);
- ans+=abs(t[1].cnt-last);
- last=t[1].cnt;
- }
- update(0,m-1,line[cnt-1],1);
- ans+=abs(t[1].cnt-last);
- printf("%d\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2824343.html