Codeforces Round 962 (Div. 3) 1996C - Sort
暴力解法：
计算l和r中不同字符的数量。首先，使用哈希数组存储’l~r’中所有字符出现的次数。将两个字母在两个字符串中出现的次数之差除以2，得到答案。
时间复杂度O（q（r-l+26）），最坏情况O（n+26）q）约为4*10^10。

正确解法：
使用前缀和优化时间复杂度，预先使用二维数组pre[N][26]进行预处理，其中pre[i][j]表示字符串前i个字符中j+1小写字母的出现次数。

时间复杂度：O（（n+q）26），最坏情况1.0410^7

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10;

int n, q;
int pre1[N][26], pre2[N][26];
string s1, s2;

void solve()
{
    cin >> n >> q;
    cin >> s1 >> s2;

    memset(pre1, 0, sizeof pre1);
    memset(pre2, 0, sizeof pre2);
    for (int i = 0; i < n; i++) {
        pre1[i + 1][s1[i] - 'a']++;
        pre2[i + 1][s2[i] - 'a']++;
        for (int j = 0; j < 26; j++) {
            pre1[i + 1][j] += pre1[i][j];
            pre2[i + 1][j] += pre2[i][j];
        }
    }

    while (q--) {
        int l, r;
        cin >> l >> r;
        int cnt = 0;
        for (int i = 0; i < 26; i++) {
            int cnt1 = pre1[r][i] - pre1[l - 1][i];
            int cnt2 = pre2[r][i] - pre2[l - 1][i];
            cnt += abs(cnt1 - cnt2);
        }
        cout << cnt / 2 << endl;
    }
}


int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    int t = 1;
    cin >> t;
    while (t--)
        solve();

    return 0;
}