33OJ
登录 注册

#D1103. 交叠涂色

交叠涂色

题目描述

小 B 有一块 NN 行 MM 列的展板,他准备进行 KK 次涂色。

每次涂色时,小 B 可以选择一整行或一整列涂满。为了保证画面干净,每一行和每一列最多只会被涂一次。

如果一个格子只被行涂过或只被列涂过,它是浅黄色;如果一个格子既被它所在的行涂过,又被它所在的列涂过,它就会变成深黄色。没有被涂过的格子保持原来的颜色,不计入深黄色。

现在给出小 B 的全部涂色操作,请你计算展板上最终有多少个深黄色格子。

输入格式

第一行三个整数 N,M,KN,M,K。

接下来 KK 行,每行包含一个字符 opop 和一个整数 xx:

  • 若 opop 为 r,表示涂第 xx 行;
  • 若 opop 为 c,表示涂第 xx 列。

输出格式

输出一行一个整数,表示深黄色格子的数量。

样例

4 3 5
r 1
r 2
c 1
r 3
c 2
6
1 1 2
r 1
c 1
1
2 2 1
r 1
0

样例解释

样例 1 中,被涂过的行是第 1,2,31,2,3 行,被涂过的列是第 1,21,2 列,共有 3×2=63\times2=6 个交点,因此深黄色格子有 66 个。

样例 2 中,唯一的格子同时被第 11 行和第 11 列涂过,所以答案是 11。

样例 3 中,只涂了第 11 行,没有任何一列被涂过,因此没有深黄色格子。

数据范围与约定

子任务 分值 限制
11 3030 1≤N,M≤10001 \le N,M \le 1000,1≤K≤10001 \le K \le 1000
22 7070 无额外限制

对于 100%100\% 的数据,保证 1≤N,M≤1061 \le N,M \le 10^6,1≤K≤min⁡(N+M,106)1 \le K \le \min(N+M,10^6);每个 opop 为 r 或 c,且 xx 在对应范围内;每一行、每一列最多被涂一次。