#P6926. 审判

    ID: 6757 传统题 1500ms 888MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2800省选/NOI-后缀自动机endpos 等价类树上倍增小并大合并集合有序集合可持久化线段树路径复制增量维护

审判

题目描述

给定一个长度为 nn 的字符串 ss,只包含 a、b、c。下标从 11 开始。

每次询问给出 li≤ril_i\le r_i。找出原串中与 s[li…ri]s[l_i\ldots r_i] 相同的所有子串,求这些出现区间的并集包含多少个位置。同一位置即使被多个区间覆盖,也只计一次。

询问强制在线,实际端点要用上一次的答案解码。

输入格式

第一行三个非负整数 n,Q,opn,Q,op,分别表示字符串长度、询问数和解码参数。

第二行一个长度为 nn 的字符串 ss。

接下来 QQ 行,每行两个非负整数 tli,tritl_i,tr_i,表示编码后的端点。令 lastanslastans 为上一次询问的答案,第一次询问时为 00。此次询问的实际端点为

$$l_i=tl_i\mathbin{\operatorname{xor}}(lastans\cdot op),\qquad r_i=tr_i\mathbin{\operatorname{xor}}(lastans\cdot op).$$

其中 xor⁡\operatorname{xor} 表示按位异或,解码后满足 1≤li≤ri≤n1\le l_i\le r_i\le n。

输出格式

输出 QQ 行,每行一个正整数,表示对应询问的结果。

样例

5 4 0
ababa
1 1
2 2
1 3
3 5
3
2
5
5

原题另外下发 ex_judgement1 和 ex_judgement2,分别满足子任务 2、4 的范围。

数据范围

1≤n≤1051\le n\le10^5,1≤Q≤1061\le Q\le10^6。编码前的实际端点在 [1,n][1,n] 内。编码字段是两个不超过 nn 的整数做异或后的结果,可能为 00 或大于 nn。原题采用捆绑评测,同一子任务内所有测试点通过才可获得该子任务的分数。

子任务 nn 上界 QQ 上界 opop 分值
1 3×1023\times10^2 10310^3 0 6
2 10310^3 12
3 10610^6 18
4 10510^5 20
5 1 44

原 PDF 题面

by Mona