#2572. 「ZJOI2017」字符串

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Ycrpro

题目描述

猪小侠最近学习了字符串相关理论,现在他遇到了这样一个题:

维护一个动态字符串 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 ,分别表示两种操作。

输出格式

对于所有的查询操作按顺序输出答案。

样例

样例输入

5 5
3 2 1 4 3
2 1 5
1 2 4 2
2 1 5
1 2 5 1
2 1 5

样例输出

3
5
1

数据范围与提示

测试点编号 n m 其他约定
1 ≤ 300
2 ≤ 2 × 10^4 ≤10^4
3
4 ≤ 2 × 10^5 3×10^4 只有第二类操作
5
6 数据随机生成
7
8
9
10

对于 100\% 的数据, 1 ≤ l ≤ r ≤ n |d| ≤ 10^3 |s_i| ≤ 10^8

注意, 6 7 两个测试数据在随机生成时, s_i [0, 1] 中随机, d ±1 中随机。操作种类和操作区间都是等概率随机的。