DRUID - Druid and Queries
Druid accumulates numbers very fast, once he had some numbers, and some queries, he asks you to play a game, the game goes as follows, given N numbers and Q queries; the fastest to answer all the Q queries wins the game. Druid challenges you to answer all the queries faster than him.
Can you beat Druid in his game?
Input
The first line contains 2 space separated integers N, Q (1 <= N, Q <= 105), the second line contains N space separated integers (0 <= Ni < 231), after that follows Q lines, the ith line contains 3 space separated integers T, A, and B, T (0 <= T <= 1) is the query type, A and B (1 <= A <= B <= N) are indices (1-based).
Output
For each query, output one line contains the answer to the i-th query. If T is 0, then the answer should be the number of odd numbers between the 2 indices A and B inclusive, otherwise, the answer should be the number of even numbers between the 2 indices A and B inclusive.
Example
Input: 10 5 10 6 4 9 46 21 99 36 45 1 1 1 2 1 1 3 1 1 4 0 1 5 0 5 10 Output: 2
3
3
1
4
Added by: | eagle93 |
Date: | 2014-06-23 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |