#P4877. [Zjoi2017]字符串

    ID: 3989 传统题 3000ms 512MiB 尝试: 77 已通过: 20 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS动态规划有限候选集缩减数据结构普通线段树排序与序列处理单调栈字符串哈希+二分求 LCP子串哈希双哈希根号分块整块懒标记CF3000

[Zjoi2017]字符串

[ZJOI2017] 字符串

题目背景

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

题目描述

维护一个动态字符串 s1..ns_{1..n},字符串的字符集是所有 ∣x∣≤109|x| \leq 10 ^ 9 的整数。要求支持两个操作:

  1. 输入 l,r,dl, r, d,对于所有 l≤i≤rl \leq i \leq r,将 sis_i 修改为 si+ds_i + d,注意 dd 可能是负数。
  2. 输入 l,rl, r,输出子串 sl..rs_{l..r} 的字典序最小的后缀的起点位置。即,如果最小后缀是 sp..rs_{p..r}(l≤p≤rl\leq p\leq r),请输出 pp。

输入格式

第一行两个非负整数 n,qn, q。

接下来一行包含 nn 个整数,表示初始时的字符串。

接下来 qq 行,每行为 1 l r d1\ l\ r\ d 或 2 l r2\ l\ r,分别表示两种操作。

输出格式

按询问顺序输出答案,每个询问一行一个整数。字典序比较按字符的整数值进行,若一个后缀是另一个后缀的真前缀,则较短的后缀更小。

样例 #1

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

提示

测试点编号 nn qq 其他约定
11 ≤300\leq 300 无
22 ≤2×104\leq 2 \times 10^4 ≤104\leq 10^4
33
44 ≤2×105\leq 2 \times 10^5 ≤3×104\leq 3 \times 10^4 只有第二类操作
55
66 数据随机生成
77
88 无
99
1010

对于 100%100\% 的数据,1≤l≤r≤n1\leq l\leq r\leq n,∣d∣≤103|d|\leq 10 ^ 3,∣si∣≤108|s_i|\leq 10^8(初始值)。

注意,66 和 77 两个测试数据在随机生成时,sis_i 在 {0,1}\{0, 1\} 中随机,dd 在 {−1,1}\{-1, 1\} 中随机。操作种类和操作区间都是等概率随机的。