[洛谷P1525] 关押罪犯

题目链接：

传送门

题目分析：

由最后划分的结果在两个集合，联想到二分图
又由于答案具有单调性，即如果当前答案可以则更大的答案也一定可以，想到二分答案
思路：
二分答案，每次对于答案进行检验，检验时将\(<=\)答案的边都忽略掉，只保留比答案大的边，然后进行染色判定二分图，如果能构成二分图，说明这些点可以被分在两个不同的集合，且由二分图的定义可以得到，集合内的点之间无连边，而两集合之间的连边在本题的背景下等于被断掉了，即可以保证有分配方案使得冲突值小于二分到的答案

代码：

#include<bits/stdc++.h>
#define N (100000+5)
#define mod (1000000000+7)
using namespace std;
inline int read() {
    int cnt = 0, f = 1; char c;
    c = getchar();
    while(!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)) {
        cnt = cnt * 10 + c - '0';
        c = getchar();
    }
    return cnt * f;
}
int n, m, l1, l2, r1, r2, tot = 0;
int fa[N * 18], id[N][20], start[N * 18], base[20];
long long ans;
int get_father(int x) {
    if(fa[x] == x) return x;
    return fa[x] = get_father(fa[x]);
}

void merge(int x, int y) {
    int fx = get_father(x);
    int fy = get_father(y);
    if(fx > fy) swap(fx, fy);
    fa[fy] = fx;   //启发式合并 
}

int main() {
    base[0] = 1;
    for (register int i = 1; i <= 18; i++) base[i] = base[i-1] << 1;
    n = read(); m = read();
    if (n == 1) {
        printf("10\n");
        return 0;
    }
    for (register int i = 0; i <= 18; i++) 
        for (register int j = 1; j + base[i] - 1 <= n; j++) {
            id[j][i] = ++tot;
            fa[tot] = tot;
            start[tot] = j;
        }
        
/*-------------合并---------------*/
 
    for (register int i = 1; i <= m; i++) {
        l1 = read(); r1 = read(); l2 = read(); r2 = read();
        for (register int j = 18; j >= 0; --j) {
            if(l1 + base[j] - 1 <= r1) {
                merge(id[l1][j], id[l2][j]);
                l1 += base[j]; l2 += base[j];
            }
        }
    }

/*-------------下放-------------*/
 
    for (register int j = 18; j >= 1; --j) 
        for (register int i = 1; i + base[j] - 1 <= n; i++) {
            int f = get_father(id[i][j]); int s = start[f];
            merge(id[i][j - 1], id[s][j - 1]);
            merge(id[i + base[j - 1]][j - 1], id[s + base[j - 1]][j - 1]);
        }
        
    ans = 9;
    
    for (register int i = 2; i <= n; i++) {
        if(fa[id[i][0]] == id[i][0]) {
            ans *= 10;
            ans %= mod;
        }
    }
//  for (register int i = 1; i <= 18; i++) printf("%d ",base[i]);
//  return 0;
    printf("%lld\n", ans%mod);
    return 0;
}