[ZJOI2017] 字符串
题目背景
猪小侠最近学习了字符串相关理论,现在他遇到了这样一个题:
题目描述
维护一个动态字符串 $s_{1..n}$,字符串的字符集是所有 $|x| \leq 10 ^ 9$ 的整数。要求支持两个操作:
1. 输入 $l, r, d$,对于所有 $l \leq i \leq r$,将 $s_i$ 修改为 $s_i + d$,注意 $d$ 可能是负数。
2. 输入 $l, r$,输出子串 $s_{l..r}$ 的字ި序最小的后缀的起点位置。即,如果最小后缀是 $s_{p..r}$($l\leq p\leq 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
说明
| 测试点编号 | $n$ | $m$ | 其他约定 |
| ------ | ------ | ------ | ------ |
| $1$ | $\leq 300$ | $\leq 300$ | 无 |
| $2$ | $\leq 2 \times 10^4$ | $\leq 2 \times 10^4$ | 无 |
| $3$ | $\leq 2 \times 10^4$ | $\leq 2 \times 10^5$ | 无 |
| $4$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |只有第二类操作 |
| $5$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |只有第二类操作 |
| $6$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |数据随机生成 |
| $7$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |数据随机生成 |
| $8$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |无 |
| $9$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |无 |
| $10$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ |无 |
对于 $100\%$ 的数据,$1\leq l\leq r\leq n$,$|d|\leq 10 ^ 3$,$|s_i|\leq 10 ^ 8$。
注意,$6$ 和 $7$ 两个测试数据在随机生成时,$s_i$ 在 $\{0, 1\}$ 中随机,$d$ 在 $\{-1, 1\}$ 中随机。操作种类和操作区间都是等概率随机的。