All Tracks Algorithms Dynamic Programming Problem

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

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?