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;
}