SPOJ.com - Problem SUMSUM

SUMSUM - Enjoy Sum with Operations

#tree #bitmasks

You are given N numbers of the array (N ≤ 100000), all less than 10⁸ and greater than 0.

Now, you are given 2 types of queries:

"1 x i" : Change the i-th number to x. (0 ≤ x ≤ 10⁸)
"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)

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.

< Previous 1 2 Next >

	nitish rao: 2013-09-05 12:39:09 @Devendra Getting NZEC error with JAVA.. :( Can you please check it? Prob ID:9987700 Edit: and TLE in C++ on 6th test. id:9987954 plz see into it. Re: You are doing some computations which are not required.(Hint: Look at the constraints ;) ) Edit: Well I tried to optimize it, still TLE :(. What are the constraints for 'Q'?? id:9988867 Re: Q<=100000 Last edit: 2013-09-06 04:37:39
	fitcat: 2013-09-05 04:57:23 The operation 1 0 1 is invalid, the element cannot be 0. All the operations are binary. Does i1 < i2 hold? Re: i1<=i2 holds always and could you please elaborate your problem on why you think that the element cannot be 0. Note: when we do xor/or/and of any 2 integers ,we xor/or/and each bit. so setting a nummber to 0 essentially means setting all bits to 0. Edit: x cannot be 0 as it is given by the constraint (10^8=>x>=1). When i1 = i2, what is the answer for the operation XOR? By definition, it should be 0, right? Re: Thanks for pointing out fitcat,i have edited the constraints and yes it will be zero. Thanks Fitcat,i could observe a problem when i1=i2 , i have edited the problem,have a look at it now,i think now it is not ambigous. Last edit: 2013-09-05 04:58:23