文件名： fusion 题目类型： 传统题 时间限制： 3 秒 内存限制： 256 MB 编译优化： 无
题目描述
知名科学家小 A 在 2118 年在计算机上实现了模拟聚变的过程。
我们将她研究的过程简化。
核子共有 26 种，可以用 a 到 z 共 26 个字母表示。
核子聚变的过程可以用一个字符串描述。
按照顺序从左到右的顺序，假如有两个相同核子相邻，两个核子就会相互吸引发生聚变生成一个序号 +1 的核子，特殊的，两个 z 核子相邻会湮灭没有新的核子生成。
每当两个核子聚变时，就需要重新从左到右重复找到两个相邻的相同核子直到不存在为止。
比如 zyzzy->zyy->zz->
小 A 为了做出足够有效的实验，每次会从一个字符串中选定一个子串操作。
她想要知道每次实验这个子串中的核子能否最终全部湮灭。
输入格式
第一行一个只有小写字母的字符串。
第二行一个数 \(n\) 表示询问次数
接下来 \(n\) 行每行两个正整数 \(l_{i},r_{i}\) 表示询问区间
输出格式
对每次询问输出一行 Yes 或 No 表示答案
样例输入
yzyyyzyzyyyz 8 1 6 7 12 1 12 6 11 1 1 1 3 4 9 3 8
样例输出
Yes Yes Yes Yes No No No No
数据规模与约定
L 表示字符串长度 对于 30% 的数据满足 L<=100 对于 60% 的数据满足 L<=3000,n<=3000 另存在 20% 数据满足字符串中只存在 y,z 对于 100% 的数据, L<=500000,n<=1000000
题解
开始没看到“从左往右”，还以为是线段树维护分治……
\(nL\) 大力 60。
我们发现对于一段合法串，我们可以把它分成多个（或一个）连续的合法字串。
比如：
zyyzyyyyz
我们可以分成：
zyy | zyy | yyz
这三段都是合法的，所以原串也是合法的。
又比如说：
zyyyyzyz
我们把它分成：
zyy | yyz | yz
显然，yz 是不合法的，所以原串是不合法的。
于是我们检验时，我们可以让指针跳着走：
zyy | yyz | yz
^
zyy | yyz | yz
---->^
zyy | yzz | yz
---->^
zyy | yzz | yz
---->^
发现指针跳到外面去了，所以说是不合法的。
不难想到用一个 nxt 数组表示以第 i 个开始的最短合法串末尾的下一个位置（感觉很像 kmp）。
那么怎么求 nxt 呢？
我们需要引入一个 to 数组。
to[i][j] 表示从第 i 位开始最短能拼成 j 字符的位置的下一个位置（\(j = 0\sim 26\)，\(0\) 表示 \(a\)，\(26\) 表示没有）。
不难发现 to[i][j] = to[to[i][j-1]][j-1]，nxt[i] = to[i][26]。
当然，开始时 to 与 nxt 都指向结尾的后面。
然而我们发现这样做会被 hack：
xzzxyz
这是因为对于第一个 z 来讲它只更新了 \(25\sim 26\) 的情况，所以第一个第一个 x 的 nxt 会指向末尾。
所以我们需要排除中间这段 zz 的干扰。
于是我们又想到转移方程：to[i][j] = to[nxt[i]][j]。
这样就大功告成了。
然而这样做很容易被卡掉，比如说全是 z 的情况，往后跳的速度会很慢。
所以我们选择倍增。
下面是代码：
#include <cstdio>
#include <cstring>
const int maxn = 500005;
char aa[maxn];
int nxt[maxn][21];
int to[maxn][26];
inline void pre()
{
int len = strlen(aa);
for(int i = 0; i < len; ++i)
aa[i] -= 'a';
for(int i = 0; i < len + 3; ++i)
{
for(int j = 0; j <= 20; ++j)
nxt[i][j] = len + 1;
for(int j = 0; j <= 26; ++j)
to[i][j] = len + 1;
}
for(int i = len - 1; i >= 0; --i)
{
to[i][(int)aa[i]] = i + 1;
for(int j = aa[i] + 1; j <= 26; ++j)
to[i][j] = to[to[i][j-1]][j-1];
nxt[i][0] = to[i][26];
for(int j = 1; j <= 20; ++j)
nxt[i][j] = nxt[nxt[i][j-1]][j-1];
for(int j = 0; j < 26; ++j)
if(to[i][j] == len + 1)
to[i][j] = to[nxt[i][0]][j];
}
}
inline bool pan(int l, int r)
{
l--;
r--; // 从0开始……（感觉自己好作死）
for(int i = 20; i >= 0; --i)
{
if(nxt[l][i] <= r + 1)
l = nxt[l][i];
if(l == r + 1)
return true;
}
return false;
}
int main()
{
freopen("fusion.in", "r", stdin);
freopen("fusion.out", "w", stdout);
gets(aa);
pre();
int n;
scanf("%d", &n);
while(n--)
{
int l, r;
scanf("%d%d", &l, &r);
puts(pan(l, r) ? "Yes" : "No");
}
fclose(stdin);
fclose(stdout);
return 0;
}