[AdditionalFile2156.zip](file://AdditionalFile2156.zip?type=additional_file)

P3514 [POI 2011] LIZ-Lollipop

题目描述

给一个只有 $1$ 和 $2$ 的序列，每次询问有没有一个子串的和为 $x$。

输入格式

第一行两个整数 $n, m$（$1 \le n, m \le 10 ^ 6$）。

第二行一个长为 $n$ 的只含 $\texttt T$ 和 $\texttt W$ 的字符串，$\texttt T$ 代表 $2$，$\texttt W$ 代表 $1$。

接下来 $m$ 行，每行一个整数 $x$（$1 \le x \le 2\times 10 ^ 6$）表示一次询问。

输出格式

$m$ 行，如果有解则输出两个整数 $l, r$ 表示区间 $[l, r]$ 的和是 $x$，如果无解则输出字符串 NIE。

输入输出样例 #1

输入 #1

5 3
TWTWT
5
1
7

输出 #1

1 3
2 2
NIE

#2156. 「POI2011 R1」棒棒糖 Lollipop

标签: 传统 | 时间限制: 600 ms | 内存限制: 256 MiB |

题目描述

译自 POI 2011 Round 1. B「Lollipop」

Byteasar 在比特镇开了一家糖果店，草莓香草味的棒棒糖是当地孩子们的最爱。这些棒棒糖都是由长度相同的香草味或者草莓味的片段组成的。一整根棒棒糖的价格是每一段棒棒糖的价格之和，每一段香草味的棒棒糖价格为一元，草莓味的棒棒糖价格为两元。

图1：举个例子，这是一根由五段组成的棒棒糖，草莓味和香草味的棒棒糖交替排列，这根棒棒糖的价格为 $8$ 元。

现在，Byteasar 只剩下最后一根棒棒糖了。这根棒棒糖太长了，因此 Byteasar 认为绝对没有人会买下这一整根。所以，他想要把这一整根在接缝处掰成几段，每一段单独出售。

Byteasar 的人生经验告诉他，他的顾客希望把自己的钱花在单独的一根棒棒糖上，于是他想知道这一根棒棒糖有没有连续的一段的价格是 $k$。但这个问题对他来说太难了，他希望你能帮帮他。

输入格式

输入的第一行包含两个整数 $n, m$，分别表示最后仅存的这根棒棒糖的长度和要考虑的价格的数量（询问的数量）。棒棒糖的每一段从 $1$ 到 $n$ 编号。
第二行包含一个由W和T组成的字符串，描述了最后仅存的这根棒棒糖，其中第 $i$ 个字母描述第 $i$ 段的口味，T表示草莓片段（价格为 2 元），W表示香草片段（价格为 1 元）。
接下来的 $m$ 行每行包含一个整数 $k_i$，表示第 $i$ 个要考虑的连续片段的价格。

输出格式

你应当输出 $m$ 行，第 $i$ 行表示第 $i$ 个询问的结果。如果在这根棒棒糖中没有连续的一段的价格为 $k_i$，应输出NIE（波兰语中的No），否则应输出两个整数 $l$ 和 $r$ ，表示最后仅存的这根棒棒糖从 $l$ 到 $r$ 的片段价格为 $k_i$。若有多个可能的答案，输出一个即可，评测系统会使用 Special Judge 判断你的输出是否正确。

样例

输入

5 3
TWTWT
5
1
7

输出

1 3
2 2
NIE

这个例子与图1相同，从 $1$ 到 $3$ 的片段组成了TWT的棒棒糖，价格为 $5$。第 $2$ 段棒棒糖是香草味的，价格为 $1$。并没有办法得到一个价值为 $7$ 的棒棒糖。

数据范围与提示

对于 $100\%$ 的数据，$1 \le n, m \le 1000000$, $1 \le k \le 2000000$

Task author: Jakub Pachocki.
翻译和 SPJ: ceba