问题 28476 --字符串

28476: 字符串

时间限制: 5 Sec  内存限制: 512 MB
提交: 3  解决: 2
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][7570kb]

题目描述

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

维护一个动态字符串 s[1..n],字符串的字符集是所有 |x| ≤ 109 的整数。

要求支持两个操作: 

1) 输入 l, r, d,对于所有 l ≤ i ≤ r,将 s[i] 修改为 s[i] + d,注意 d 可能是负数。 

2) 输入 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

提示

来源

[提交][状态]