【IOI2018】排座位 - 题目 - Universal Online Judge

你要在一个长方形大厅里举办国际编程比赛，该大厅共有 $H W$ 个座位（ $H$ 行 $W$ 列）。行的编号是从 $0$ 到 $H - 1$ ，列的编号是从 $0$ 到 $W - 1$ 。位于 $r$ 行 $c$ 列的座位用 $(r, c)$ 表示。一共邀请了 $H W$ 位参赛者，编号是从 $0$ 到 $H W - 1$ 。你制定好了一个座位表，第 $i$ （ $0 \leq i \leq H W - 1$ ）个参赛者被安排到座位 $(R_{i}, C_{i})$ 。座位表中参赛者和座位是一一对应的。

大厅中一个座位集合 $S$ 被称为是长方形的，如果存在整数 $r_{1}, r_{2}, c_{1}$ 和 $c_{2}$ 满足下列条件：

$0 \leq r_{1} \leq r_{2} \leq H - 1$ 。
$0 \leq c_{1} \leq c_{2} \leq W - 1$ 。
$S$ 正好是所有满足 $r_{1} \leq r \leq r_{2}$ 和 $c_{1} \leq c \leq c_{2}$ 的座位 $(r, c)$ 的集合。

如果一个长方形座位集合包含 $k$ （ $1 \leq k \leq H W$ ）个座位，并且被分配到这个集合的参赛者的编号恰好是从 $0$ 到 $k - 1$ ，那么该集合是美妙的。一个座位表的美妙度定义为这个表中美妙的长方形座位集合的个数。

在准备好座位表后，你会收到一些交换两个参赛者座位的请求。具体来说，有 $Q$ 个这样的请求，按时间顺序编号为 $0$ 到 $Q - 1$ 。第 $j$ （ $0 \leq j \leq Q - 1$ ）个请求希望交换参赛者 $A_{j}$ 和 $B_{j}$ 的座位。你立即接受每个请求并更新座位表。每次更新后，你的目标是计算当前座位表的美妙度。

实现细节

你应该实现下列过程和函数：

give_initial_chart(int H, int W, int[] R, int[] C)

H, W：行数和列数
R, C：两个长度为 $H W$ 的数组，代表初始的座位表
这个过程只被调用一次，而且是在 swap_seats 的任何调用之前。

int swap_seats(int a, int b)

该函数用来处理一次交换座位的请求
a, b：需要交换座位的参赛者
该函数被调用 $Q$ 次
该函数应返回交换座位后座位表的美妙度

例子

令 $H = 2$ ， $W = 3$ ， $R = [0, 1, 1, 0, 0, 1]$ ， $C = [0, 0, 1, 1, 2, 2]$ ，和 $Q = 2$ 。

评测程序先调用 give_initial_chart(2, 3, [0, 1, 1, 0, 0, 1], [0, 0, 1, 1, 2, 2])。

最初，座位表如下：

$\begin{matrix} 0 & 3 & 4 \\ 1 & 2 & 5 \end{matrix}$

假设评测程序调用 swap_seats(0, 5)。在这个编号为 $0$ 的请求完成后，座位表变成：

$\begin{matrix} 5 & 3 & 4 \\ 1 & 2 & 0 \end{matrix}$

对应参赛者集合 ${0}, {0, 1, 2}$ 和 ${0, 1, 2, 3, 4, 5}$ 的三个座位集合都是长方形和美妙的。所以，该座位表的美妙度为 $3$ ，swap_seats 应该返回 $3$ 。

假设评测程序再次调用 swap_seats(0, 5)。在这个编号为 $1$ 的请求完成后，座位表回到初始状态。对应参赛者集合 ${0}, {0, 1}, {0, 1, 2, 3}$ 和 ${0, 1, 2, 3, 4, 5}$ 的四个座位集合都是长方形和美妙的。所以，该表的美妙度为 $4$ ，swap_seats 应该返回 $4$ 。

在样例数据下载中的文件ex_seats1.in和ex_seats1.out对应于上述例子。此外，样例数据包中还有一些其他的输入输出例子。

限制条件

$1 \leq H$
$1 \leq W$
$H W \leq 1 000 000$
$0 \leq R_{i} \leq H - 1$ （ $0 \leq i \leq H W - 1$ ）
$0 \leq C_{i} \leq W - 1$ （ $0 \leq i \leq H W - 1$ ）
$(R_{i}, C_{i}) \neq (R_{j}, C_{j})$ （ $0 \leq i < j \leq H W - 1$ ）
$1 \leq Q \leq 50 000$
对于 swap_seats 的所有调用， $0 \leq a \leq H W - 1$
对于 swap_seats 的所有调用， $0 \leq b \leq H W - 1$
对于 swap_seats 的所有调用， $a \neq b$

子任务

（5分） $H W \leq 100$ ， $Q \leq 5 000$
（6分） $H W \leq 10 000$ ， $Q \leq 5 000$
（20分） $H \leq 1 000$ ， $W \leq 1 000$ ， $Q \leq 5 000$
（6分）对于 swap_seats 的所有调用， $Q \leq 5 000$ ， $| a - b | \leq 10 000$
（33分） $H = 1$
（30分）无附加限制条件

评测程序示例

评测程序示例按照以下格式读入输入

第 $1$ 行： $H W Q$
第 $2 + i$ 行（ $0 \leq i \leq H W - 1$ ） : $R_{i} C_{i}$
第 $2 + H W + j$ 行（ $0 \leq j \leq Q - 1$ ）： $A_{j} B_{j}$

这里 $A_{j}$ 和 $B_{j}$ 是调用 swap_seats 处理请求时的参数。

评测程序示例按照以下格式打印你的答案：

第 $1 + j$ 行（ $0 \leq j \leq Q - 1$ ）：swap_seats 对于请求 $j$ 的返回值

约定及限制

对于所支持的各种编程语言，下面列出了对应的数据类型。对于数据类型的细节等，参见实现示例。

语言	$int$	$int64$	$int[]$	数组 $a$ 的长度	$string$
$C++$	$int$	$long long$	$std::vector<int>$	$a.size()$	$std::string$

时间限制： $3 s$

空间限制： $268 MB$

下载

样例数据下载

Universal Online Judge

UOJ

#406. 【IOI2018】排座位

实现细节

例子

限制条件

子任务

评测程序示例

约定及限制

下载