Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Permutation Query

By TarikHassan, ash_98 · 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.

Input

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

Output

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

Sample

InputOutput
5 4
2 1 3 4 5
1 1 5
2 4 3
1 1 5
1 1 3
YES
NO
YES

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

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


Discussion

Statistics


63% Solution Ratio

NirjhorEarliest, 1M ago

Farhan20Fastest, 0.1s

samiulsamiLightest, 4.6 MB

serotoninShortest, 1201B

Submit

Login to submit

Editorial

First, how can we say that an array is a permutation? Suppose array length is nnn, then sum of the p...

Toph uses cookies. By continuing you agree to our Cookie Policy.