P5211 [ZJOI2017] String

Pig Xiaoxia has recently been studying string-related theory, and now he has encountered the following problem.

Maintain a dynamic string $s_{1..n}$, whose alphabet is all integers with $|x| \leq 10 ^ 9$. You need to support two operations: 1. Input $l, r, d$. For all $l \leq i \leq r$, modify $s_i$ to $s_i + d$. Note that $d$ may be negative. 2. Input $l, r$. Output the starting position of the lexicographically smallest suffix of the substring $s_{l..r}$. That is, if the smallest suffix is $s_{p..r}$ ($l \leq p \leq r$), output $p$.

The first line contains two non-negative integers $n, q$. The next line contains $n$ positive integers, representing the initial string. The next $q$ lines each describe an operation in the form $1\ l\ r\ d$ or $2\ l\ r$, corresponding to the two operations above.

For each query operation, output the answer in order.

| Test Point ID | $n$ | $m$ | Other Constraints | | ------ | ------ | ------ | ------ | | $1$ | $\leq 300$ | $\leq 300$ | None | | $2$ | $\leq 2 \times 10^4$ | $\leq 2 \times 10^4$ | None | | $3$ | $\leq 2 \times 10^4$ | $\leq 2 \times 10^5$ | None | | $4$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | Only the second type of operation | | $5$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | Only the second type of operation | | $6$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | testdata generated randomly | | $7$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | testdata generated randomly | | $8$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | None | | $9$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | None | | $10$ | $\leq 2 \times 10^5$ | $\leq 3 \times 10^4$ | None | Constraints: For $100\%$ of the data, $1 \leq l \leq r \leq n$, $|d| \leq 10 ^ 3$, and $|s_i| \leq 10 ^ 8$. Note: In test points $6$ and $7$, during random generation, $s_i$ is chosen randomly from $\{0, 1\}$, and $d$ is chosen randomly from $\{-1, 1\}$. The operation type and the operation interval are both selected uniformly at random. Translated by ChatGPT 5