CF429E Points and Segments 题解

xkai · 2023-11-01 17:58:22 · 个人记录

一个很简单的做法，不需要欧拉回路或者二分图什么的图论知识，而且好写。

虽然题解满了，还是记录一下。

首先，因为样例没有无解的情况，猜测一定有解。

把线段按照左端点从小到大排序。如果第一条与第二条无交，第一条就随便染了。我们讨论有交的情况。

前两条线段必然异色。因为存在一个只包含前两条线段的区域 —— 如果不存在，那么我们可以人为在第二、三个左端点之间加入一段区域，这样只会让限制更强，但因为我们猜测了任何情况都有解，所以这一步转化后仍然有解。

然后此时把前两条线段绑在一起，发现这一个整体对于后续只会在 (\min\{r_1,r_2\},\max\{r_1,r_2\}] 的区域会有 \pm 1 的贡献，所以把这个区域看做一条新的线段。这样就是 n-1 条线段的子问题了。

还有点小问题，就是原题意说的是数轴上任意一点，但是实际上只看整点也是没有问题的，因为线段的端点都是整数，有交的话必然会有整点在交里面。主要方便代码实现。

Upd: 只关注整点是错的，虽然 CF 数据没有卡。给所有端点乘 2 即可。

需要一个左端点的小根堆，时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100010;
int fa[N],d[N];
int get(int x){
    if(!fa[x])return x;
    int r=get(fa[x]);
    if(r!=fa[x]){
        d[x]^=d[fa[x]];
    }
    return fa[x]=r;
}
int n,l[N],r[N];


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++)cin>>l[i]>>r[i],l[i]*=2,r[i]*=2;

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    for(int i=1;i<=n;i++)q.push({l[i],i});

    while(q.size()>1){
        int x=q.top().second;q.pop();
        int y=q.top().second;q.pop();
        if(r[x]<l[y]){
            q.push({l[y],y});
            continue;
        }
        if(r[x]<r[y]){
            fa[x]=y,d[x]=1;
            l[y]=r[x]+1;
            if(l[y]<=r[y]){
                q.push({l[y],y});
            }
        }
        else{
            fa[y]=x,d[y]=1;
            l[x]=r[y]+1;
            if(l[x]<=r[x]){
                q.push({l[x],x});
            }
        }
    }

    for(int i=1;i<=n;i++){
        get(i);
        cout<<d[i]<<' ';
    }
}