#P13840. [cf2017final]Combination Lock

    ID: 13041 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-一维差分普通并查集无向连通分量模意义不变量

[cf2017final]Combination Lock

题目描述

有字符串 SS,按照任意顺序进行任意次以下 NN 种操作:

  • 操作 ii:S S 的第 li l_i 个字母到第 ri r_i 个字母分别变为它们的下一个字母。(a 变成 b, b 变成 c・・・);假设 z 的下一个字母是 a。

判断是否可以把 SS 变成回文。

输入格式

输入以以下形式:

SS

N N

L1 L_1 R1 R_1

L2 L_2 R2 R_2

…\ldots

LN L_N RN R_N

输出格式

把 SS 变成回文,能的话就输出 YES,不能的话就输出 NO。

输入输出样例 #1

输入 #1

bixzja
2
2 3
3 6

输出 #1

YES

输入输出样例 #2

输入 #2

abc
1
2 2

输出 #2

NO

输入输出样例 #3

输入 #3

cassert
4
1 2
3 4
1 1
2 2

输出 #3

YES

说明/提示

  • 1 ≤ ∣S∣ ≤ 105 1\ \leq\ |S|\ \leq\ 10^5
  • S S 只由小写字母组成。
  • 1 ≤ N ≤ 105 1\ \leq\ N\ \leq\ 10^5
  • 1 ≤ Li ≤ Ri ≤ ∣S∣ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ |S|

样本解释  1\ 1:

例如,按顺序进行操作,就会变成 bixzja→bjyzja→bjzakb→bkaakb,也就是变成回文字符串了。