最大的开源网站,做网站的国标有哪些,广州网站设计成功柚米,企业宣传网站公司问题
给您两个长度为 #x1d45b;n 的字符串 #x1d44e;a 和 #x1d44f;b 。然后#xff0c;您(被迫)回答 #x1d45e;q 个问题。
对于每个查询#xff0c;你都会得到一个由 #x1d459;l 和 #x1d45f;r 限定的范围。在一次操作中#xff0c;您可以选择一…问题
给您两个长度为 n 的字符串 a 和 b 。然后您(被迫)回答 q 个问题。
对于每个查询你都会得到一个由 l 和 r 限定的范围。在一次操作中您可以选择一个整数 i ( ≤≤l≤i≤r ) 和集合 aix 其中 x 是您想要的任何字符。输出必须执行的最少操作数以便 ([..])([..])sorted(a[l..r])sorted(b[l..r]) 。**对一个查询执行的操作不会影响其他查询。
对于任意字符串 c ([..])sorted(c[l..r]) 表示由按词典顺序排列的字符 ,1,...,cl,cl1,...,cr 组成的子串。
输入
第一行包含 t ( 1≤≤10001≤t≤1000 )--测试用例数。( 1≤≤10001≤t≤1000 ) - 测试用例的数量。
每个测试用例的第一行包含两个整数 n 和 q ( 1≤,≤2⋅1051≤n,q≤2⋅105 ) - 两个字符串的长度和查询次数。
下面一行包含长度为 n 的 a 。可以保证 a 只包含小写拉丁字母。
下面一行包含长度为 n 的 b 。保证 b 只包含小写拉丁字母。
下面的 q 行包含两个整数 l 和 r ( 1≤≤≤1≤l≤r≤n ) - 查询范围。
保证所有测试用例中的 n 和 q 之和不超过 2⋅1052⋅105 。
输出
对于每个查询在新行中输出一个整数即需要执行的最少操作数。
做法
题目大意就是给你两个字符串然后问你在某个区间内修改几次能让这一区间排完序后完全相同。对于一个区间两个字符串完全相同26个字母的个数都要相同。我们就对两个串分别求前缀和然后看26个字母个数的差异然后除以二就是答案了。
#includebits/stdc.h
using namespace std;
int t,n,q;
string a,b;
int qzh1[30][200010],qzh2[30][200010];
int main(){scanf(%d,t);while(t--){scanf(%d%d,n,q);cinab;for(int j0;j26;j){for(int i1;in;i){if(a[i-1]-aj) qzh1[j][i]qzh1[j][i-1]1;else qzh1[j][i]qzh1[j][i-1];if(b[i-1]-aj) qzh2[j][i]qzh2[j][i-1]1;else qzh2[j][i]qzh2[j][i-1];}}while(q--){int l,r;scanf(%d%d,l,r);int ans0;for(int i0;i26;i){ansabs(qzh1[i][r]-qzh1[i][l-1]-qzh2[i][r]qzh2[i][l-1]);}coutans/2endl;}}
}
