Martian Coin Game

All submissions for this problem are available.
Freakin' news has recently claimed that they have discovered a civilization on mars and that they have established contact with the martians. Following is a summary of the midnight hour breakin' news on freakin' news :
Playful Configuration
A configuration of n coins placed in a 2 × n grid (2 rows, n columns) such that every column contains exactly one coin is called a playful configuration.
(Coins can only be placed inside a cell, and not on the boundary of two cells. Every coin is facing either headsup or tailsup.)
One can update a playful configuration in the following ways :
1) switch(i, j) , where 1<=i<=j<=n :
For all integers r such that i<=r<=j, do the following :
If there is a coin at (1, r), remove it and place it, facing same side up at (2, r).
Otherwise remove the coin at (2, r) and place it, facing same side up at (1, r).
2) flip(i, j) , where 1<=i<=j<=n :
For all integers r such that i<=r<=j, do the following :
Flip the coin in column r without changing its position. (If the coin is initially facing headsup then after flipping it will face tailsup and vice versa.)
One can query a playful configuration in the following way :
query(i, j) , where 1<=i<=j<=n :
Let h1 be the number of integers r such that i<=r<=j and there is a coin facing headsup at (1,r).
Let h2 be the number of integers r such that i<=r<=j and there is a coin facing headsup at (2,r).
Let t1 be the number of integers r such that i<=r<=j and there is a coin facing tailsup at (1,r).
Let t2 be the number of integers r such that i<=r<=j and there is a coin facing tailsup at (2,r).
query(i, j) returns h1,h2,t1 and t2.
The king of mars plays the following game every month :
He arranges n coins in a playful configuration. Initially all coins are in the first row (facing either headsup or tailsup). He periodically performs operations on the configurations. Each operation is either an update (flip or switch) or a query. Any player who responds correctly to each query wins a large prize. Unfortunately, the game is too difficult and no player has yet won the coveted prize.
This month however, one of the ministers has gained access to the initial configuration as well as a list of all the operations. The minister has asked freakin' news to help him answer all queries correctly. Your job is to do this task for freakin' news.
Input Format
The first line contains a single integer n : The number of coins in the playful configuration.
The next line contains n space seperated integers f[1],f[2],...f[n] which describe the inital state of the coins. The coin in column i is initially at (1,i). If f[i] is 1, the coin at (1,i) is initially facing headsup. Otherwise, the coin at (1,i) is initially facing tailsup.
The next line contains a single integer m : The number of operations.
The k'th of the next m lines contains 3 integers op,i,j which describe the k'th operation. Each operation is described as follows :
If op is 0, the operation is query(i,j).
If op is 1, the operation is flip(i,j).
If op is 2, the operation is switch(i,j).
Output Format
For each query, the program must output a single line consisting of 4 space seperated integers h1, h2, t1 and t2.
Constraints
1<=n<=100000
Each f[i] is either 0 or 1.
1<=m<=100000
For each operation, op is either 0,1 or 2.
For each operation, 1<=i<=j<=n.
Sample Input
10
1 1 1 1 1 0 0 0 0 0
5
0 1 7
2 3 5
0 1 7
1 1 10
0 1 7
Sample Output
5 0 2 0
2 3 2 0
2 0 2 3
Explanation
At the time of the first query, the configuration is :
H H H H H T T T T T
E E E E E E E E E E
At the time of the second query the configuration is :
H H E E E T T T T T
E E H H H E E E E E
At the time of the third query the configuration is :
T T E E E H H H H H
E E T T T E E E E E
Author:  architk 
Tags  architk 
Date Added:  23032012 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions