# 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? Commented Feb 4, 2013 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
Commented Feb 4, 2013 at 14:24
• @saadtaame Turn to an answer? Commented Feb 4, 2013 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... Commented Feb 4, 2013 at 18:55
• @Raphael You can't! You still use the grid of zeros and ones. My argument concerns running time.
– mrk
Commented Feb 5, 2013 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 Commented Feb 5, 2013 at 20:18
• @ChopraJack True.
– mrk
Commented Feb 6, 2013 at 0:50