codeforces 1291D Irreducible Anagrams 思维

https://vjudge.net/problem/CodeForces-1291D

题目大意：对于字符串$t$t和$s$s，在两者是相同字母异序词(就是每个字母的出现次数都一样)的基础上，如果说$t$t是$s$s的一个可约序列，那么存在一个$k>=2$k>=2使得：
简单来说就是把$t$t和$s$s按顺序划分为$k$k个字串，$t_i$ti​和$s_i$si​也是相同字母异序词，如果不存在这样的$k$k，那么就说$t$t和$s$s不可约。题目给定了一个字符串$s$s，然后有$n$n个询问$(l,r)$(l,r)，表示字符串$s$s的子串$s[l……r]$s[l……r]，如果能找到一个字符串$t$t使得$t$t和$s$s不可约，输出$Yes$Yes，否则输出$No$No。

思路：这题其实就题目很绕，读懂了还是很好做的，尤其是不可约的情况很容易构造出来。我们考虑一个长度为$len$len的字符串$s$s，如果$s[1]!=s[len]$s[1]!=s[len]，那么我们可以构造出一个字符串$t$t使得$t[1]=s[len],t[len]=s[1],t[2……len-1]=s[2 ……len-1]$t[1]=s[len],t[len]=s[1],t[2……len−1]=s[2……len−1]，显然$t$t和$s$s就不可约，因为对于任意$k$k，$t_1、s_1$t1​、s1​和$t_k、s_k$tk​、sk​都不是相同字母异序词。考虑$s[1]=s[len]$s[1]=s[len]时，如果在$s[2……len]$s[2……len]中存在两个和$s[1]$s[1]不同的字母，我们就可以用第一种情况中的方法构造出一个字符串$t$t使得$t$t和$s$s不可约。那么目前仅存的问题就是如何快速的求出$[l,r]$[l,r]内某个元素是否出现过，线段树？$No$No，前缀和就$ok$ok了。

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;

const int maxn=2e5+5;

int n;
int cnt[26][maxn];
char s[maxn];

int main()
{
    scanf("%s",s+1);
    scanf("%d",&n);
    int l,r,len=strlen(s+1);
    for(int i=1;i<=len;i++)
    {
        for(int j=0;j<26;j++)
            cnt[j][i]=cnt[j][i-1];
        cnt[s[i]-'a'][i]++;
    }
    while(n--)
    {
        scanf("%d%d",&l,&r);
        if(l==r)
            printf("Yes\n");
        else
        {
            if(s[l]!=s[r])
                printf("Yes\n");
            else
            {
                int ct=0;
                for(int i=0;i<26;i++)
                    if('a'+i!=s[l]&&cnt[i][r]-cnt[i][l-1])
                        ++ct;
                if(ct>=2)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
        }
    }
    return 0;
}