P3863 Sequence

Given a sequence of length $n$, there are $q$ operations of the following forms. $1~l~r~x$ means adding $x$ to each element with index in $[l,r]$ (note that $x$ may be negative). $2~p~y$ means querying for how many seconds in the past $a_p$ has been at least $y$ (excluding the current second; see the sample for details). Time starts at second $0$, and the $i$-th operation occurs at second $i$.

The first line contains two integers $n,q$, as described. The second line contains $n$ integers $a_i$, the initial values of the sequence. Each of the next $q$ lines starts with $\text{opt}$, indicating the type of this operation. If $\text{opt} = 1$, it is followed by three integers $l, r, x$, as described. If $\text{opt} = 2$, it is followed by two integers $p, y$, as described.

For each operation of type $2$, output one integer on a single line indicating the answer.

Explanation for Sample 1: at position $1$, the values from second $0$ to second $3$ are $1,1,-2,-2$. For the first query, during seconds $0$ to $1-1=0$, the value is not less than $2$. For the second query, during seconds $0$ to $3-1=2$, the value is not less than $1$, namely at second $0$ and second $1$. For $30\%$ of the testdata, $n,q \leq 1000$. For $70\%$ of the testdata, $n,q \leq 50000$. For $100\%$ of the testdata, $2 \leq n,q \leq 100000$, $1 \leq l \leq r \leq n$, $1 \leq p \leq n$, $-10^9 \leq x,y,a_i \leq 10^9$. Translated by ChatGPT 5