Permutation Query

TarikHassan, ash_98 National Girls' Programmi...
Limits 1s, 256 MB

An array of integers p1,p2,....,pnp_1,p_2,....,p_n is called a permutation if it contains each number from 11 to nn exactly once. For example, the following arrays are permutations: [3,1,2],[1],[1,2,3,4,5][3,1,2], [1], [1,2,3,4,5] and [4,3,1,2][4,3,1,2]. The following arrays are not permutations: [2],[1,1],[2,3,4][2], [1,1], [2,3,4].

You are given an array of nn elements and qq queries. These queries are of two types:

  • 1lr1 \, \, l \, \, r means, if Al,Al+1,Al+2,,,,Ar1,ArA_l,A_{l+1},A_{l+2},,,,A_{r-1},A_r holds permutation, then print YES. Otherwise, print NO.

  • 2 pos val2 \text{ pos val} means, set Apos=val.A_{pos}=val.


The first line contains two integer nn and qq(1n,q2×105)(1\leq n,q \leq 2\times10^{5})the size of the array and the number of queries.

The second line contains nn integer A1,A2,....,AnA_1,A_2,....,A_n(1Ain)(1\leq A_i\leq n).

The next qq lines contain two types of queries.

Typei{1,2}Type_i \in \{1, 2\}

1lirin1\leq l_i\leq r_i\leq n

1posi,valin1\leq pos_i, val_i \leq n


For every query of type 11, print YES if ll to rr holds a permutation. Otherwise, print NO.


5 4
2 1 3 4 5
1 1 5
2 4 3
1 1 5
1 1 3

Initially, the array looks like this [2,1,3,4,5].

After the second query, the array becomes [2,1,3,3,5].


Login to submit.


63% Solution Ratio
NirjhorEarliest, 8M ago
Farhan20Fastest, 0.1s
samiulsamiLightest, 4.6 MB
serotoninShortest, 1201B
Toph uses cookies. By continuing you agree to our Cookie Policy.