【CF429E】Points and Segments 歐拉回路
【CF429E】Points and Segments
題意：給你數軸上的n條線段$[l_i,r_i]$，你要給每條線段確定一個權值+1/-1，使得：對于數軸上的任一個點，所有包含它的線段的權值和只能是+1,-1或0。
$n\le 10^5$
題解：首先，我們用掃描線，整個數軸被分成若干個小區(qū)間。對于一個小區(qū)間，如果有偶數條線段包含它，則它的權值只能是0，否則可以是+1/-1。我們可以在所有權值為+1/-1的小區(qū)間處人為的增加一條線段，這樣的話我們只需要讓所有小區(qū)間權值都是0就行了。
嗯。。。每個小區(qū)間都被偶數個線段包含。。。權值和是0。。。想到什么呢？
如果我們給線段定向，向右的為+1，向左的為-1，那么我們要求的就是整個圖的歐拉回路！于是dfs求歐拉回路即可！
細節(jié)：如果我們直接建圖跑歐拉回路的話，則一條1-2,2-3的路徑其實是不合法的，因為2實際上被包含了2次，而我們再建圖時相當于直接越過了2這個點。解決方法是將區(qū)間變成左閉右開，即ri++。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=200010;
struct node
{
int x,k,org;
}p[maxn];
int n,m,cnt;
int last[maxn<<1],to[maxn<<1],nxt[maxn<<1],head[maxn],val[maxn],vis[maxn],used[maxn<<1];
inline int rd()
{
int ret=0; char gc=getchar();
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
bool cmp(const node &a,const node &b)
{
return a.x<b.x;
}
inline void add(int a,int b)
{
to[cnt]=b,nxt[cnt]=head[a],head[a]=cnt++;
}
void dfs(int x)
{
vis[x]=1;
for(int i=head[x];i!=-1;i=nxt[i]) if(!used[i])
used[i]=1,used[i^1]=2,dfs(to[i]);
}
int main()
{
//freopen("a.in","r",stdin);
n=rd();
int i;
for(i=1;i<=n;i++) p[i].x=rd(),p[i+n].x=rd()+1,p[i].k=1,p[i+n].k=-1,p[i].org=p[i+n].org=i;
sort(p+1,p+2*n+1,cmp);
memset(head,-1,sizeof(head));
for(i=1;i<=n+n;i++)
{
if(i==1||p[i].x>p[i-1].x)
{
m++;
if(!(i&1)) add(m-1,m),add(m,m-1);
}
if(p[i].k==1) last[p[i].org]=m;
else add(last[p[i].org],m),add(m,last[p[i].org]),last[p[i].org]=cnt-2;
}
for(i=1;i<=m;i++) if(!vis[i]) dfs(i);
for(i=1;i<=n;i++) printf("%d ",used[last[i]]&1);
return 0;
}
| 歡迎來原網站坐坐！ >原文鏈接<
浙公網安備 33010602011771號