你需要维护一个动态字符串 $s \left[ 1 .. n \right]$，字符串的字符集是所有 $|x| \leq 10^9$ 的整数。要求支持两种操作：
输入 $l, r, d$，对于所有 $l \leq i \leq r$，将 $s_i$ 修改为 $s_i + d$，注意 $d$ 可能是负数。
输入 $l, r$，输出子串 $s \left[ l .. r \right]$ 的字典序最小的后缀的起点位置。即，如果最小后缀是 $s \left[ p .. r \right]$ ($l \leq p \leq r$)，请输出 $p$。
第一行包含两个非负整数 $n, q$ ($1 \leq n \leq 2 \times 10^5; 0 \leq q \leq 3 \times 10^4$)。
第二行包含 $n$ 个整数 $s_i$ ($-10^8 \leq s_i \leq 10^8$)，表示初始时的字符串。
接下来 $q$ 行，每行为 1 l r d 或 2 l r，分别表示两种操作。
对于每一个 $2$ 操作，输出一行一个整数，表示字典序最小的后缀的起点位置。
对于字符串 $s = u v$，我们称 $v$ 是 $s$ 的 "好的" 后缀当且仅当存在字符串 $t$ 满足 $v t$ 是 $s t$ 的最小后缀。下面证明：一个长度为 $n$ 的字符串，"好的" 后缀的数量不超过 $\log n$ 个。
我们只需证明，如果两个 "好的" 后缀 $u, v$ 满足 $\left| u \right| < \left| v \right|$，则一定有 $2 \left| u \right| \leq \left| v \right|$。
反之，设存在两个后缀 $u, v$ 满足 $\left| u \right| < \left| v \right| < 2 \left| u \right|$。
首先，由于 $s \sqsupset u, s \sqsupset v, \left| u \right| < \left| v \right|$，因此 $v \sqsupset u$。
其次，考察 $v \left[ 1 .. \left| u \right| \right]$ 和 $u$。
如果 $u < v \left[ 1 .. \left| u \right| \right]$，则 $v$ 不是 "好的" 后缀，因为 $u t$ 永远小于 $v t$。
同理，$u > v \left[ 1 .. \left| u \right| \right]$ 也是不行的，故只有 $u = v \left[ 1 .. \left| u \right| \right]$，即 $u \sqsubset v$。
由 $u \sqsubset v$ 及 $v \sqsupset u$ 可知 $u \vartriangleleft v$ ($u$ 是 $v$ 的非平凡 border)。
由 Border —— 周期定理，$v$ 有一个长度为 $\left| v \right| - \left| u \right| < \dfrac {\left| v \right|} 2$ 的周期，记为 $T$。于是 $u = T \beta, v = T^2 \beta$ ($\beta \neq \varepsilon$)。
由于 $u$ 是 "好的" 后缀，因此存在串 $t$，满足 $v t > u t$，即 $T^2 \beta t > T \beta t \Rightarrow T \beta t > \beta t$。
而 $\beta$ 是 $s$ 的非空后缀，且 $\beta t < T \beta t = u t$，这与 $u$ 是 "好的" 后缀矛盾。故不存在这样的 $u, v$。
由于有 "区间修改" 的操作，因此考虑使用线段树维护对应区间 "好的" 后缀 (的左端点坐标) 的集合。由于 "好的" 后缀数量不超过 $\log n$ 个，这样一来空间也不会爆。
首先，我们需要考虑如何合并两个区间的信息 ("好的" 后缀)。即给定 $s$ 和 $t$ 的 "好的" 后缀，求 $s t$ 的 "好的" 后缀。
不过，这样可能会有些许难度，因此我们允许一些不是 "好的" 后缀的后缀加入集合，但需要保证 "好的" 后缀一定在集合中，且元素个数还是 $O \left( \log n \right)$ 的。这样，我们就有一个方便的合并算法了。
由上面的证明过程，我们可以发现：设一个串 $s$ 中 "好的" 后缀 (长度从小到大) 分别为 $s_1, s_2, \cdots, s_k$ (其中 $\left| s_i \right| < \left| s_{i+1} \right|$)，则一定有 $s_1 \vartriangleleft s_2 \vartriangleleft \cdots \vartriangleleft s_k$。
由于线段树的区间是等分的，因此合并过程中左子区间对最后答案的贡献至多为 $1$。因此我们首先不管三七二十一把右子区间中的所有后缀都加进来。
设当前的后缀集合为 $S = \left\{ s_1, s_2, \cdots, s_k \right\}$。我们从短到长考虑左区间的后缀 $l$。首先，我们比较 $s_k$ 与 $l \left[ 1 .. \left| s_k \right| \right]$，如果 $s_k < l \left[ 1 .. \left| s_k \right| \right]$，则 $s_k \not\vartriangleleft l$ ($s_k$ 不是 $l$ 的 border)，因此 $l$ 就可以直接舍弃了。
如果 $s_k > l \left[ 1 .. \left| s_k \right| \right]$，那么显然 $l$ 这个后缀已经不可能是 "好的" 后缀了，于是将其舍弃，继续寻找下一个元素 $s_{k-1}$。
如果 $s_k = l \left[ 1 .. \left| s_k \right| \right]$，即 $s_k \vartriangleleft l$。根据引理，如果 $\left| l \right| < 2 \left| s_k \right|$，由证明过程，则我们直接丢弃 $s_k$，然后将 $l$ 插入；否则 ($2 \left| s_k \right| \leq \left| l \right|$)，直接将 $l$ 插入 $S$ 即可。
这样，就可以在 $O \left( \log^2 n \right)$ 的时间内完成两个节点的合并，$O \left( n \log n \right)$ 的时间完成建树。
考虑一次询问，先把区间 $\left[ l, r \right]$ 拆分为 $O \left( \log n \right)$ 个线段树节点，然后只需要对每个线段树节点，把对应区间的 "候选后缀" 集合全都拿来比较一下即可。
容易证明，字典序最小的后缀在 "候选后缀" 中，因此正确性没有问题。由于共有 $O \left( \log^2 n \right)$ 个候选后缀，因此询问中这部分的复杂度为 $O \left( \log^3 n \right)$。
对于一次修改，由于是区间加，因此容易发现，如果某个线段树节点对应的区间与 $\left[ l, r \right]$ 无交或是 $\left[ l, r \right]$ 的子集，则不影响该节点的集合。
由线段树定位理论，只有 $O \left( \log n \right)$ 个节点的集合需要改变。故我们要更新 $O \left( \log n \right)$ 次，这部分的复杂度为 $O \left( \log^3 n \right)$。
对于每个字符的具体的值，可以采用暴力的方法将其加 $d$。你要相信 $n \cdot q = 6 \times 10^9$ 次加法是很快的！
因此总的时间复杂度为 $O \left( (n + q) \log^3 n + n q \right)$ (其中 $n q$ 项的常数非常小以至于它不是瓶颈)。
#include <bits/stdc++.h>
#define segc int M = (L + R - 1) >> 1, lc = id << 1, rc = lc | 1
const int N = 200054, LN = 18;
struct node {int v[LN], cnt;} x[N * 4];
int n, q, ans, a[N];
inline int intcmp(const int *buffer1, const int *buffer2, int count) {for (; --count && *buffer1 == *buffer2; ++buffer1, ++buffer2); return *buffer1 - *buffer2;}
void update(node &ret, const node &l, const node &r, int end) {
int i, u, v, c;
memcpy(ret.v, r.v, (ret.cnt = r.cnt) << 2);
for (i = 0; i < l.cnt; ++i) for (; ; ) {
u = l.v[i], v = ret.v[ret.cnt - 1];
if ((c = intcmp(a + u, a + v, end - v)) > 0) break;
if (!c) {ret.cnt -= (end - v) * 2 > end - u, ret.v[ret.cnt++] = u; break;}
if (!--ret.cnt) {ret.v[ret.cnt++] = u; break;}
}
}
void build(int id, int L, int R) {
if (L == R) {x[id].v[0] = L, x[id].cnt = 1; return;}
segc; build(lc, L, M), build(rc, M + 1, R);
update(x[id], x[lc], x[rc], R + 1);
}
void adj(int id, int L, int R, int ql, int qr) {
if (ql <= L && R <= qr) return; segc;
if (ql <= M) adj(lc, L, M, ql, qr);
if (qr > M) adj(rc, M + 1, R, ql, qr);
update(x[id], x[lc], x[rc], R + 1);
}
void range(int id, int L, int R, int ql, int qr) {
if (ql <= L && R <= qr) {
for (int i = 0; i < x[id].cnt; ++i) intcmp(a + x[id].v[i], a + ans, qr - ans + 1) >> 31 && (ans = x[id].v[i]); return;
}
segc;
if (qr > M) range(rc, M + 1, R, ql, qr);
if (ql <= M) range(lc, L, M, ql, qr);
}
int main() {
int i, l, r, d, op;
scanf("%d%d", &n, &q);
for (i = 1; i <= n; ++i) scanf("%d", a + i);
for (build(1, 1, n); q; --q)
if (scanf("%d%d%d", &op, &l, &r), op == 1) {
for (scanf("%d", &d), i = l; i <= r; ++i) a[i] += d;
adj(1, 1, n, l, r);
} else
range(1, 1, n, l, ans = r), printf("%d\n", ans);
return 0;
}
坑1：由于字符集为整数，因此比较的时候不能使用 memcmp 要手写 intcmp。
坑2：询问时要按照从短到长的顺序，因此要先访问右子树再访问左子树。