SAMTWARR - Two Array Problem

no tags 

You are given two arrays each of length N(1 <= N <= 100000) which are initially filled with zeros. You have to apply M (1 <= M <= 100000) queries of three kind: 

0 arr left right :  calculate and output sum of elements from left to right in array arr (arr = 0 -- first array, arr = 1 -- second     array); 
1 arr idx newValue : change value of element at index idx of array arr on newValue;
2 left right :  swap range of elements of two arrays from left to right ( for i = left to right do swap(a[i], b[i]) );

Input

The first line of input contains two integers - N, M. The folowing M lines contains information about queries.
On each query - one line:
First integer number cmd contains 0, 1 or 2 (type of query described above).
if cmd equals 0, then following 3 integers arr, left, right - 0 <= arr <= 1, 0 <= left <= right <= N - 1.
if cmd equals 1, then following 3 integers arr, idx, newValue - 0 <= arr <= 1, 0 <= idx <= N - 1, -10000 <= newValue <= 10000.
if cmd equals 2, then following 2 integers left, right - 0 <= left <= right <= N - 1.

Output

On each query with cmd equals 0 you should output corresponding value described above.

Example

Input:
5 10
1 0 0 1
1 1 4 2
0 0 0 4
0 1 0 4
2 0 0
0 0 0 4
0 1 0 4
2 0 4
0 0 0 4
0 1 0 4

Output:
1
2
0
3
3
0


hide comments
DK...: 2019-04-18 03:35:37

easy for Splay Tree

julkas: 2018-12-16 11:12:02

Good problem.

mahmud2690: 2016-09-26 14:38:32

Interesting :D

fire_heart: 2016-08-24 13:43:40

AC in first try ^_^

hodobox: 2016-06-18 04:06:49

Had to make a testcase-generator generator for bruteforce (to find input with low amount of querries that gives WA), but as a result learnt something new :)

Stephen Merriman: 2010-03-31 04:21:16

The time displayed is the sum of times for all input files. The time limit is per input file.

Seshadri R: 2010-03-30 03:53:28

In statistics & best solutions page, there are six accepted solutions that have exceeded the time limit 2s. Then, how did they get accepted in the first place?


Added by:rajeshsr
Date:2010-03-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS OBJC PERL6 SQLITE VB.NET
Resource:https://www.spoj.pl/users/cmd/