会议 - 题目

1918年捷克斯洛伐克建国之初，政治局势原则上是有利的，但极其混乱。大多数高级官员在国外承担着额外职责，只能在有限的时间内参与政府工作。幸运的是，总统办公室成功编制了一份日程表，其中每位官员都被分配了一个唯一的、他们必定会在布拉格出现的时间区间。

捷克斯洛伐克陆军部长米兰·拉斯蒂斯拉夫·什特凡尼克（Milan Rastislav Štefánik）同时也是一位天文学家，凭借其科学背景在内阁成员中脱颖而出。这使他能够寻求更系统的方法来组织政府的日程，以便内阁能够亲自会见尽可能多的官员。

日程表跨越了很长的一天数序列，索引为 $1, 2, 3, 4, \dots, 100000$。

对于每位官员，记录了他们在布拉格出现的第一天和最后一天。政府被分配了固定数量的会议天数。这些天数可以自由选择，不一定连续，与官员的会议将在这些天内举行。

什特凡尼克首先在日程表中随机选择并标记了规定数量的会议天数。之后，他确定了无法参会的官员数量，即错过了所有会议天数的官员人数。

接下来，他会选择已选定的会议天数之一，并将其移动到另一个日期，确保新日期与任何其他已选定的天数不重叠。每次调整后，他都会再次记录无法参会的官员数量。他多次重复此操作。在重复的过程中，任何特定会议天数的日期都可以被移动多次，或者根本不移动。

为了计算这些数量，什特凡尼克依赖于他从阿尔卑斯山勃朗峰的观测中带回的一个相当不完美的机械计算器。

今天，我们可以使用高效的计算机程序来重复部长的这一过程。

第一行包含三个整数 $N, C, Q$（$1 \le N \le 10^5$，$1 \le C \le 10^5$，$1 \le Q \le 10^5$），分别表示官员人数、规定的会议天数和询问次数。每个询问代表将一个计划中的会议天数从一个日期移动到另一个日期。

接下来 $N$ 行，每行代表一个区间 $[x, y]$，表示一位官员在布拉格的时间。其中 $x$ 和 $y$ 是该区间第一天和最后一天的日程索引。保证 $x \le y$ 且 $1 \le x, y \le 10^5$。

接下来一行包含 $C$ 个互不相同的整数 $C_i$（$1 \le C_i \le 10^5$），描述部长最初选择的会议天数。

接下来 $Q$ 行，每行描述一个询问，包含两个整数 $f$ 和 $t$（$1 \le f, t \le 10^5$）。这里 $f$ 和 $t$ 代表将一个会议天数从索引 $f$ 移动到索引 $t$。保证在询问时，索引 $f$ 处确实有一个会议天数，而索引 $t$ 处没有会议天数。

首先，输出单行，表示在最初选择会议天数后，无法参会的官员数量。

接下来，对于每个询问，输出单行，表示在进行该询问对应的日程调整后，无法参会的官员数量。

总共，输出必须包含 $Q + 1$ 行。

QOJ.ac