# 0 and 1 Queries in tables of N*N cells

There is a square table composed of N*N Cells. Initially all cell is filled with a number 0. Two types of Operations can be performed on the table.

R i k: All the numbers in the cells on ith row has been changed to k.

C i k: All the numbers in the cells on ith column has been changed to k.

Please Note : k ∈ {0, 1} (ie k = 0 or 1).

At any time ,Alice is interested to know the total number of 0's on some row or total number of 0's on some column.

Input

First line contains a single integer N as described above.Next line contains a single integer Q representing the total operations and queries from Alice. Then Followed Q lines , containing operations or queries in following format:

R i k: All the numbers in the cells ith row has been changed to k.

C i k: All the numbers in the cells ith column has been changed to k.

qc i :How many 0's are there in ith row?

qr i:How many cols are there in ith col?


Examples: Input:

3

6

qr 1

C 1 1

qr 1

qc 1

R 1 0

qc 1


Output:

3

2

0

1


I tried a Naive solution.But it got time out. The constraint is quite large and the time limit is just 0.55 Seconds.

**1 ≤ N, Q ≤ 500000 (6 * 10^5)

How can i solve this problem within the given time-limit?

P.S: This is not a homework.

• Please give proper credit for the source of the problem. Also, please include some of your own thoughts. Which operations are timed, only queries or also manipulations? – Raphael Feb 4 '13 at 12:19
• @ChopraJack You can use 2 arrays of size $N$, one for cols and the other for rows, in which you store the number of 0's in each col/row. Initially, the array values are set to $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likwise for the i'th row). – mrk Feb 4 '13 at 14:24
• @saadtaame Turn to an answer? – Yuval Filmus Feb 4 '13 at 15:45
• I agreee with @Raphael, OP should state if settings are to be considered for performance or not. If they aren't, saadtaame's solution is as good as it could get. If not... – vonbrand Feb 4 '13 at 18:55
• @Raphael You can't! You still use the grid of zeros and ones. My argument concerns running time. – mrk Feb 5 '13 at 11:15

My solution uses 2 arrays (R and C) to store the zero-counts and a 1D array (Grid) to represent the grid of zeros and ones as a sequence of numbers. All 3 arrays are of size $N$. Queries take constant time (you return the value in the i'th col/row). An update operation takes linear time in $N$ because you have to set the i'th col to $N$ or 0 and update all of the rows (likewise for the i'th row). Here is a Python implementation and a test case (yours):

N = 3
R = []
C = []
Grid = []

for k in range(N):
R.append(N)
C.append(N)
Grid.append(0)

def qr(k):
print R[k - 1]

def qc(k):
print C[k - 1]

def r(i, k):
R[i - 1] = (1 - k) * N
for l in range(N):
bit = ((Grid[i - 1] & (1 << l) >> l)
if bit != k:
if k == 0:
C[l] = C[l] + 1
else:
C[l] = C[l] - 1
Grid[i - 1] = Grid[i - 1] | (k << l)

def c(i, k):
C[i - 1] = (1 - k) * N
for l in range(N):
bit = ((Grid[l] & (1 << (i - 1))) >> (i - 1))
if bit != k:
if k == 0:
R[l] = R[l] + 1
else:
R[l] = R[l] - 1
Grid[l] = Grid[l] | (k << (i - 1))

qr(1)
c(1, 1)
qr(1)
qc(1)
r(1, 0)
qc(1)


You have to complete this with code that parses the input file and interprets the commands.

• An update operation takes linear time in N.In worst case , updates can be as big as 6 * 10^5. So N*6 * 10^5 is too slow.The Timelimit is just 0.55 Secs – Chopra Jack Feb 5 '13 at 20:18
• @ChopraJack True. – mrk Feb 6 '13 at 0:50