题目

在一个数轴上一共有 NN 段闭区间，它们可能有交。

现在你需要对它们黑白染色。对于每个位置 xx ，假设覆盖它的黑色区间个数为 bxbx，覆盖它的白色区间个数为 wxwx，要求满足 |bx−wx|≤1|bx−wx|≤1。区间 [l,r][l,r] 覆盖位置 xx 当且仅当 l≤x≤rl≤x≤r。

给出任意一种方案即可。

输入格式
第一行两个整数 NN。

接下来 NN 行，每行两个整数 li,rili,ri，表示一个 [li,ri][li,ri] 的区间。

输出格式
一共 NN 个 0/10/1 数，其中第 ii 个数为 11 表示第 ii 个区间染黑，否则为染黑。

样例一
Input
2
1 3
3 5
Output
1 0
样例二
Input
5
1 5
3 9
4 8
5 9
6 8
Output
1 0 0 1 1
数据范围
30%的数据满足：N≤20N≤20
60%的数据满足：N≤500N≤500
对于100%的数据满足：N≤105,0≤li≤ri≤109N≤105,0≤li≤ri≤109，数据保证至少有一组解。

思路

我们把黑的看成 $+1$，白的看成 $-1$。对于区间 $[l,r]$，做个差分，便可以看做是一条从 $l$ 到 $r+1$ 的边。

我们想要的是每个位置是 $0,\pm 1$，这个对应到差分上值有 $0,\pm 1,\pm 2$，不太好处理。但是如果我们想要的是每个位置都是 $0$，那么差分后每个位置都是 $0$，也就是说如果建出来的图存在欧拉回路，那么我们按照欧拉回路上的边的方向就可以得到一组解。

对于原题，可以发现为 $\pm 1$ 的一定是被覆盖奇数次的位置，那么新增一些区间来覆盖它们，使得每个位置都为偶数次。这个时候建出来的图也一定是存在欧拉回路的，于是我们就得到了一组满足每个位置都是 $0,\pm 1$ 的解。

代码

#include<bits/stdc++.h>
#define register
using namespace std;
const int N=2e5+77;
int fa[N],vl[N];
int gf(int a)
{if(a==fa[a])return a;int x=gf(fa[a]);vl[a]^=vl[fa[a]];fa[a]=x;return x;
}
pair<int,int>pp[N];
int main()
{int n,l,r;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&l,&r);pp[i*2-1]=std::make_pair(l,i);pp[i*2]=std::make_pair(r,i+n);fa[i]=fa[i+n]=i,vl[i+n]=1;}sort(pp+1,pp+2*n+1);int nw=0;for(int i=1;i<=2*n;i++){int no=pp[i].second;if(!nw)nw=no;else{if(gf(nw)!=gf(no)){vl[fa[no]]=vl[no]^vl[nw]^1;fa[fa[no]]=fa[nw];}nw=0;}}for(int i=1;i<=n;i++){gf(i);printf("%d ",vl[i]);}
}