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)

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.

Click here to see my set of problems at Spoj.

Submit solution!

hide comments

< Previous 1 2 Next >

	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 ! done using BIT + bitmasking
	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 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

Submit solution!

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