Atcoder ABC155F Perils in Parallel 【构造图】【差分】【离散化】

Perils in Parallel

题目

图片说明
意思就是有N个分布在不同点的炸弹，其状态有激活和未激活两种，我们可以有M个区间可供选择，对选择区间内的炸弹状态反转。问，是否可以将所有的炸弹置为未激活状态。若可以，请输出从小到大输出选择了那些区间。

分析

首先进行离散化，以题目样例1举例：

原数据：
图片说明
离散化之后的数据，在最后加入一个虚拟的炸弹，便于之后差分操作：
因为对[l,r]操作，差分就是对l,和r+1操作，所以多加一个。还有这里的差分是用的异或来代替

之后进行差分：

对应坐标压缩之后，所以原M个区间就变成如下对l，和r+1进行反转操作了：

很明显，我们只需要选择1，4反转一下，2，3反转一下，差分数组就全变成0了。
很明显，现在我们的目的就是为了让差分数组所有元素变成0，这样在还原的时候，所有炸弹就是未激活状态。
我们把每一个差分操作(对l和r+1的操作)想像成图的一条边构成一个图。图里面所有点只有0和1，然后每条边都可以反转一下，让两端的状态反转。现在我们的目的就成了让图中所有结点通过反转全变成0

注意，有些点不在区间两端，所有它是单独的一个联通块。整个图有可能不是联通的。我们需要对图中每一个联通块进行处理。

处理每一个联通块

我们选择一个结点作为最高点，往下递归。我以图例进行演示，文字不好描述
图片说明
从1号点开始递归，当它递归到叶子结点时，叶子结点就返回其状态，比如递归到了5，发现5号点状态是0，则3-5这条边是不能够反转的，因为反转之后5号点就变成了1了。然后递归到了6，发现其状态是1，则必须反转，反转之后，6号点变成0，3号点变成0，然后发现3号点状态变成0了，则2-3这条边不能够反转。之后递归到7号点，其为1，反转4-7边，4号点变成1，反转2-4边，最后2号点为0，1-2边不反转。现在全部图就变成了0了。也就对应这差分数组全是0，差分还原之后也全是0

AC代码

#include <iostream>
#include <algorithm>
#include <vector>
#define fs first
#define sc second
using namespace std;
const int maxn = 1e5+10;
using pii = pair<int,int>;

int N,M;
vector<pii> G[maxn];
vector<int> ans;//保存选的边
pii arr[maxn];
bool vis[maxn];
int ca[maxn];//差分数组

int dfs(int u){
    vis[u] = true;
    int st = ca[u];
    for(auto v:G[u]){
        if(vis[v.fs]) continue;
        int r = dfs(v.fs);
        if(r) { //如果子图传递回来的是1，则必须进行反转
            ans.push_back(v.sc); //保存边
            st ^= 1;//异或一下
        }
    }
    return st;
}
int main(){
    cin>>N>>M;
    for(int i = 1;i<=N;i++) scanf("%d %d",&arr[i].fs,&arr[i].sc);
    sort(arr+1,arr+N+1);
    ca[1] = arr[1].sc;
    for(int i = 2;i<=N+1;i++) ca[i] = arr[i].sc^arr[i-1].sc;//构造差分数组，后一项异或前一项就是差值
    for(int i = 1;i<=M;i++){
        int a,b;
        scanf("%d %d",&a,&b);
        int l = lower_bound(arr+1,arr+N+1,pii(a,0))-arr;//因为我想要下标从1开始，就没有多减1
        int r = upper_bound(arr+1,arr+N+1,pii(b,1))-arr; 
        if(l == r) continue; //对同一个地方异或两次，可以直接忽略掉
        G[l].emplace_back(r,i);//把边的编号一起绑定
        G[r].emplace_back(l,i);
    }
    for(int i = 1;i<=N;i++){
        if(vis[i]) continue;
        if(dfs(i)){
            cout<<-1<<endl;
            return 0;
        }
    }
    cout<<ans.size()<<endl;
    sort(ans.begin(),ans.end());
    for(auto v:ans) cout<<v<<" ";

    return 0;
}