CF429E Points and Segments 题解

题目链接

点击打开链接

题目解法

真难啊/yun

把区间染成红色看作区间 \(+1\)，染成蓝色看作区间 \(-1\)，要求是每个点上的数 \(\in \{-1,0,1\}\)
可以选择的数有 \(-1,1\) 不太好做，我们考虑将限制变成每个点上的数只能为 \(0\)
我们记经过点 \(x\) 的线段数量为 \(cnt_x\)
如果 \(cnt_x\) 是奇数，那么我们添一条线段 \([x,x]\)，用来配平，这样就可以保证每个点上的数只能为 \(0\) 了

区间 \(+1/-1\) 仍然不太好做，我们考虑维护其差分数组
那么所有数都为 \(0\) 等价于 差分数组的所有数都为 \(0\)
二元关系考虑建图
我们把每条线段的 \(l_i, r_i+1\) 之间连边，现在的问题变成了给每条边定向，使得每个点出度 \(=\) 入度
这显然跑一遍欧拉回路即可

时间复杂度 \(O(n\log n)\)，瓶颈在离散化

#include <bits/stdc++.h>
#define F(i,x,y) for(int i=(x);i<=(y);i++)
#define DF(i,x,y) for(int i=(x);i>=(y);i--)
#define ms(x,y) memset(x,y,sizeof(x))
#define SZ(x) (int)x.size()-1
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int,int> pii;
template<typename T> void chkmax(T &x,T y){ x=max(x,y);}
template<typename T> void chkmin(T &x,T y){ x=min(x,y);}
template<typename T> void read(T &FF){
    FF=0;int RR=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') RR=-1;
    for(;isdigit(ch);ch=getchar()) FF=(FF<<1)+(FF<<3)+ch-48;
    FF*=RR;
}
const int N=200010;
int n,l[N],r[N],dsc[N],s[N];
int e[3*N],ne[3*N],h[N],idx;
void add(int x,int y){ e[idx]=y,ne[idx]=h[x],h[x]=idx++;}
void add_edge(int x,int y){ add(x,y),add(y,x);}
bool vis[N],tag[3*N],col[3*N];
void dfs(int u){
    vis[u]=1;
    for(int &i=h[u];~i;){
        if(tag[i]){ i=ne[i];continue;}
        tag[i]=tag[i^1]=1,col[i]=1;
        dfs(e[i]);
    }
}
int main(){
    read(n);
    int cnt=0;
    F(i,1,n){
        read(l[i]),read(r[i]);
        dsc[++cnt]=l[i],dsc[++cnt]=r[i]+1;
    }
    sort(dsc+1,dsc+cnt+1);
    cnt=unique(dsc+1,dsc+cnt+1)-dsc-1;
    ms(h,-1);
    F(i,1,n){
        l[i]=lower_bound(dsc+1,dsc+cnt+1,l[i])-dsc;
        r[i]=lower_bound(dsc+1,dsc+cnt+1,r[i]+1)-dsc;
        add_edge(l[i],r[i]);
        s[l[i]]++,s[r[i]]--;
    }
    F(i,1,cnt) s[i]+=s[i-1];
    F(i,1,cnt) if(s[i]&1) add_edge(i,i+1);
    F(i,1,cnt) if(!vis[i]) dfs(i);
    F(i,0,n-1) if(col[i*2]) printf("0 ");else printf("1 ");puts("");
    return 0;
}