CodeForces

Luogu翻译

分析

记红色的区间为$1$，蓝色的区间为$-1$，那么对于任意一个点，覆盖它的线段的权值和的绝对值不超过$1$。

那么可以对于每个区间 $[l,r]$ ，从 $l$ 向 $r+1$ 连无向边。此时也就变成了每个点的入度与出度之差的绝对值不超过$1$。

发现奇度数点不太好搞。可以按照横坐标排个序，然后一一匹配。这样子只要求一条欧拉回路就行了。

求出欧拉回路后给每条边染色，正向经过的染红色，反向经过的染蓝色即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

struct Edge { int v,id,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v,int id) {
    static int cnt=1;
    e[++cnt]=(Edge){v,id,head[u]},head[u]=cnt;
    e[++cnt]=(Edge){u,id,head[v]},head[v]=cnt;
}

int n;
struct segment { int l,r; } a[N];
int s[N];
int deg[N],vis[N],mark[N],ans[N];

inline void dfs(int u) {
    vis[u]=1;
    for (re int& i=head[u];i;i=e[i].nxt) {
        if (mark[i]) continue;
        int v=e[i].v,id=e[i].id;
        mark[i]=mark[i^1]=1,ans[id]=(u<v);
        dfs(v);
    }
}

int main() {
    n=read(); int top=0;
    for (re int i=1;i<=n;++i) {
        a[i].l=read(),a[i].r=read()+1;
        s[++top]=a[i].l,s[++top]=a[i].r;
    }
    //离散化
    sort(s+1,s+top+1); top=unique(s+1,s+top+1)-s-1;
    for (re int i=1;i<=n;++i) {
        a[i].l=lower_bound(s+1,s+top+1,a[i].l)-s;
        a[i].r=lower_bound(s+1,s+top+1,a[i].r)-s;
        addEdge(a[i].l,a[i].r,i);
        ++deg[a[i].l],++deg[a[i].r];
    }
    //匹配奇度数点
    for (re int i=1,last=0;i<=top;++i) {
        if ((deg[i]&1)==0) continue;
        if (last) addEdge(last,i,0),last=0;
        else last=i;
    }
    //求解
    for (re int i=1;i<=top;++i)
        if (!vis[i]) dfs(i);
    for (re int i=1;i<=n;++i) printf("%d ",ans[i]); puts("");
    return 0;
}