Equal Median

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/LTIME74/hindi/EQMD.pdf), [Bengali](http://www.codechef.com/download/translated/LTIME74/bengali/EQMD.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/LTIME74/mandarin/EQMD.pdf), [Russian](http://www.codechef.com/download/translated/LTIME74/russian/EQMD.pdf), and [Vietnamese](http://www.codechef.com/download/translated/LTIME74/vietnamese/EQMD.pdf) as well. You are given a sequence of integers $A_1, A_2, \ldots, A_N$. You should process $Q$ queries. In each query:  You are given two integer parameters $id$ and $v$.  Change the value of $A_{id}$ to $v$.  Then, consider all ways to partition the sequence $A_1, A_2, \ldots, A_N$ into multisets $M_1, M_2, \ldots, M_K$ (for an arbitrary $K \ge 1$) such that:  Each element of $A$ is assigned to exactly one multiset.  The medians of all multisets are the same.  Find the maximum possible value of $K$, i.e. the maximum number of multisets in such a partition. The median of a multiset is defined as follows: Consider the multiset as a sequence sorted in nondecreasing order. If its size is odd, the median is the middle element. If it is even, there are two integers in the middle and the median is the smaller one (either one if they are equal). Note that a multiset may contain duplicate elements, so if $x$ elements of $A$ with identical values are assigned to the same multiset, that multiset will contain the same integer $x$ times. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains two spaceseparated integers $N$ and $Q$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$.  Each of the next $Q$ lines contains two spaceseparated integers $id$ and $v$ describing a query. ### Output For each query, print a single line containing one integer ― the maximum number of multisets. ### Constraints  $1 \le T \le 1,000$  $1 \le N, Q \le 10^5$  $1 \le A_i \le 10^9$ for each valid $i$  $1 \le id \le N$  $1 \le v \le 10^9$  the sum of $N$ over all test cases does not exceed $10^6$  the sum of $Q$ over all test cases does not exceed $10^6$ ### Subtasks **Subtask #1 (50 points):**  $N, Q \le 1,000$  the sum of $N$ over all test cases does not exceed $10,000$  the sum of $Q$ over all test cases does not exceed $10,000$ **Subtask #2 (50 points):** original constraints ### Example Input ``` 1 4 3 1 1 1 2 4 1 4 2 3 2 ``` ### Example Output ``` 4 3 2 ```Author:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/EQMD 
Tags  adhoc, kingofnumbers, ltime74, median 
Date Added:  24072019 
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, rust, SCALA, swift, 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, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, 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. 