题目描述

难度分:$1200$

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

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，$q(1 \leq q \leq 2 \times 10^5)$，长为$n$的字符串$s$，长为$n$的字符串$t$，都只包含小写英文字母。

然后输入$q$个询问，每个询问输入两个数$L$和$R$，表示下标从$L$到$R$的子串$(1 \leq L \leq R \leq n)s[L..R]$和$t[L..R]$。

对于每个询问，你可以修改$s[L..R]$中的若干字母，使得$s[L..R]$和$t[L..R]$排序后相等。输出最小修改次数。

注意：每个询问互相独立。

输入样例

3
5 3
abcde
edcba
1 5
1 4
3 3
4 2
zzde
azbe
1 3
1 4
6 3
uwuwuw
wuwuwu
2 4
1 3
1 6

输出样例

0
1
0
2
2
1
1
0

算法

前缀和

事实上就是在给定$L$和$R$的情况下，看看子串$s[L…R]$和$t[L…R]$的字母频数差别。操作次数其实就是$\frac{\Sigma_{letter=a}^{z}|counter1[letter]-counter2[letter]|}{2}$，$counter1[.]$和$counter2[.]$分别表示$.$在$s[L…R]$和$t[L…R]$中的频数。本质上就是多退少补，$s$串中相较于$t$串中少的字母需要通过把相较于$t$串多的字母改过来。

如此一来，只需要预处理出两个前缀和数组$ss$和$ts$即可$O(\Sigma)$计算这个求和操作，其中$\Sigma$表示字符集大小，本题中$\Sigma=26$。$ss[c][i]$表示字母$c$在前缀$s[1…i]$中的出现次数，$ts[c][i]$表示字母$c$在前缀$t[1…i]$中的出现次数。

复杂度分析

时间复杂度

预处理出$ss$和$ts$的时间复杂度为$O(n\Sigma)$。后续处理每个询问的时间复杂度为$O(\Sigma)$，处理$q$个询问的时间复杂度就是$O(q\Sigma)$。因此，整个算法的时间复杂度为$O((n+q)\Sigma)$。

空间复杂度

额外空间的瓶颈是$ss$和$ts$两个前缀和数组，空间复杂度为$O(n\Sigma)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010;
char s[N], t[N];
int T, n, q, ss[26][N], ts[26][N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &q);
        scanf("%s", s + 1);
        scanf("%s", t + 1);
        for(char c = 'a'; c <= 'z'; c++) {
            for(int i = 1; i <= n; i++) {
                ss[c - 'a'][i] = ss[c - 'a'][i - 1] + (s[i] == c? 1: 0);
                ts[c - 'a'][i] = ts[c - 'a'][i - 1] + (t[i] == c? 1: 0);
            }
        }
        while(q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            int ans = 0;
            for(char c = 'a'; c <= 'z'; c++) {
                int i = c - 'a';
                ans += abs(ss[i][r] - ss[i][l - 1] - (ts[i][r] - ts[i][l - 1]));
            }
            ans >>= 1;
            printf("%d\n", ans);
        }
    }
    return 0;
}