#P13958. [2024多校联盟省选模拟]漫絮散板

    ID: 13170 传统题 4000ms 512MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2500字符串后缀自动机数据结构贪心模拟

[2024多校联盟省选模拟]漫絮散板

题目描述

为了欢迎加入短笛声部的新成员小雅,副首席小铃决定创作一首乐曲。

乐谱可以看作一个长度为 nn 的字符串 SS(只由 a、b 组成)。随后她们制定了一份 qq 天的训练计划。
每天给定参数 l,rl,r,她们将针对乐曲的一段 [l,r][l,r] 进行练习,这次练习分为 r−l+1r-l+1 轮。

第 ii 轮(1≤i≤r−l+11\le i\le r-l+1):

  • 小铃吹奏区间 [l, l+i−1][l,\ l+i-1];
  • 小雅吹奏区间 [l+i−1, r][l+i-1,\ r]。

定义这一轮的和谐度为:两段吹奏内容的最长公共子串(连续公共部分)的长度。
也就是 S[l,l+i−1]S[l,l+i-1] 与 S[l+i−1,r]S[l+i-1,r] 的最长公共子串长度,记为 fif_i。

为了减少输出量,你只需要输出:

⨁i=1r−l+1(i+fi),\bigoplus_{i=1}^{r-l+1} (i+f_i),

其中 ⊕\oplus 表示按位异或。

输入格式

第一行三个整数 id, n, q:测试点编号(样例为 0)、乐谱长度与计划天数。
第二行一个长度为 nn 的字符串 SS。
之后 qq 行,每行输入两个整数 l,rl,r,表示当天的练习参数。

输出格式

共输出 qq 行,按顺序对每一天输出一个整数表示答案。

0 8 2
ababbaba
2 4
1 8
5
6

样例解释

第一次练习:[l,r]=[2,4][l,r]=[2,4],乐段为 bab。
每一轮演奏区间依次为:

  • {[2,2],[2,4]}\{[2,2],[2,4]\},
  • {[2,3],[3,4]}\{[2,3],[3,4]\},
  • {[2,4],[4,4]}\{[2,4],[4,4]\},

和谐度依次为 1,1,11,1,1。

第二次练习:[1,8][1,8],乐段为 ababbaba。
每一轮的和谐度依次为 1,2,3,3,3,3,2,11,2,3,3,3,3,2,1。

数据范围与提示

测试点编号 nn qq 特殊性质
1 ≤30\le 30 ≤3\le 3 无
2–3 ≤150\le 150 ≤5\le 5
4–6 ≤1500\le 1500 ≤15\le 15
7 ≤104\le 10^4 ≤20\le 20 A
8–9 ≤5000\le 5000 B
10–12 ≤2×104\le 2\times 10^4 ≤15\le 15 无
13–15 ≤5×104\le 5\times 10^4 ≤10\le 10 C
16–17 ≤105\le 10^5 ≤20\le 20 无
18–20 ≤30\le 30
  • 特殊性质 A:字符串 SS 只由字符 a 组成。
  • 特殊性质 B:字符串 SS 随机生成。
  • 特殊性质 C:l=1l=1。

对于 100% 的数据:
1≤n≤105, 1≤q≤30, 1≤l≤r≤n1\le n\le 10^5,\ 1\le q\le 30,\ 1\le l\le r\le n,字符串 SS 只由 a、b 两种字符组成。