LibreOJ

2864 「IOI2018」排座位

内存限制：268 MB 时间限制：3000 ms

题目描述

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

大厅中一个座位集合 $S$ 被称为是长方形的，如果存在整数 $r_1,r_2,c_1$ 和 $c_2$ 满足下列条件： * $0\le r_1\le r_2\le H-1$。 * $0\le c_1\le c_2\le W-1$。 * $S$ 正好是所有满足 $r_1\le r\le r_2$ 和 $c_1\le c\le c_2$ 的座位 $(r,c)$ 的集合。

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

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

交互过程

在程序开始，你应该引入 seats.h 头文件。

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

give_initial_chart(int H, int W, int[] R, int[] C)
  • H, W：行数和列数
  • R, C：两个长度为 $HW$ 的数组，代表初始的座位表
  • 这个过程只被调用一次，而且是在 swap_seats 的任何调用之前。
int swap_seats(int a, int b)
  • 该函数用来处理一次交换座位的请求
  • a, b：需要交换座位的参赛者
  • 该函数被调用 $Q$ 次
  • 该函数应返回交换座位后座位表的美妙度

数据范围与提示

  • $1\le H$
  • $1\le W$
  • $HW\le 1\ 000\ 000$
  • $0\le R_i\le H-1$（$0\le i\le HW-1$）
  • $0\le C_i\le W-1$（$0\le i\le HW-1$）
  • $(R_i,C_i)\ne(R_j,C_j)$（$0\le i<j\le HW-1$）
  • $1\le Q\le 50\ 000$
  • 对于 swap_seats 的所有调用，$0\le a\le HW-1$
  • 对于 swap_seats 的所有调用，$0\le b\le HW-1$
  • 对于 swap_seats 的所有调用，$a\ne b$

子任务

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

评测程序示例

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

  • 第 $1$ 行：$H\ W\ Q$
  • 第 $2+i$ 行（$0\le i\le HW-1$） : $R_i\ C_i$
  • 第 $2+HW+j$ 行（$0\le j\le Q-1$）：$A_j\ B_j$

这里 $A_j$ 和 $B_j$ 是调用 swap_seats 处理请求时的参数。

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

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