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.

Click here to see my set of problems at Spoj.


hide comments
vishal_781: 2023-04-21 12:15:27

ac in single go bc

sankalp_7: 2022-11-22 14:55:28

@codercodecoder You haven't even tried it... And you are writing, ac in one go, XD

depressedboy: 2022-01-20 10:24:04

Extremely Brilliant Problem one must try this problem
( BITMASKING + RANGE_QUERY + COMBINATORICS )
You will learn a lot of things

Last edit: 2022-01-20 10:25:15
codercodecoder: 2020-04-19 16:47:40

ac in one go madharchod

learnerinblack: 2018-06-07 12:49:36

AC in one go :D BIT + bitmasking => learnt a lot

arpit728: 2018-04-17 06:46:33

@kaushal yadav

How you got to know in which case you are getting TLE.

amit_ranjan: 2018-01-02 20:00:06

My 180 :)

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-
<snip>

Last edit: 2022-10-12 20:30:23
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


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