[ZJOI2017] 字符串
题目背景
猪小侠最近学习了字符串相关理论,现在他遇到了这样一个题:
题目描述
维护一个动态字符串 s1..n,字符串的字符集是所有 ∣x∣≤109 的整数。要求支持两个操作:
- 输入 l,r,d,对于所有 l≤i≤r,将 si 修改为 si+d,注意 d 可能是负数。
- 输入 l,r,输出子串 sl..r 的字典序最小的后缀的起点位置。即,如果最小后缀是 sp..r(l≤p≤r),请输出 p。
输入格式
第一行两个非负整数 n,q。
接下来一行包含 n 个整数,表示初始时的字符串。
接下来 q 行,每行为 1 l r d 或 2 l r,分别表示两种操作。
输出格式
按询问顺序输出答案,每个询问一行一个整数。字典序比较按字符的整数值进行,若一个后缀是另一个后缀的真前缀,则较短的后缀更小。
样例 #1
样例输入 #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 |
q |
其他约定 |
| 1 |
≤300 |
无 |
| 2 |
≤2×104 |
≤104 |
| 3 |
| 4 |
≤2×105 |
≤3×104 |
只有第二类操作 |
| 5 |
| 6 |
数据随机生成 |
| 7 |
| 8 |
无 |
| 9 |
| 10 |
对于 100% 的数据,1≤l≤r≤n,∣d∣≤103,∣si∣≤108(初始值)。
注意,6 和 7 两个测试数据在随机生成时,si 在 {0,1} 中随机,d 在 {−1,1} 中随机。操作种类和操作区间都是等概率随机的。