Polynomial queries
/

## Algorithms, Datastructures, Dynamic Programming, Mathamatics, Segment Trees

Problem
Editorial
Analytics

You are given an array $A$ of size $N$. You must perform $Q$ queries on it. There are two types of queries:

• Change pos val: In this operation, you are required to change the value of $A[pos]$ to $val$.
• Poly L R: You must answer whether there exists a polynomial $P$ such that $P(A[k]) = k$ for every $k$ between $L$ and $R$ $(L \le k \le R)$.

Input format

• The first line of the input contains two integers $N$ and $Q$.
• The next line contains $N$ integers describing the initial array.
• The next $Q$ lines describe a query each. A change operation is denoted by 0 pos val and a question is denoted by 1 L R.
Note: The array is 1-indexed.

Output format

For each query of the second type, print a line containing Yes or No.

Constraints

$N,\ Q \le 4 \times 10^5$

For a test set worth 30 points, it holds that $N,\ Q \le 10^3$.

All the numbers initially and after each update, are between 1 and $4\times 10^5$.

SAMPLE INPUT
3 3
1 2 3
1 1 3
0 2 1
1 1 2

SAMPLE OUTPUT
Yes
No

Explanation

For the first query, the polynomial p(x) = x is a valid option.

For the second query, there is no answer, as we would need to have 1 = p(1) = 2

Time Limit: 1.5 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...