倍增 + 并查集

VJspr4I - 萌萌哒

给定 $N$ 和 $Q$ 个限制 $L_{i 1},R_{i 1},L_{i 2},R_{i 2}$，问满足如下条件的字符串 $S = (S_1S_2S_3 \cdots S_n)$ 数量：①$1 \leqslant S_{1} \leqslant 9, 0 \leqslant S_{i} \leqslant 9$；②子串 $S[L_{i 1},R_{i 1}]$ 与 $S[L_{i 2},R_{i 2}]$ 完全相同。$N, Q \leqslant 10^{5}$。

若字符串的两位置相同 $S_{i}=S_{j}$ 则给 $i,j$ 连边，设连边后连通块个数为 $x$，那么答案为 $9\cdot 10^{x-1}$。

思路一 如果大区间已经相同，就没有必要合并小区间了。

并查集合并满足结合律以及幂等性，符合 RMQ 的适用条件。不需要一个一个枚举区间里的位置，而是将每个区间拆成若干个子区间的并，每个子区间的长度都是 2 的幂次，将子区间加入并查集。dsu[d].same(l, r) 表明 $S[\ell, \ell + 2^{d}) = S[r, r + 2^{d})$。每次复杂度 $\mathcal{O}(\log N)$。

预处理后将大区间的等量关系下放到两个小区间上。总复杂度 $\mathcal{O}[(N + Q)\log N]$。缺点是不支持在线询问。

constexpr int D = 20;
constexpr int mod = 1e9 + 7;

void solve() {
    int N, Q;
    cin >> N >> Q;
    
    vector<DisjointSets> dsu(D + 1, DisjointSets(N));
    
    while (Q--) {
        int L1, R1, L2, R2;
        cin >> L1 >> R1 >> L2 >> R2;
        L1--;
        L2--;
        int len = R1 - L1; // 区间长度 
        for (int d = D; d >= 0; d--) {
            if (len >> d & 1) {
                dsu[d].uno(L1, L2); // 把对应区间并起来 
                L1 += 1 << d;
                L2 += 1 << d;  // 倍增跳 
            }
        }
    }
    
    for (int d = D - 1; d >= 0; d--) {
        for (int i = 0; i + (1 << d) < N; i++) {
            int p = dsu[d + 1].find(i);
            // 前一半和后一半的并查集合并 
            dsu[d].uno(i, p);
            dsu[d].uno(i + (1 << d), p + (1 << d));
        }
    }
    
    int res = 1;
    for (int i = 0; i < N; i++) {
        if (dsu[0].find(i) == i) {
            if (res == 1) res = 9;
            else res = 1LL * res * 10 % mod;
        }
    }
    cout << res << endl;
}

思路二 真正有用的合并最多只有 $N-1$ 次，倍增跳到需要合并的位置。为了快速判断两个区间是否完全相同，用线段树维护哈希值。复杂度 $\mathcal{O}[(N + Q \log N)\log N]$。

struct Info {
    Z lr = 0;
    Z rl = 0;
    Z pw = 1;
    void apply(const Info& o)& {
        *this = o;
    }
};
Info operator + (const Info& l, const Info& r) {
    return {
        l.lr + r.lr * l.pw,
        r.rl + l.rl * r.pw,
        l.pw * r.pw
    };
}

constexpr int P = 1e9 + 7;
    
