# 20180711 模拟赛 T3 -- 聚变

Author: Fanyi Pu

Published: 2018-09-08

Canonical: <https://pufanyi.com/blog/20180711-t3>

20180711 模拟赛 T3 -- 聚变

> **文件名：** 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 的情况，往后跳的速度会很慢。

所以我们选择倍增。

下面是代码：

```cpp
#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;
}
```