Codeforces Round 962 (Div. 3) Problem C

原题链接：

题目大意：

截取l~r这段字符串来比较，可进行替换单个字符的操作，问，要使得排成字典序的这两个字符串相同，要进行的最少操作。

简述就是统计每个字符的个数，然后把个数差分别加起来，因为题目中给字符串内只含有小写字母。所以可以开一个二维数组去存每个遍历时刻下每个字母的个数总和，那么显而易见的，这题就是一道非常明显的前缀和题。

那么按照上述描述的解法，看样例1就是这个过程，很清楚的知道最后输出的是0

那么再看下一条样例：

很清楚的知道最后num的值为2，但因为两个字符串分别加上了缺失字符的数量，所以最后的结果要除二，所以最后输出的结果就是1

而这个过程的代码也不难写，只要运用二维数组就可以完成这个字母前缀和的过程，那么直接上代码：

#include <bits/stdc++.h>
using namespace std;
int t,n,q,l,r,num;
string s,s1;
void prob(){
	cin>>n>>q;
	vector <vector <int> > a (n+1,vector <int> (26,0));
	vector <vector <int> > b (n+1,vector <int> (26,0));
	cin>>s>>s1;
	for(int i=0;i<n;i++){
		a[i+1][int(s[i]-'a')]++;
		b[i+1][int(s1[i]-'a')]++;
		for(int j=0;j<26;j++){
			a[i+1][j] += a[i][j];
			b[i+1][j] += b[i][j];
		}	
	}
	while(q--){
		num = 0;
		cin>>l>>r;
		for(int i=0;i<26;i++)
			num += abs((a[r][i]-a[l-1][i])-(b[r][i]-b[l-1][i]));
		cout<<num/2<<endl;
	}
	return;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>t;
    while(t--)
    	prob();
    return 0;
}