#2864. 「IOI2018」排座位

内存限制:268 MiB 时间限制:3000 ms 题目类型:交互
上传者: spj

题目描述

你要在一个长方形大厅里举办国际编程比赛,该大厅共有 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 的座位。你立即接受每个请求并更新座位表。每次更新后,你的目标是计算当前座位表的美妙度。

输入格式

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

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
  • 该函数应返回交换座位后座位表的美妙度

样例

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])

最初,座位表如下:

0 3 4
1 2 5

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

5 3 4
1 2 0

对应参赛者集合 \{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

在压缩附件包里的文件 sample-01-in.txtsample-01-out.txt 对应于上述例子。此外,压缩附件包中还有一些其他的输入输出例子。

数据范围与提示

  • 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 的返回值