I can't think of a good algorithm
<p>There is a magic board. The magic board has N*N cells: N rows and N columns. Every cell contains one integer, which is 0 initially. Let the rows and the columns be numbered from 1 to N.</p>

<p>There are 2 types of operations can be applied to the magic board:</p>

<p>•RowSet i x: it means that all integers in the cells on row i have been changed to x after this operation.</p>

<p>•ColSet i x: it means that all integers in the cells on column i have been changed to x after this operation.</p>

<p>And your friend sometimes has an interest in the total number of the integers 0s on some row or column:</p>

<p>•RowQuery i: it means that you should answer the total number of 0s on row i.</p>

<p>•ColQuery i: it means that you should answer the total number of 0s on column i.</p>

<p>Input</p>

<p>The first line of input contains 2 space-separated integers N and Q. They indicate the size of the magic board, and the total number of operations and queries from the friend.</p>

<p>Then each of the next Q lines contains an operation or a query by the format mentioned above.</p>

<p>Output</p>

<p>For each query, output the answer of the query.</p>

<p>Constraints</p>

<p>1 ≤ N, Q ≤ 500000 (5 * 105)</p>

<p>1 ≤ i ≤ N</p>

<p>x ∈ {0, 1} (That is, x = 0 or 1)</p>

<p>Sample Input:</p>

<p>3 6</p>

<p>RowQuery 1</p>

<p>ColSet 1 1</p>

<p>RowQuery 1</p>

<p>ColQuery 1</p>

<p>RowSet 1 0</p>

<p>ColQuery 1</p>

<p>Output:
3</p>

<p>2</p>

<p>0</p>

<p>1</p>

<p>How to go about it? The time constraint is 0.6 seconds and therefore the naïve algorithm of marking out the operations on a 2D array, wont work.</p>
