SPOJ.com - Problem SUMSUM

SUMSUM - Enjoy Sum with Operations

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!

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

hide comments

2016-03-13 02:26:39 amit_gh
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.

2015-12-21 07:17:00 ashish kumar
It is difficult to get AC using segment tree !
done using BIT + bitmasking

2015-05-13 12:58:43 Pagan Min
segtree + bitmask...enjoyed solving :)

2015-01-16 18:07:30 Ashish Khatkar
Requires too much optimization. Finally AC :)

2014-07-19 14:32:00 Pratyush Kar
good question remember to use brackets lot of WA because of that

2014-05-31 14:10:42 kaushal yadav
@Devendra Agarwal Getting TLE in 7th test (ID: 11680501) Please have a look into it.

Last edit: 2014-05-31 17:30:48

2013-09-05 12:39:09 nitish rao
@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

2013-09-05 04:57:23 fitcat
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