Chef and Array

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef likes arrays and anything related to it. He call an array V dominating if there exists a number x (the dominator) whose number of occurrences in V strictly greater than half the size of the array (that is, floor(V/2)).
His friend Dmytro wants to make Chef happy, so he presented this interesting problem for Chef.
Given an array A. You have to process Q queries on it. Queries can be one of two types:
 1 x y  Assign value y to xth element in array A, i.e. A_{x} = y.
 2 l r  print "Yes" if subarray A[l..r] is dominating, "No" otherwise
Input
The first line of input contains two integers N and Q denoting the number of elements in A, and the number of queries to be executed.
The second line of input contains N space separated integers denoting the array A.
Each of the next Q lines contains one query.
Output
For each query of type 2, output the answer to the query in a single line.
Constraints
 1 ≤ N, Q ≤ 10^{5}
 1 ≤ A_{i}, y ≤ 10^{9}
 1 ≤ x ≤ N
 1 ≤ l ≤ r ≤ N
Example
Input: 5 8 1 2 3 2 1 2 1 5 2 2 4 1 3 2 2 1 5 1 2 3 2 1 5 1 3 1 2 1 5 Output: No Yes Yes No Yes
Explanation
For first query, we have to tell whether the entire array A is dominating or not. It turns out that it is not dominating, because occurrences of 1 and 2 are equal to 2 (which is not more than half the size of array, i.e. 2) and that of 3 is 1.
For second query, the subarray [2, 3, 2] is dominating and 2 is the dominator of it. Number of occurrences of 2 is 2 which is strictly greater than half the size of subarray, i.e. floor(3/2) = 1.
Author:  mgch 
Tester:  karanaggarwal 
Editorial  http://discuss.codechef.com/problems/CHEFLKJ 
Tags  cook72, medium, mgch, segmenttree 
Date Added:  10072016 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 