CF1849C Binary String Copying 题解

wxzzzz · 2023-12-14 13:34:17 · 个人记录

思路

哈希判重。

因为只有 0 和 1，所以排序完之后必然前面一段为 0，后面一段为 1，把 0 和 1 的个数分别记为 cnt0 和 cnt1。

为了方便求出区间排序后的哈希值，可以不直接记录哈希值，而是记录 1_i 对全局哈希值的贡献，显然 s_i 的贡献为 s_i\times P^{n-i}，于是可以维护两个东西：

对于每次操作可以把整个序列分成四段：

整个序列的哈希值为 hs_{l-1}+hs1_r-hs1_{l+cnt0-1}+hs_n-hs_r。

代码

#include <bits/stdc++.h>
using namespace std;
int t, n, m, ans, s[200005];
unsigned long long p[200005], hs[200005], hs1[200005];
char c;
unordered_map<unsigned long long, bool> flag;
int main() {
    cin >> t;
    p[0] = 1;

    for (int i = 1; i <= 2e5; i++)
        p[i] = p[i - 1] * 131;

    while (t--) {
        cin >> n >> m;
        flag.clear(), ans = 0, c = '$';

        while (c != '0' && c != '1')
            c = getchar();

        for (int i = 1; i <= n; i++) {
            s[i] = s[i - 1] + c - '0';
            hs[i] = hs[i - 1] + (c - '0') * p[n - i];
            c = getchar();
        }

        for (int i = 1; i <= n; i++)
            hs1[i] = hs1[i - 1] + p[n - i];

        while (m--) {
            int l, r;
            unsigned long long hsh, cnt0, cnt1;
            cin >> l >> r;
            cnt1 = s[r] - s[l - 1], cnt0 = r - l + 1 - cnt1;
            hsh = hs[l - 1] + hs1[r] - hs1[l + cnt0 - 1] + hs[n] - hs[r];

            if (!flag[hsh])
                ans++, flag[hsh] = 1;
        }

        cout << ans << '\n';
    }

    return 0;
}