题解：P12838 [蓝桥杯 2025 国 B] 子串去重

· · 题解

以下设 |S| 表示字符串 S 的长度，设 |\Sigma| = 26 表示字符集大小。

首先，显然有单次查询 O(|S| + |\Sigma|) 的暴力做法：对于每次询问，O(|S|) 暴力扫区间，遇到没出现过的字符，就把它加到去重的结果里，然后 O(|\Sigma|) 地比较。

为什么可以 O(|\Sigma|) 地比较呢？因为一段区间去重后，留下的字符必然不超过 |\Sigma| 个。

那么，我们或许可以换个思路，不从区间入手，而是从字符入手：O(|\Sigma|) 地枚举字符，找到其在区间里第一次出现的位置，同样得到区间去重后的结果，然后进行比较。

如果还是 O(|S|) 暴力扫区间，单次查询的时间复杂度为 O(|\Sigma||S|)。

诶？怎么还变慢了？

别急，这个做法的瓶颈在于找到每个字符在区间里第一次出现的位置。这似乎是好优化的！

考虑对于每个字符 c，都维护出现次数的前缀和，那么对于区间 [l, r] 里的每个位置 x，都可以 O(1) 求出区间 [l, x] 内字符 c 的出现次数。

于是你惊奇地发现，出现次数是具有单调性的（单调不下降）！所以可以二分查找第一次出现的位置。

这样，单次查询的时间复杂度就优化到了 O(|\Sigma|\log |S|)。

预处理前缀和，加上 m 次查询，总时间复杂度为 O(|\Sigma||S| + m|\Sigma|\log |S|)，空间复杂度为 O(|\Sigma||S|)。

#define pir pair<int, int>
const int N = 100005;
char s[N];
int n, sum[26][N];
inline int get_front(int L, int R, int c){
    int l = L, r = R;
    while(l + 1 < r){
        int mid = (l + r) >> 1;
        if(sum[c][mid] - sum[c][L - 1]) r = mid;
        else l = mid;
    }
    if(sum[c][l] - sum[c][L - 1]) return l;
    else return r;
}
inline vector<int> ask(int l, int r){
    vector<pir> pos;
    for(int i = 0; i < 26; i++)
        if(sum[i][r] - sum[i][l - 1])
            pos.push_back({get_front(l, r, i), i});
    sort(pos.begin(), pos.end());
    vector<int> res;
    for(auto x : pos) res.push_back(x.second);
    return res;
}
signed main(){
    scanf("%s", s + 1), n = strlen(s + 1);
    for(int i = 1; i <= n ; i++){
        for(int j = 0; j < 26; j++) sum[j][i] = sum[j][i - 1];
        ++sum[s[i] - 'a'][i];
    }
    for(int m = read(); m; m--){
        int la = read(), ra = read(), lb = read(), rb = read();
        vector<int> a = ask(la, ra), b = ask(lb, rb);
        int len_a = a.size(), len_b = b.size(), ans = 0;
        for(int i = 0; i < len_a && i < len_b; i++) ans += (a[i] != b[i]);
        if(len_b < len_a) swap(len_a, len_b);
        print(ans + len_b - len_a), putchar('\n');
    }
    return 0;
}