P8419 [THUPC 2022 Finals] riapq

Given a permutation $a_1,\dots,a_n$, you need to maintain a sequence $b_1,\dots,b_n$, with initial values all equal to $0$. There are $m$ operations in total: - Update operation: given $l,r$, for every pair $(i,j)$ satisfying $l\le i\le j\le r,\;a_i\le a_j$, increase $b_j$ by $1$. - Query operation: given $x$, query $b_x$.

The first line contains two integers $n,m$. The second line contains $n$ integers representing $a_1,\dots,a_n$ in order. The next $m$ lines each contain either $1,l,r$ or $2,x$, representing an update operation or a query operation. All numbers in the input are integers.

For each query operation, output one line containing one integer, representing the answer.

Constraints: $1\le n,m\le 2\times 10^5$. $1\le a_i\le n$, and all $a_i$ are pairwise distinct. $1\le l\le r\le n$. $1\le x\le n$. Translated by ChatGPT 5