#PQJ44x5218. QOJ 44_5218
QOJ 44_5218
3 字符串 3.1 题目᧿䘠 猪小侠最近学习了字符串相关理论,现在他遇到了这样一个题: 维护一个动态字符串s[1..n],字符串的字符集是所有|x| ≤109 的整数。要求支持两个操作:
- 输入l, r, d,对于所有l ≤i ≤r,将s[i] 修改为s[i] + d,注意d 可能是负数。
- 输入l, r,输出子串s[l..r] 的字ި 序最小的后缀的起点位置。即,如果最小后缀是s[p..r], (l ≤ p ≤r),请输出p。 3.2 输入格式 第一行两个非负整数n, q。 接下来一行包含n 个正整数,表示初始时的字符串。 接下来q 行,每行为1 l r d 或2 l r,分别表示两种操作。 3.3 输出格式 对于所有的查询操作按顺序输出答案。 3.4 样例输入 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 样例输出 3 5 1 6
3.6 数据规⁑与约定 测试点编号 n m 其他约定 1 ≤300 ≤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 中随机。操作种类 和操作区间都是等概率随机的。 7