#P6926. 审判
审判
题目描述
给定一个长度为 的字符串 ,只包含 a、b、c。下标从 开始。
每次询问给出 。找出原串中与 相同的所有子串,求这些出现区间的并集包含多少个位置。同一位置即使被多个区间覆盖,也只计一次。
询问强制在线,实际端点要用上一次的答案解码。
输入格式
第一行三个非负整数 ,分别表示字符串长度、询问数和解码参数。
第二行一个长度为 的字符串 。
接下来 行,每行两个非负整数 ,表示编码后的端点。令 为上一次询问的答案,第一次询问时为 。此次询问的实际端点为
$$l_i=tl_i\mathbin{\operatorname{xor}}(lastans\cdot op),\qquad r_i=tr_i\mathbin{\operatorname{xor}}(lastans\cdot op).$$其中 表示按位异或,解码后满足 。
输出格式
输出 行,每行一个正整数,表示对应询问的结果。
样例
5 4 0
ababa
1 1
2 2
1 3
3 5
3
2
5
5
原题另外下发 ex_judgement1 和 ex_judgement2,分别满足子任务 2、4 的范围。
数据范围
,。编码前的实际端点在 内。编码字段是两个不超过 的整数做异或后的结果,可能为 或大于 。原题采用捆绑评测,同一子任务内所有测试点通过才可获得该子任务的分数。
| 子任务 | 上界 | 上界 | 分值 | |
|---|---|---|---|---|
| 1 | 0 | 6 | ||
| 2 | 12 | |||
| 3 | 18 | |||
| 4 | 20 | |||
| 5 | 1 | 44 |
by Mona