EVENFRQ - Even Frequency
Kutus loves even number. Girl friend of kutus, name putus makes an interesting problem for kutus to testing his even number knowledge. Putus gives an integer array A, consisting of N number.
Putus asked Kutus to process the following three types of queries on this array accurately and efficiently.
• 0 X V: add V to the Xth element of array. i.e AX = AX + V.
• 1 L R V: replace all the element in range L to R with V.
• 2 L R: Find out whether all elements frequency in the range L to R is/are even or not
Input start with an integer T, which denotes the number of test case. Each case contains 2 space separated integer N and Q denoting the size of array A and the number of queries to be performed.
Next line contains N space separated integers denoting the elements of array A. Each of the next Q lines of input contains a query having one of the mentioned three types. There will be no more than fifty update operation (type 0 & type 1).
For each case print the case number and print the answer. If all elements frequency in the range L to R is/are even, then answer will be ‘Yes’ otherwise answer will be ‘No’.
T <= 10
1 <= N <= 100000
1 <= Q <= 100000
0 <= Ai , V <= 100000
1 <= L <= R <= N
Input: 1 5 6 1 2 2 3 2 2 2 3 0 5 1 2 2 5 2 1 5 1 1 3 2 2 1 5 Output: Case 1: Yes Yes No No
getting TLE even after using both methods of mapping and hashing.. :(
I've used some evil technique to successfully "attack" this problem :-)