问题背景

P5268 [SNOI2017] 一个简单的询问 前置题。

题目链接：https://www.luogu.com.cn/problem/P5268

题目描述

给定一个长度为 $n$ 的数列 $a$ 和一个长度为 $m$ 的数列 $b$。

定义函数 $count(a, x)$ 表示数列 $a$ 中数值等于 $x$ 的数的个数。

同时，本题中，我们定义函数 $f(a, b)$ 为：

$f(a, b) = \sum\limits_{x = 0}^{\infty} count(a, x) \times count(b, x)$

你需要先求出 $f(a, b)$ 的值。

然后有 $q$ 次操作，操作分为如下两种类型：

• $\mathtt{1\ p\ x}$：将 $a_p$ 的值修改为 $x$；
• $\mathtt{2\ p\ x}$：将 $b_p$ 的值修改为 $x$。

每次操作后你都要重新计算并输出 $f(a, b)$ 的值。

输入格式

第一行，三个整数 $n, m, q$。

第二行，$n$ 个整数 $a_1, a_2, \ldots, a_n$。

第三行，$m$ 个整数 $b_1, b_2, \ldots, b_m$。

接下来 $q$ 行，每行包含一个操作（$\mathtt{1\ p\ x}$ 或 $\mathtt{2\ p\ x}$）。

输出格式

输出共 $q + 1$ 行，每行包含一个整数。

其中第一个整数表示初始时的 $f(a, b)$ 的值。

接下来 $q$ 行，每行对应一次操作后的 $f(a, b)$ 的值。

注：本题中，操作具有持续性，即后一次操作是在前一次操作的基础上继续进行的修改。

样例

5 8 4
1 1 1 2 2
1 1 1 1 2 2 2 2
1 5 3
2 7 4
1 1 3
1 5 4

20
16
15
11
12

说明/提示

数据规模与约定

• 对于 $20\%$ 的数据，$n,m,q,a_i,b_i,x \le 20$
• 对于 $50\%$ 的数据，$n,m,q,a_i,b_i,x \le 2000$
• 对于 $100\%$ 的数据，$1 \le n,m,q \le 2 \times 10^5$，$1 \le a_i, b_i \le n$，且
  • 对于 $\mathtt{1\ p\ x}$ 操作，$1 \le p \le n, 1 \le x \le 2 \times 10^5$
  • 对于 $\mathtt{2\ p\ x}$ 操作，$1 \le p \le m, 1 \le x \le 2 \times 10^5$