A6730 | 「NOI2023」字符串
来源NOI
时间限制1s
内存限制512MB
通过 / 提交0/0
题目描述
小 Y 是一名大学生，最近正在研究字符串方向的问题。
小 Y 了解到关于字符串的如下定义:
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s[l], s[l+1], \dots, s[r]$, 将其顺次拼接得到的新字符串。
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。
- 给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$，使得对于任意 $1 \leq j < i$，$a[j] = b[j]$，且 $a[i] < b[i]$。
在了解了上述定义后，小 Y 想到了这样的问题:
给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件:
- $1 \leq l \leq r$。
- $s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$。
小 Y 想求助你帮忙解决这一问题。
小 Y 了解到关于字符串的如下定义:
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其子串 $s[l: r]$（$1 \leq l \leq r \leq n$）为选择 $s[l], s[l+1], \dots, s[r]$, 将其顺次拼接得到的新字符串。
- 给定一个长度为 $n$ 的字符串 $s[1: n]$，我们定义其翻转后的结果 $R(s)$ 为将 $s[n], s[n-1], \dots, s[1]$ 顺次拼接，也就是将字符串反序拼接得到的字符串。
- 给定两个长度均为 $n$ 的字符串 $a[1: n], b[1: n]$，我们定义 $a$ 的字典序小于 $b$ 当且仅当存在 $1 \leq i \leq n$，使得对于任意 $1 \leq j < i$，$a[j] = b[j]$，且 $a[i] < b[i]$。
在了解了上述定义后，小 Y 想到了这样的问题:
给定一个长度为 $n$ 的字符串 $s[1: n]$。有 $q$ 次询问，每次询问给定两个参数 $i, r$。你需要求出有多少 $l$，满足如下条件:
- $1 \leq l \leq r$。
- $s[i: i+l-1]$ 字典序小于 $R(s[i+l: i+2l-1])$。
小 Y 想求助你帮忙解决这一问题。
输入格式
从文件
输入的第一行包含两个整数 $c, t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。
接下来依次输入每组测试数据，对于每组测试数据：
输入的第一行包含两个正整数 $n, q$，表示子符串长度和询问次数。
输入的第二行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。
输入的接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \leq n$。
string.in 中读入数据。输入的第一行包含两个整数 $c, t$，分别表示测试点编号和测试数据组数。$c=0$ 表示该测试点为样例。
接下来依次输入每组测试数据，对于每组测试数据：
输入的第一行包含两个正整数 $n, q$，表示子符串长度和询问次数。
输入的第二行包含一个长度为 $n$ 的仅包含小写字母的字符串 $s$。
输入的接下来 $q$ 行，每行包含两个正整数 $i, r$。表示一次询问，保证 $i+2r-1 \leq n$。
输出格式
输出到文件
对于每一组测试数据的每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。
string.out 中。对于每一组测试数据的每一次询问，输出一行一个整数，表示满足条件的 $l$ 的个数。
输入输出样例
输入 #1
0 2 9 3 abacababa 1 4 2 4 3 3 9 3 abaabaaba 1 4 2 4 3 3
输出 #1
4 0 3 2 0 2
对于所有测试数据保证：$1 \le t \le 5$，$1 \le n \le 10 ^ 5$，$1 \le q \le 10 ^ 5$，$1 \le i + 2r - 1 \le n $，字符串 $s$ 仅包含小写字母。
|测试点编号|$n \le$|$q \le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1$|$5$|$5$|A|
|$2$|$10$|$10$|A|
|$3$|$20$|$20$|A|
|$4$|$50$|$50$|A|
|$5$|$10^2$|$10^2$|A|
|$6$|$10^3$|$10^3$|无|
|$7$|$2,000$|$2,000$|无|
|$8$|$3,000$|$3,000$|无|
|$9$|$4,000$|$4,000$|无|
|$10$|$23,333$|$23,333$|A|
|$11$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|A|
|$12$|$75,000$|$75,000$|A|
|$13$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|A|
|$14$|$10 ^ 5$|$10 ^ 5$|A|
|$15$|$23,333$|$23,333$|B|
|$16$|$75,000$|$75,000$|B|
|$17$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|B|
|$18$|$10 ^ 5$|$10 ^ 5$|B|
|$19$|$23,333$|$23,333$|无|
|$20$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|无|
|$21$|$75,000$|$75,000$|无|
|$22$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|无|
|$23$|$95,000$|$95,000$|无|
|$24 \sim 25$|$10 ^ 5$|$10 ^ 5$|无|
特殊性质 A：保证字符串中仅包含字符 $\texttt{a}$ 和 $\texttt{b}$，且每个字符独立等概率地在 $\texttt{a}$ 和 $\texttt{b}$ 中选择。
特殊性质 B：保证字符串中的相邻字符互不相同。
|测试点编号|$n \le$|$q \le$|特殊性质|
|:-:|:-:|:-:|:-:|
|$1$|$5$|$5$|A|
|$2$|$10$|$10$|A|
|$3$|$20$|$20$|A|
|$4$|$50$|$50$|A|
|$5$|$10^2$|$10^2$|A|
|$6$|$10^3$|$10^3$|无|
|$7$|$2,000$|$2,000$|无|
|$8$|$3,000$|$3,000$|无|
|$9$|$4,000$|$4,000$|无|
|$10$|$23,333$|$23,333$|A|
|$11$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|A|
|$12$|$75,000$|$75,000$|A|
|$13$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|A|
|$14$|$10 ^ 5$|$10 ^ 5$|A|
|$15$|$23,333$|$23,333$|B|
|$16$|$75,000$|$75,000$|B|
|$17$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|B|
|$18$|$10 ^ 5$|$10 ^ 5$|B|
|$19$|$23,333$|$23,333$|无|
|$20$|$5 \times 10 ^ 4$|$5 \times 10 ^ 4$|无|
|$21$|$75,000$|$75,000$|无|
|$22$|$9 \times 10 ^ 4$|$9 \times 10 ^ 4$|无|
|$23$|$95,000$|$95,000$|无|
|$24 \sim 25$|$10 ^ 5$|$10 ^ 5$|无|
特殊性质 A：保证字符串中仅包含字符 $\texttt{a}$ 和 $\texttt{b}$，且每个字符独立等概率地在 $\texttt{a}$ 和 $\texttt{b}$ 中选择。
特殊性质 B：保证字符串中的相邻字符互不相同。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？