A5743 | 「ZJOI2017」字符串
时间限制3s
内存限制512MB
通过 / 提交0/0
题目描述
猪小侠最近学习了字符串相关理论，现在他遇到了这样一个题：
维护一个动态字符串 $s[1..n]$ ，字符串的字符集是所有 $|x| ≤ 10^9$ 的整数。要求支持两个操作：
- 输入 $l, r, d$ ，对于所有 $l ≤ i ≤ r$ ，将 $s[i]$ 修改为 $s[i] + d$ ，注意 $d$ 可能是负数。
- 输入 $l, r$ ，输出子串 $s[l..r]$ 的字ި序最小的后缀的起点位置。即，如果最小后缀是 $s[p..r],(l ≤p ≤ r)$ ，请输出 $p$ 。
维护一个动态字符串 $s[1..n]$ ，字符串的字符集是所有 $|x| ≤ 10^9$ 的整数。要求支持两个操作：
- 输入 $l, r, d$ ，对于所有 $l ≤ i ≤ r$ ，将 $s[i]$ 修改为 $s[i] + d$ ，注意 $d$ 可能是负数。
- 输入 $l, r$ ，输出子串 $s[l..r]$ 的字ި序最小的后缀的起点位置。即，如果最小后缀是 $s[p..r],(l ≤p ≤ r)$ ，请输出 $p$ 。
输入格式
第一行两个非负整数 $n, q$ 。
接下来一行包含 $n$ 个正整数，表示初始时的字符串。
接下来 $q$ 行，每行为 $1$ $l$ $r$ $d$ 或 $2$ $l$ $r$ ，分别表示两种操作。
接下来一行包含 $n$ 个正整数，表示初始时的字符串。
接下来 $q$ 行，每行为 $1$ $l$ $r$ $d$ 或 $2$ $l$ $r$ ，分别表示两种操作。
输出格式
对于所有的查询操作按顺序输出答案。
输入输出样例
输入 #1
5 5 3 2 1 4 3 2 1 5 1 2 4 2 2 1 5 1 2 5 1 2 1 5
输出 #1
3 5 1
|测试点编号|n|m|其他约定|
|:-:|:-:|:-:|:-:|
|1|$≤ 300$|$≤ 300$|无|
|2|$≤ 2 × 10^4$|$≤10^4 $|无|
|3|$≤ 2 × 10^4$|$≤10^4 $|无|
|4|$≤ 2 × 10^5$|$3×10^4$|只有第二类操作|
|5|$≤ 2 × 10^5$|$3×10^4$|只有第二类操作|
|6|$≤ 2 × 10^5$|$3×10^4$|数据随机生成|
|7|$≤ 2 × 10^5$|$3×10^4$|数据随机生成|
|8|$≤ 2 × 10^5$|$3×10^4$|无|
|9|$≤ 2 × 10^5$|$3×10^4$|无|
|10|$≤ 2 × 10^5$|$3×10^4$|无|
对于 $100\%$ 的数据， $1 ≤ l ≤ r ≤ n$ ， $|d| ≤ 10^3$ ， $|s_i| ≤ 10^8$ 。
注意，$6$ 和 $7$ 两个测试数据在随机生成时， $s_i$ 在 $[0, 1]$ 中随机， $d$ 在 $±1$ 中随机。操作种类和操作区间都是等概率随机的。
|:-:|:-:|:-:|:-:|
|1|$≤ 300$|$≤ 300$|无|
|2|$≤ 2 × 10^4$|$≤10^4 $|无|
|3|$≤ 2 × 10^4$|$≤10^4 $|无|
|4|$≤ 2 × 10^5$|$3×10^4$|只有第二类操作|
|5|$≤ 2 × 10^5$|$3×10^4$|只有第二类操作|
|6|$≤ 2 × 10^5$|$3×10^4$|数据随机生成|
|7|$≤ 2 × 10^5$|$3×10^4$|数据随机生成|
|8|$≤ 2 × 10^5$|$3×10^4$|无|
|9|$≤ 2 × 10^5$|$3×10^4$|无|
|10|$≤ 2 × 10^5$|$3×10^4$|无|
对于 $100\%$ 的数据， $1 ≤ l ≤ r ≤ n$ ， $|d| ≤ 10^3$ ， $|s_i| ≤ 10^8$ 。
注意，$6$ 和 $7$ 两个测试数据在随机生成时， $s_i$ 在 $[0, 1]$ 中随机， $d$ 在 $±1$ 中随机。操作种类和操作区间都是等概率随机的。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？