SUMSUM - Enjoy Sum with Operations


You are given N numbers of the array (N <= 100000), all less than 10^8 and greater than 0.

Now, you are given 2 queries:

  1. "1 x i" : Change the i-th number to x. (0 <= x <= 10^8)
  2. "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.


hide comments
Tanmoy Tapos Datta: 2017-10-28 23:25:25

Can be done with segment tree or BIT and some combinatorics. Here is an editorial for this problem-
https://turing13.wordpress.com/2017/10/28/spoj-sumsum-enjoy-sum-with-operations/

sas1905: 2017-06-26 01:32:25

2 WA for skipping the note part..:(

akt_1998: 2017-06-25 21:37:16

BIT+bitmasking -> AC in one go

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

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