【题解】AGC056C 差分约束 思维 建模

· · 题解

好题，考察了对差分约束较深的理解。

首先限制区间 (l,r] 内恰好有 \frac {r-l} 2 个 1，可以考虑将限制转化为前缀和数组上的限制，即 S_r-S_l=\frac {r-l} 2，又因为前缀和本身的限制关系 S_{i}-S_{i-1}\in[0,1]，可以得出一个差分约束的关系：

\left\{ \begin{aligned} &S_r-S_l=\frac {r-l} 2\\ &S_i\leq S_{i-1}+1\\ &S_{i-1}\leq S_i\\ \end{aligned} \right.

直接将等于边拆成大于小于边做差分约束求字典序最小的 S，因为有负权边会被卡成 O(n^2)。

考虑将等号代表的关系使用一个代表元表示（S_i=S_{del(i)} + c_i），这样可以避免掉上面的负权边，但是第二类边可能会出现 S_i+c_i\leq S_j+c_j 移项得到 S_i\leq S_j+c_j-c_i 在 c_i > c_j 时同样会出现负权边。

考虑如何避免负权边，之所以会出现负权边是因为第一类的传递关系中会涉及到量的改变，我们试图建立一种直接的等价类关系来描述第一类关系：

考虑式子拆开成一个左侧只和 l 相关右侧只和 r 相关的等式：2S_r-r=2S_l-l，这样我们就把传递关系改成了一种等价关系，定义 x_i=2S_i-i，则上面三个式子分别变成了：

\left\{ \begin{aligned} &x_i=x_j\\ &x_i\leq x_{i-1}+1\\ &x_{i-1}\leq x_i+1\\ \end{aligned} \right.

（当然还有 x_i\neq x_{i-1}，这个条件会在后面的差分约束中天然被满足）

所以直接将所有第一种关系相同的 x_i 用同一个变量 x_{del(i)} 表示，然后对所有代表变量解决差分约束问题。

同样的，我们只需要最小化 x 的字典序就可以最小化 S 的字典序，直接 bfs 跑差分约束即可，因为我们求的是字典序最小解，可以证明不会出现 x_i=x_{i-1} 的情况。

接下来我们来证明使用差分约束系统构造出的解天然满足 x_i\neq x_{i-1}：首先缩起来的代表元素一定满足代表的都是奇偶性相同的元素，接下来这个差分约束系统只会对若干个奇数下标等价类的 x 的和偶数下标等价类的代表元之间连权为 1 的边，故我们构造出来的差分约束系统是一个有向的二分图（只在奇数代表元和偶数代表元之间有边），所以通过差分约束得到的最短路的奇偶性是确定的，只和下标奇偶性相关，故 x_i 和 x_{i-1} 奇偶性一定不同。

代码：（为方便使用了并查集进行缩等价类，复杂度会多一个 n\alpha(n)）

#include<bits/stdc++.h>
#define ll long long
#define all(x) x.begin(),x.end()
#define rep(i,x,y) for(auto i(x);i<=(y);++i)
#define Rep(i,x,y) for(auto i(x);i>=(y);--i)
using namespace std;
const int N = 1e6 + 20 ;
int n , m , x[N] , fa[N] , ptr ;
vector <int> ed[N] ;
inline int find (int x) {
    while (x ^ fa[x]) x = fa[x] = fa[fa[x]] ;
    return x; 
}
signed main ( ) {
    ios :: sync_with_stdio(false) , cin.tie(0) , cout.tie(0);
    cin >> n >> m ; iota (fa,fa+n+1,0);
    rep (i,1,m) {
        int l , r ; cin >> l >> r ; -- l ;
        int gl = find (l) , gr = find (r) ;
        if(fa[gl] ^ gr) fa[gl] = gr ;
    }
    rep (i,1,n) {
        ed[find(i)].emplace_back (find(i - 1)) ;
        ed[find(i - 1)].emplace_back (find(i)) ; 
    }
    memset(x,-1,sizeof x);  x[find(0)] = 0;
    vector <int> q = {find(0)} ;
    while (ptr < (int)q.size( )) {
        int u = q[ptr ++];
        for (int v : ed[u]) {
            if (!~x[v]) {
                x[v] = x[u] + 1 ;
                q.emplace_back(v) ;
            }
        }
    } 

    rep (i,1,n)
        if (x[find(i)] > x[find(i - 1)]) 
            cout << 0 ;
        else 
            cout << 1 ; 

    return 0 ;
}