UOJ356 【JOI2017春季合宿】Port Facility

时间：2021-01-05 14:26:54

暴力就是O(n^2)连边，二分图，这样只有22分。

我们考虑优化建边，我们按照左端点排序，对于一个新加进来的线段，我们向左端点距其最近的和他相交的线段连边，别的相交的我们连同色边，当一个点连了两条同色边我们就把它删掉，复杂度O(nlogn)，边数O(n)。

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <set>

 #define N 2000005

 #define inf 1000000000

 #define mod 1000000007

 using namespace std;

 set <int> s1,s2;

 set <int> :: iterator it;

 int n,nxt[N],pre[N],Ans,vis[N],sta[N],top;

 struct data{int l,r;}d[N];

 bool cmpl(data a,data b){return a.l<b.l;}

 int e=,head[N];

 struct edge{int v,w,next;}ed[N<<];

 void add(int u,int v,int w){ed[e]=(edge){v,w,head[u]};head[u]=e++;}

 void dfs(int x,int c){

     vis[x]=c;

     for(int i=head[x];i;i=ed[i].next){

         int v=ed[i].v;

         if(vis[v]!=-&&vis[v]!=c^ed[i].w){puts("");exit();}

         if(vis[v]!=-)continue;

         dfs(v,c^ed[i].w);

     }

 }

 int main(){

     scanf("%d",&n);

     for(int i=;i<=n;i++)

         scanf("%d%d",&d[i].l,&d[i].r);

     sort(d+,d+n+,cmpl);

     s1.insert(-inf);s1.insert(inf);

     s2.insert(-inf);s2.insert(inf);

     for(int i=,x,y;i<=n;i++){

         x=d[i].l,y=d[i].r;

         it=s1.upper_bound(y);

         nxt[y]=*it;it--;pre[y]=*it;

         if((*it)>x)add(y,*it,),add(*it,y,);

         it=s2.upper_bound(y);it--;

         for(;(*it)>x;it--){

             if(pre[*it]>x)add(*it,pre[*it],),add(pre[*it],*it,),pre[*it]=-inf;

             if(nxt[*it]<y)add(*it,nxt[*it],),add(nxt[*it],*it,),nxt[*it]=inf;

             if(pre[*it]==-inf&&nxt[*it]==inf)sta[++top]=*it;

         }

         while(top)s2.erase(sta[top--]);

         s1.insert(y);s2.insert(y);

     }

     Ans=;

     memset(vis,-,sizeof vis);

     for(int i=;i<=n;i++)if(vis[d[i].r]==-){

         dfs(d[i].r,);

         Ans=(Ans<<)%mod;

     }

     printf("%d\n",Ans);

 }

相关文章