Luogu P3295 [SCOI2016]萌萌哒

题目描述

https://www.luogu.com.cn/problem/P3295

Solution

每次操作相当于让两个区间对应位置相等，注意到最多进行 $n$ 次并查集的 $merge$ 操作

我们考虑一个比较神奇的倍增操作，我们将一个点变成 $log$ 个

坑

$fa[u][k]$ 表示从 $u$ 开始长度为 $k$ 的区间

#include <iostream>
#include <cstdio>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 1000000007;

ll pow_mod(ll x, ll n) {
    ll s = 1;
    for (; n; n >>= 1) {
        if (n & 1) s = s * x % p;
        x = x * x % p;
    }
    return s; 
}

int n, m;

int fa[maxn][21], Log[maxn];
void init() { Log[0] = -1;
    for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
    for (int j = 0; j <= 20; ++j)
        for (int i = 1; i <= n; ++i) fa[i][j] = i;
}

int find(int x, int k) { return fa[x][k] == x ? x : fa[x][k] = find(fa[x][k], k); }

void merge(int k, int l1, int l2) {
    int f1 = find(l1, k), f2 = find(l2, k);
    if (f1 == f2) return ; fa[f1][k] = f2;
    if (!k) return ;
    merge(k - 1, l1, l2);
    merge(k - 1, l1 + (1 << k - 1), l2 + (1 << k - 1));
} 

int main() {
    cin >> n >> m; init(); 
    for (int i = 1; i <= m; ++i) {
        int l1, l2, r1, r2, k; scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        k = Log[r1 - l1 + 1];
        merge(k, l1, l2);
        merge(k, r1 - (1 << k) + 1, r2 - (1 << k) + 1); 
    } int s = 0; 
    for (int i = 1; i <= n; ++i) if (find(i, 0) == i) ++s;
    cout << 9 * pow_mod(10, s - 1) % p << endl; 
    return 0;
}