字符串查询
给你单词 S 和 Q 个询问。
每次询问，你会得到正整数 A,B,C 和 D。
我们令单词 X 由 S 的第 A 到 B 个字母组成，单词 Y 由 S 的第 C 到 D 个字母组成。
你需要回答，是否能够重新排列单词 Y 中的字母，得到单词 X。
输入格式
第一行一个单词 S，仅由小写字母组成。
第二行一个正整数 Q。
接下来 Q 行，每行四个整数 A,B,C,D。
输出格式
每次询问，如果能，输出 DA，否则输出 NE。
数据范围
1≤|S|≤50000,
1≤Q≤50000,
1≤A≤B≤|S|,
1≤C≤D≤|S|,
B−A=D−C
输入样例：
kileanimal
2
2 2 7 7
1 4 4 7
输出样例：
DA
NE
思路
如果每次对范围内的字符进行排序进行一一匹配显然会tle
那么是否有一种方法可以不进行排序匹配也能够预判结果呢，答案是显然的，我们只需要知道范围内每个字母的数量即可，一旦某个字母的数量不匹配，那么我们就可以推断匹配是不成功的
开始得知范围内某个字母的数量，我们可以利用前缀和的思想先记录\(1-r(1 \le r \le n )\)的每个字母的数量即可
代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int cnt[N][26];
char s[N];
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin >> s + 1;
int len = strlen(s + 1);
for(int i = 1; i <= len; i ++ ){
cnt[i][s[i] - 'a'] ++;
for(int j = 0; j <= 25; j ++ ){
cnt[i][j] += cnt[i - 1][j];
}
}
int m;
cin >> m;
while(m -- ){
int a,b,c,d;
cin >> a >> b >> c >> d;
bool f = 0;
for(int j = 0; j <= 25; j ++ ){
if(cnt[b][j] - cnt[a - 1][j] != cnt[d][j] - cnt[c - 1][j]){
f = 1;
break;
}
}
if(!f)cout << "DA" << '\n';
else cout << "NE" << '\n';
}
}