Comet OJ

C0597 [ZJOI2017]字符串

内存限制：512 MB 时间限制：3000 ms

题目描述

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

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

输出

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

样例

样例输入 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

提示

【数据范围与提示】

image.png

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

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