0 and 1 Queries in tables of N*N cells

Question

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.

Our task is to answer Alice Query.

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.

Answer 1

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.