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 x-th element in array A, i.e. Ax = y.
- 2 l r - print "Yes" if subarray A[l..r] is dominating, "No" otherwise
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.
For each query of type 2, output the answer to the query in a single line.
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai, y ≤ 109
- 1 ≤ x ≤ N
- 1 ≤ l ≤ r ≤ N
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
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.
|Tags||cook72, medium, mgch, segment-tree|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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|
Fetching successful submissions