Description：

给你很多区间，你可以给这些区间加一或减一，求一种方案使得最后每个数的绝对值都不超过 $1$ 。

$1\leqslant n\leqslant 10^5$

Solution：

差分一下，一个操作就是给 $l$ 加一或减一，给 $r+1$ 进行相反操作，然后题解告诉我们这可以让我们想到在这两个之间连一条无向边，给它确定是加还是减就相当于给边定向，这个时候可以发现如果形成了一个环的话，那么只要把向左的标记为 $-1$ ，向右的标记为 $1$ 就行了。

但是不一定全部形成环，也就是说可能有奇度数点，考虑怎么在合法的前提下处理他们，既然一个环的话每个点最后都被加了相同的次数，也就是说每个点最后都是零，而只要绝对值不超过一就合法，那么我们可以把所有奇数点拿出来排序，这一定有偶数个，然后把每个向下一个连边，这样最后成为很多环，再加上一些不相交的区间，这样组合出的答案一定是合法的，只要求一个欧拉回路给边定向就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 200010

struct edges

{

	int u,v;

}es[MAXN];

struct edge

{

	int to,nxt;

	bool tag;

}e[MAXN << 2];

int edgenum = 0;

int lin[MAXN];

int ind[MAXN];

void add(int a,int b)

{

	++ind[a];++ind[b];

	e[edgenum].to = b;e[edgenum].tag = true;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].tag = true;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int b[MAXN],tot = 0;

int P(int k)

{

	return lower_bound(b + 1,b + 1 + tot,k) - b;

}

bool v[MAXN];

void dfs(int k)

{

	v[k] = true;

	for(int i = lin[k];i != -1;i = e[i].nxt)

	{

		if(e[i].tag && e[i ^ 1].tag)

		{

			e[i].tag = false;

			dfs(e[i].to);

		}

	}

	return;

}

int c[MAXN];

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

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

	{

		scanf("%d%d",&es[i].u,&es[i].v);++es[i].v;

		if(es[i].u > es[i].v)swap(es[i].u,es[i].v);

		b[++tot] = es[i].u;b[++tot] = es[i].v;

	}

	sort(b + 1,b + 1 + 2 * n);

	tot = unique(b + 1,b + 1 + 2 * n) - b - 1;

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

	{

		add(P(es[i].u),P(es[i].v));

	}

	int last = 0;

	for(int i = 1;i <= tot;++i)

	{

		if(ind[i] & 1)

		{

			if(last == 0)last = i;

			else

			{

				add(last,i);

				last = 0;

			}

		}

	}

	for(int i = 1;i <= tot;++i)

	{

		if(!v[i])dfs(i);

	}

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

	{

		if(e[(i - 1) << 1].tag)printf("0 ");

		else printf("1 ");

	}

	return 0;

}