题目描述
有字符串 \(S\)，按照顺序多次进行以下 \(N\) 种操作：
- 操作 \(i\)：$ S $ 的第 $ l_i $ 个字母到第 $ r_i $ 个字母分别变为它们的下一个字母。(
a变成b，b变成c・・・)；假设z的下一个字母是a。
判断是否可以把 \(S\) 变成回文。
输入格式
输入以以下形式：
\(S\)
$ N $
$ L_1 $ $ R_1 $
$ L_2 $ $ R_2 $
$\ldots $
$ L_N $ $ R_N $
输出格式
把 \(S\) 变成回文，能的话就输出 YES，不能的话就输出 NO。
样例输入
bixzja
2
2 3
3 6
样例输出
YES
提示
- $ 1\ \leq\ |S|\ \leq\ 10^5 $
- $ S $ 只由小写字母组成。
- $ 1\ \leq\ N\ \leq\ 10^5 $
- $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ |S| $
当我们操作区间 \([l,r]\) 时，相当于将这个区间每个字符 \(+1\) 并且模 \(26\)，很容易想到差分。
很明显，如果想要让最后结果变为一个回文串，那就必须让 \(S[i]=S[len-i+1]\)（\(len\) 为字符串 \(S\) 的长度）。
为了让这个和差分数组扯上关系，我们让 \(S[0]=S[len+1]='a'\)，差分数组的长度也会变为 \(len+1\)。
由于 \(S[0]=S[len+1]\)，那如果要让 \(S[1]=S[len]\)，就需要 \((d[1]+d[len+1])\bmod 26\equiv0\)。
所以说，我们只需要满足 \((d[i]+d[len-i+2])\bmod 26\equiv0(i\in [1,\lfloor \frac{len+1}{2} \rfloor])\)，就说明 \(S[i]=S[len-i+1]\)（前提：\(S[i-1]=S[len-i+2]\)）。
对于差分，我们很容易发现 \(d[l]+d[r+1]\) 是一个定值，但是 \(d[l]\) 和 \(d[r+1]\) 可以随意变换。
这时问题便转化成了：合理操作每一个 \(d[l_i]\) 和 \(d[r_i+1]\)，使得 \(d[l_i]+d[r_i+1]\) 始终不变且让 \((d[i]+d[len-i+2])\bmod 26\equiv0\)。
最难想到的来了，我们可以把 \(d[i]+d[len-i+2]\) 抽象成一个点，其点权为 \(d[i]+d[len-i+2]=S[i]-S[len-i+1]\)（自己推）。
然后将 \(d[l]\) 所对应的点与 \(d[r+1]\) 所对应的点连边，假设连接了点 \(A\) 与 点 \(B\)，那么它们各自的点权就相当于它们所需要的值。
例如，如果 \(A\) 的点权大于 \(B\) 的点权，那么减小 \(d[l]\) 增大 \(d[r+1]\)，反之亦然。
这样每一个 \(l\) 和 \(r\) 都连接了一组连通块，如果每个连通块的和模 \(26\) 都为 \(0\) 的话，那么可以，否则不行。
如果有一个连通块和模 \(26\) 不为 \(0\)。
这说明至少有一组连通块无法保证互相平衡，从而构不成回文串。
#include<bits/stdc++.h>
using namespace std;
int n,len;
const int N=1e5+5;
char s[N];
int d[N];
struct DSU{
int fa[N];
void init(){
for(int i=1;i<=len+1;i++) fa[i]=i,d[i]=s[i]-s[i-1];
return ;
}
int find(int x){
if(fa[x]==x) return x;
fa[x]=find(fa[x]);
return fa[x];
}
void merge(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy) return ;
d[fx]=d[fy]=d[fx]+d[fy];
fa[fx]=fy;
}
}check;
int main()
{
scanf("%s",s+1);len=strlen(s+1);
check.init();
for(int i=1;i<len-i+2;i++) check.merge(i,len-i+2);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int l,r;scanf("%d%d",&l,&r);
if(l>r) swap(l,r);
check.merge(l,r+1);
}
for(int i=1;i<=len+1;i++){
if(check.find(i)!=i) continue;
if(d[i]%26==0) continue;
printf("NO\n");
return 0;
}
printf("YES\n");
return 0;
}