题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$，$m$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$m(1 \leq m \leq 2 \times 10^5)$和长为$n$的01字符串$s$。

然后输入$m$个操作，每个操作输入两个下标$i$和$j(1 \leq i \leq j \leq n)$。

每次操作，复制一份$s$，记作$t$，然后把$t[i]$到$t[j]$排序，即区间$[i,j]$内的$0$排在$1$的前面。

这$n$次操作可以得到多少个不同的字符串？

输入样例

3
6 5
101100
1 2
1 3
2 4
5 5
1 6
6 4
100111
2 2
1 4
1 3
1 2
1 1
0
1 1

输出样例

3
3
1

算法

字符串哈希

对于每一个操作$[l,r]$，可以先得到前缀$s[1…l-1]$和$s[r+1…n]$的哈希值$prefix$和$suffix$，而考虑到字符串中只有$0$和$1$两种字符，利用前缀和计算出区间$[l,r]$内$0$和$1$的个数，就能直接把新串$t$的哈希值给计算出来（比较模板，详见代码）。把这个哈希值存入到一个集合中，进行完$m$次操作的集合大小就是我们能够获得的不同字符串个数。

复杂度分析

时间复杂度

字符串哈希和前缀和的预处理时间复杂度为$O(n)$，接下来每次操作都是有限几次常熟操作计算哈希值，因此算法整体的时间复杂度为$O(n+m)$。

空间复杂度

空间瓶颈的消耗在于前缀和数组和字符串哈希数组，都是$O(n)$的。因此，算法的额外空间复杂度为$O(n)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_set>

using namespace std;
typedef unsigned long long ULL;

const int N = 200010, BASE = 131;
int T, n, m, one[N];
char s[N];
ULL h[N], p[N], zh[N], oh[N];

ULL shash(int left, int right) {
    if(left > right) return 0;
    return h[right] - h[left - 1]*p[right - left + 1];
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        scanf("%s", s + 1);
        p[0] = 1;
        for(int i = 1; i <= n; i++) {
            one[i] = one[i - 1] + (s[i] == '1'? 1: 0);
            oh[i] = oh[i - 1]*BASE + '1';
            zh[i] = zh[i - 1]*BASE + '0';
            h[i] = h[i - 1]*BASE + s[i];
            p[i] = p[i - 1]*BASE;
        }
        unordered_set<ULL> st;
        for(int i = 1; i <= m; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            // 子串[l,r]中0和1的数量
            int ocnt = one[r] - one[l - 1];
            int zcnt = r - l + 1 - ocnt;
            // 计算哈希值
            ULL prefix = shash(1, l - 1), suffix = shash(r + 1, n);
            prefix = prefix*p[zcnt] + (zh[zcnt] - zh[0]*p[zcnt]);
            prefix = prefix*p[ocnt] + (oh[ocnt] - oh[0]*p[ocnt]);
            ULL shash_value = prefix*p[n - r] + suffix;
            st.insert(shash_value);
        }
        int ans = st.size();
        printf("%d\n", ans);
    }
    return 0;
}