Truy vấn giá trị phân biệt II (Distinct Values Queries II)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $x_1,\ldots,x_n$ và hai loại thao tác: 1 k u đổi $x_k$ thành $u$; 2 a b kiểm tra liệu mọi giá trị trong đoạn $x_a..x_b$ có đôi một khác nhau hay không.

Dữ liệu vào

Dòng đầu chứa $n,q$. Dòng thứ hai chứa dãy ban đầu. Mỗi trong $q$ dòng tiếp theo là 1 k u hoặc 2 a b.

Kết quả

Với mỗi thao tác loại 2, in YES nếu mọi giá trị trong đoạn đều khác nhau, ngược lại in NO.

Subtask

Subtask 1 (20%)

• $n\le 30$, số truy vấn $\le 30$.
• Các điều kiện còn lại như Subtask 3.

Subtask 2 (30%)

• $n\le 3000$, số truy vấn $\le 3000$.
• Các điều kiện còn lại như Subtask 3.

Subtask 3 (50%)

• $1\le n,q\le2\cdot10^5$
• $1\le x_i,u\le10^9$
• $1\le k\le n$
• $1\le a\le b\le n$

Ví dụ

Input

5 4
3 2 7 2 8
2 3 5
2 2 5
1 2 9
2 2 5

Output

YES
NO
YES

Giải thích

Ban đầu đoạn [2,5] chứa [2,7,2,8] nên có lặp 2 và trả NO. Sau khi đổi vị trí 2 thành 9, đoạn này thành [9,7,2,8] nên trả YES.