AT_aalc001_d 転倒数

You are given a sequence $ A=(A_1,A_2,\ldots,A_N) $ of length $ N $ consisting of $ 0,1,2 $ . Process $ Q $ queries. Each query is of one of the following $ 2 $ types: - `1 i x`: Change $ A_i $ to $ x $ . - `2 l r`: Print the inversion count of the sequence $ (A_l,A_{l+1},\ldots,A_r) $ . Here, the **inversion count** of a sequence $ B=(B_1,B_2,\ldots,B_k) $ of length $ k $ is the number of pairs of integers $ (i,j) $ satisfying $ 1 \leq i \lt j \leq k $ and $ B_i \gt B_j $ .

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ Each query is given in one of the following formats: > $ 1 $ $ i $ $ x $ > $ 2 $ $ l $ $ r $

Let $ q $ be the number of type $ 2 $ queries. Print $ q $ lines. The $ j $ -th line should contain the answer to the $ j $ -th type $ 2 $ query.

### Sample Explanation 1 Initially, $ A=(2,0,1,2,0) $ . After processing query $ 3 $ , $ A=(2,2,1,2,0) $ . ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 0 \leq A_i \leq 2 $ - For type $ 1 $ queries, $ 1 \leq i \leq N $ , $ 0 \leq x \leq 2 $ - For type $ 2 $ queries, $ 1 \leq l \leq r \leq N $ - All numerical values in the input are integers.