【CF429E】Points and Segments
题意：给你数轴上的n条线段$[l_i,r_i]$，你要给每条线段确定一个权值+1/-1，使得：对于数轴上的任一个点，所有包含它的线段的权值和只能是+1,-1或0。
$n\le 10^5$
题解：首先，我们用扫描线，整个数轴被分成若干个小区间。对于一个小区间，如果有偶数条线段包含它，则它的权值只能是0，否则可以是+1/-1。我们可以在所有权值为+1/-1的小区间处人为的增加一条线段，这样的话我们只需要让所有小区间权值都是0就行了。
嗯。。。每个小区间都被偶数个线段包含。。。权值和是0。。。想到什么呢？
如果我们给线段定向，向右的为+1，向左的为-1，那么我们要求的就是整个图的欧拉回路！于是dfs求欧拉回路即可！
细节：如果我们直接建图跑欧拉回路的话，则一条1-2,2-3的路径其实是不合法的，因为2实际上被包含了2次，而我们再建图时相当于直接越过了2这个点。解决方法是将区间变成左闭右开，即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;
}