SUMSUM - Enjoy Sum with Operations
You are given N numbers of the array (N ≤ 100000), all less than 108 and greater than 0.
Now, you are given 2 types of queries:
- "1 x i" : Change the i-th number to x. (0 ≤ x ≤ 108)
- "2 Op i1 i2": Compute the sum of all two elements taken at a time within index i1 to i2 (both inclusive) under the operation Op. Op could be XOR, OR or AND.
For example, let N=4, Query=3 and "10 20 30 40" be the Initial array.
Query:
2 OR 1 3 1 0 1 2 OR 1 3
Answer:
2 OR 1 3 → (10 OR 20) + (20 OR 30) + (10 OR 30) 1 0 1 → Now array becomes 0 20 30 40 2 OR 1 3 → (0 OR 20) + (20 OR 30) + (0 OR 30)
Example
Input: 4 3 10 20 30 40 2 OR 1 3 1 0 1 2 OR 1 3 Output 90 80
NOTE: If i1 is equal to i2, always output 0.
hide comments
amit_gh:
2016-03-13 02:26:39
Take care of output limits. Java solution gave TLE whereas same c++ solution got AC. I used same i/o functions in java that I have been using to successfully solve other problems in java. I think admin should increase time limit for java solutions. |
|
ashish kumar:
2015-12-21 07:17:00
It is difficult to get AC using segment tree !
|
|
Pagan Min:
2015-05-13 12:58:43
segtree + bitmask...enjoyed solving :) |
|
Ashish Khatkar:
2015-01-16 18:07:30
Requires too much optimization. Finally AC :) |
|
Pratyush Kar:
2014-07-19 14:32:00
good question remember to use brackets lot of WA because of that |
|
kaushal yadav:
2014-05-31 14:10:42
@Devendra Agarwal Getting TLE in 7th test (ID: 11680501) Please have a look into it. Last edit: 2014-05-31 17:30:48 |
|
nitish rao:
2013-09-05 12:39:09
@Devendra Getting NZEC error with JAVA.. :( Can you please check it? Prob ID:9987700
|
|
fitcat:
2013-09-05 04:57:23
The operation 1 0 1 is invalid, the element cannot be 0.
|
Added by: | devu |
Date: | 2013-08-30 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own Problem |