$N \times N$ 枚のタイルを $K$ 色で塗ることを考えます。
このとき、一行または一列を色 $c$ で塗ることを $Q$ 回行います。
最初は全てが色 $1$ で塗られているものとします。
作業後の各色の枚数を求めてください。
・$1 \le N \le 10^{5}$
・$1 \le K \le 10^{5}$
・$1 \le Q \le 10^{5}$
writer の解説がかなりあっさりで、解けなかった人間にはしんどいだろうと思い、書いています。
---
前に塗られた部分は後から塗られた方で上書きされるので、クエリを逆から見るようにする。
逆から見るようにしたとき、行を塗ったときは、それ以降（実際には過去に起こったことだが）は列に関しては塗ることができる箇所は $1$ 減り、
同様に列を塗ったときは、それ以降は行に関しては塗ることができる箇所は $1$ 減る。
これを表現するカウンタと、各行あるいは各列が既に塗られているかという配列、および色ごとに塗られた枚数を数える配列があれば良い。
全部を処理し終わった後に $N \times N$ 枚に足りない場合、その分を色 $1$ で補うのを忘れないように。
#!/usr/bin/python2
# -*- coding: utf-8 -*-
# †
N, K, Q = map(int, raw_input().split())
seenR = [False] * N # 既に行が塗られているかどうか
seenC = [False] * N # 既に列 〃
r_inc, c_inc = N, N # 一回のクエリで行, 列を塗ることができる枚数
cnt = [0] * K # 色ごとの塗られた枚数
Qs = []
for _ in xrange(Q):
a, b, c = raw_input().split()
b = int(b) - 1
c = int(c) - 1
Qs.append([a, b, c])
Qs.reverse()
for a, b, c in Qs:
if a == 'R':
if not seenR[b]:
seenR[b] = True
cnt[c] += r_inc
c_inc -= 1
else:
if not seenC[b]:
seenC[b] = True
cnt[c] += c_inc
r_inc -= 1
cnt[0] = N * N - sum(cnt[1:])
print '\n'.join(map(str, cnt))
(ΦωΦ)＜おしまい