void solve() {
    int N, Q;
    cin >> N >> Q;

    SegmentTree<Info> seg(N);

    vector<Z> h(N);
    for (int i = 0; i < N; i++) { 
        h[i] = ull(rnd());
        seg.apply(i, { h[i], h[i], H });
    }

    vector<vector<int>> dsu(N);
    for (int i = 0; i < N; i++) { 
        dsu[i].push_back(i);
    }

    auto uno = [&](int x, int y) {
        x = dsu[x][0]; y = dsu[y][0];
        assert(x != y);
        if (dsu[x].size() < dsu[y].size()) swap(x, y);
        for (auto z : dsu[y]) {
            seg.apply(z, { h[x], h[x], H });
            dsu[x].push_back(z);
            dsu[z] = { x };
        }
    };

    while (Q--) {
        int L1, R1, L2, R2;
        cin >> L1 >> R1 >> L2 >> R2;
        L1--;
        L2--;

        while (L1 < R1) {
            for (int bit = 16; ~bit; bit--) {
                if (L1 + (1 << bit) <= N && L2 + (1 << bit) <= N && seg.query(L1, L1 + (1 << bit)).lr == seg.query(L2, L2 + (1 << bit)).lr) {
                    L1 += (1 << bit);
                    L2 += (1 << bit);
                }
            }
            if (L1 >= R1) break;
            uno(L1, L2);
        }
    }


    int res = 1;
    for (int i = 0; i < N; i++) {
        if (dsu[i][0] == i) {
            if (res == 1) res = 9;
            else res = 1LL * res * 10 % P;
        }
    }
    cout << res << endl;
}

用这种方法时间复杂度略高，码量也大。但对于下面这道题，你别无选择。

2022 NCPC K. Keyboard Queries

有一个神秘字符串 $s$ 包含 $N$ 个未知字母。$Q$ 次操作：

• 给定 $L_{i},R_{i}$ 表示子串 $s[L_{i}, R_{i}]$ 回文。
• 给定 $L_{i 1},R_{i 1},L_{i 2},R_{i 2}$，判断子串 $S[L_{i 1},R_{i 1}]$ 与 $S[L_{i 2},R_{i 2}]$ 是否完全相同。

void solve() {
    // 前面一样的 
    
    while (Q--) {
        int op;
        cin >> op;
        
        if (op == 1) {
            int L, R;
            cin >> L >> R;
            L--;
 
            while (L < R) {
                for (int d = 16; ~d; d--) {
                    if (L + (1 << d) <= N && R - (1 << d) >= 0) {
                        if (seg.query(L, L + (1 << d)).lr == seg.query(R - (1 << d), R).rl) {
                            L += (1 << d);
                            R -= (1 << d);
                        }
                    }
                }
                if (L >= R) break;
                uno(L, R - 1);
            }
        } else {
            int L1, R1, L2, R2;
            cin >> L1 >> R1 >> L2 >> R2;
            L1--;
            L2--;
            if (R2 - L2 != R1 - L1) {
                cout << "Not equal" << endl;
            } else if (seg.query(L1, R1).lr == seg.query(L2, R2).lr) {
                cout << "Equal" << endl;
            } else {
                cout << "Unknown" << endl;
            }
        }
    }
}

评注 我们最喜欢相同的东西，可以消消乐消掉！上述两种思路的核心思想均为倍增优化，并将区间划分与快速跳跃相结合，避免重复劳作，以降低时间复杂度。两种实现方式在具体设计上存在显著差异，最终却殊途同归 ~

VJspr11H - 2023 CCPC 深圳 - 相似基因序列问题

给定 $N$ 个长度为 $M$ 的字符串 $S_{1}, S_{2}, \dots,S_N$。定义两个字符串相似：最多只有 $K$ 个对应字母不同。$Q$ 组询问，每次给出一个长度为 $M$ 的字符串，问与几个 $S_{i}$ 相似。$1 \leqslant N, Q \leqslant 300$，$1 \leqslant M \leqslant 60,000$，$1 \leqslant K \leqslant 10$。

突破口是 $K$ 很小，也就是说字符串大部分是相同的，用倍增 / 二分跳到下一个不相同的位置。复杂度 $\mathcal{O}(Q N K \log M)$。

int n, q, m, k;
cin >> n >> q >> m >> k;
vector<Hash> s(n);
while (q--) {
    Hash t;
    int res = 0;
    for (int id = 0; id < n; ++id) {
        int kcnt = 0, i = 0;
        while (i < m) {  // 比较第 i 位是否相同 
            if (t(i, i + 1) != s[id](i, i + 1)) {
                if (++kcnt > k) break;
            }
            int len = m - i;
            while (len) {
                if (t(i, i + len) != s[id](i, i + len)) len /= 2;
                else break;
            }
            i += max(1, len);
        }
        res += kcnt <= k;
    }
    cout << res << endl;
}