首先大概可以想到把所有連通塊分開作（如果兩條線段有相交的話就在他們之間連邊，這樣子形成的連通塊）。對於一個連通塊來說，可以發現如果答案是用這個連通塊的話，所有線段會形成一個類似生成樹的東西，但也不完全是，而如果把一條線段的每個單位長全部拆開來，他就的確變成了一棵生成樹了，因此就只要算出這個連通塊的線段總共覆蓋了多少個格點，再減一就會是這個連通塊砍完多餘線段後剩下的線段長度了，這個部份就可以用掃描線作了。但要注意到如果有兩條同方向的線段有交集要先處理掉，把直的和橫的線段都轉換成同方向沒有公共點的線段們。再來問題剩下要如何把每個連通塊都分出來，這裡反而比較麻煩，首先考慮一個比較樸素的算法，利用掃描線按照縱座標由下往上掃描，維護此時有哪些$x$座標有鉛直的線段，並且在遇到一條橫線時把所有他有交到的鉛直線和他都連到同一個連通塊中，這裡可以用 disjoint set 實作。問題是這樣太慢了，而注意到要被歸到同一個連通塊裡的鉛直線們是在座標上連續的一段區間，所以可以考慮用 Treap 加上 lazy tag 來維護所有的當前鉛直線，當我們要把一段區間的所有區間都歸到同一個連通塊時，就把那段區間的 Treap 切下來，在他的根放上 lazy tag 然後 merge 回去就好了。並且這時也可以順便算答案，因為當遇到一條橫線，我們把對應的區間切下來時，被切下來的這棵 Treap 的大小就是這條橫線交到的直線數量，有了這些值和每條線段所屬的連通塊後就不難算出每個連通塊的答案，取最大的那個就是我們要的了。
code :
#include<bits/stdc++.h> #define LL long long using namespace std; const int maxn=200000+10 ; int fa[maxn] ; int getfa(int x) { return fa[x]==x ? x : fa[x]=getfa(fa[x]) ; } inline void join(int x,int y){fa[getfa(x)]=getfa(y);} struct node { node *l,*r ; int id,size,val,fix,tag ; node(int _v,int _id) { l=r=NULL ; val=_v ; id=_id ; fix=rand() ; tag=0 ; size=1 ; } }; inline int size(node *u){return u ? u->size : 0 ;} inline void pull(node *u){if(u) u->size=size(u->l)+size(u->r)+1 ;} void push(node *u) { if(!u->tag) return ; if(u->l) { if(u->l->tag) join(u->tag,u->l->tag) ; else u->l->tag=u->tag , join(u->tag,u->l->id) ; } if(u->r) { if(u->r->tag) join(u->tag,u->r->tag) ; else u->r->tag=u->tag , join(u->tag,u->r->id) ; } u->tag=0 ; } node *merge(node *a,node *b) { if(!a||!b) return a ? a : b ; if(a->fix<b->fix) { push(a) ; a->r=merge(a->r,b) ; pull(a) ; return a ; } else { push(b) ; b->l=merge(a,b->l) ; pull(b) ; return b ; } } void split(node *u,node *&a,node *&b,int k) /// a : <=k , b : >k { if(!u){a=b=NULL ; return ;} push(u) ; if(u->val<=k) { a=u ; split(u->r,a->r,b,k) ; pull(a) ; } else { b=u ; split(u->l,a,b->l,k) ; pull(b) ; } } node *root=NULL ; void erase(int val) { node *a,*b,*c ; split(root,a,b,val-1) ; split(b,b,c,val) ; root=merge(a,c) ; } void insert(int val,int id) { node *a,*b ; split(root,a,b,val) ; root=merge(merge(a,new node(val,id)),b) ; } struct P { int x1,y1,x2,y2,id ; void scan(int _id) { scanf("%d%d%d%d",&x1,&y1,&x2,&y2) ; id=_id ; if(x1>x2||y1>y2) swap(x1,x2) , swap(y1,y2) ; } bool operator < (const P &rhs) const { if(x1==x2) return x1==rhs.x1 ? y1<rhs.y1 : x1<rhs.x1 ; else return y1==rhs.y1 ? x1<rhs.x1 : y1<rhs.y1 ; } }; inline void norm(vector<int> &v) { sort(v.begin(),v.end()) ; v.resize(unique(v.begin(),v.end())-v.begin()) ; } inline int ID(vector<int> &v,int x) { return lower_bound(v.begin(),v.end(),x)-v.begin() ; } vector<int> corx,cory ; /// coordinate vector<P> segx,segy ; void delete_seg(vector<P> &v,int t) { sort(v.begin(),v.end()) ; int j=1 ; for(int i=1;i<v.size();i++) { if(!t&&v[j-1].x1!=v[i].x1){v[j++]=v[i] ; continue ;} if(t &&v[j-1].y1!=v[i].y1){v[j++]=v[i] ; continue ;} if(!t&&v[i].y1<=v[j-1].y2) v[j-1].y2=max(v[j-1].y2,v[i].y2) ; else if(t &&v[i].x1<=v[j-1].x2) v[j-1].x2=max(v[j-1].x2,v[i].x2) ; else v[j++]=v[i] ; } v.resize(j) ; } void precal() { for(auto i : segx) corx.push_back(i.x1) , cory.push_back(i.y1) , cory.push_back(i.y2) ; for(auto i : segy) cory.push_back(i.y1) , corx.push_back(i.x1) , corx.push_back(i.x2) ; norm(corx) ; norm(cory) ; for(auto &i : segx) i.x1=i.x2=ID(corx,i.x1) , i.y1=ID(cory,i.y1) , i.y2=ID(cory,i.y2) ; for(auto &i : segy) i.y1=i.y2=ID(cory,i.y1) , i.x1=ID(corx,i.x1) , i.x2=ID(corx,i.x2) ; delete_seg(segx,0) ; delete_seg(segy,1) ; } struct event { int x,y,id,type ; bool operator < (const event &rhs) const { return y==rhs.y ? type<rhs.type : y<rhs.y ; } }ev[2*maxn]; inline void process_event(const event &e) { if(e.type==0) insert(e.x,e.id) ; else erase(e.x) ; } int cover[maxn] ; LL num[maxn],ans ; main() { srand(time(NULL)) ; int n ; scanf("%d",&n) ; for(int i=1;i<=n;i++) { P p ; p.scan(i) ; if(p.x1==p.x2) segx.push_back(p) ; else segy.push_back(p) ; } precal() ; for(auto i : segx) ans=max(ans,(LL)cory[i.y2]-cory[i.y1]) ; for(auto i : segy) ans=max(ans,(LL)corx[i.x2]-corx[i.x1]) ; for(int i=1;i<=n;i++) fa[i]=i ; int ecnt=0 ; for(auto i : segx) ev[ecnt++]=(event){i.x1,i.y1,i.id,0} , ev[ecnt++]=(event){i.x1,i.y2,i.id,1} ; sort(ev,ev+ecnt) ; node *a,*b,*c ; int j=0 ; for(int i=0;i<segy.size();i++) { int nowy=segy[i].y1 ; while(j<ecnt && (ev[j].y<nowy || (ev[j].y==nowy && !ev[j].type))) process_event(ev[j++]) ; split(root,a,b,segy[i].x1-1) ; split(b,b,c,segy[i].x2) ; cover[segy[i].id]=size(b) ; if(b) { if(b->tag) join(b->tag,segy[i].id) ; else b->tag=segy[i].id , join(b->id,b->tag) ; } root=merge(merge(a,b),c) ; } while(j<ecnt) process_event(ev[j++]) ; for(auto i : segx) num[getfa(i.id)]+=cory[i.y2]-cory[i.y1]+1 ; for(auto i : segy) num[getfa(i.id)]+=corx[i.x2]-corx[i.x1]+1-cover[i.id] ; for(int i=1;i<=n;i++) ans=max(ans,num[i]-1) ; printf("%lld\n",ans) ; }
沒有留言:
張貼留言