题解:
当子串长为 1或者串中字符种类为 1,显然构造不出。
排除以上情况后,显然无论怎么分割子串,首尾字符是不可能划分到一起的。
思考极端情况时,划分为 s[l]和 s[l+1∼r]或者 s[l∼r−1]和 s[r],
故问题转换成了如何使得 t的首尾字符与 s的首尾字符完全不同的构造情况。
首先,当 s串中字符种类多于 2个时,三个字符只要挑 2个放到首尾即可。
其次,当 s串中种类为 2时:
-
如果 s串中 s[l]=s[r],我们只需要构造 t使得 t[l]=s[r],t[r]=s[l]即可。
-
如果 s串中 s[l]==s[r]。那么假设存在一个 t符合题目要求使得 s为irreducible anagram。
那么先初始化 t=s,要构造一个符合要求的 t,还是从尽可能地构造 s[l]!=t[l]且 s[r]!=t[r]入手。初始状态下我们只要分隔开首尾,怎么构造都可以。
第一种情况:
我们从 l向右寻找一个 i,当 s[i]==t[i]&&t[l]!=t[i],swap(t[l],t[i]),那么必须放在一起的区域就变成了 t[l∼i]。
继续从 r向左寻找一个 j,当 s[j]==t[j]&&t[r]!=t[j],swap(t[r],t[j]),那么必须放在一起的区域又多了 t[j∼r]。
如果 i和 j都找到了,那么此时 t[l]!=s[l]&&t[r]!=s[r]。就是至少划分成 t[l∼i],t[j∼r],
s[i+1∼j−1]无需划分。ps:如果只有一个找到,说明两种字符中,一种字符只有一个,
那么无论怎么交换都不可能符合要求。第二种情况:
我们从 r向左寻找一个 j,当 s[j]==t[j]&&t[l]!=t[j],swap(t[l],t[j]),那么必须放在一起的区域就变成 了 t[l∼j]。
继续从 l向右寻找一个 i,当 s[i]==t[j]&&t[r]!=t[i],swap(t[r],t[i]),那么必须放在一起的区域又多了 t[i∼r]。
毫无疑问这两者会有相交的部分。但其实这两种寻找方式都是调换了两个相同的字符到 l,r,两个相同的字符到 i.j,实际上和上面那种交换是一样的。
因此这种情况是构造不出来的。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 2e5 + 10;
char s[N];
int ch[26], q;
int pre[N][26];
int main()
{
scanf("%s%d", s + 1, &q);
for(int i = 1; s[i]; i++) ch[s[i] - 'a']++;
for(int i = 1; s[i]; i++) {
for(int j = 0; j < 26; j++)
pre[i][j] = pre[i - 1][j];
pre[i][s[i] - 'a']++;
}
while(q--) {
int l, r;
scanf("%d%d", &l, &r);
if(l == r) puts("Yes");
else {
int t[26] = {0}, cnt = 0;
for(int j = 0; j < 26; j++) t[j] = pre[r][j] - pre[l - 1][j];
for(int j = 0; j < 26; j++) if(t[j]) cnt++;
if(cnt > 2) puts("Yes");
else if(s[l] != s[r]) puts("Yes");
else puts("No");
}
}
return 0;
}