UOJ Logo Universal Online Judge

UOJ

#406. 【IOI2018】排座位

统计

你要在一个长方形大厅里举办国际编程比赛,该大厅共有 $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])

最初,座位表如下:

\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.inex_seats1.out对应于上述例子。此外,样例数据包中还有一些其他的输入输出例子。

限制条件

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

约定及限制

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

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

时间限制:$3\texttt{s}$

空间限制:$268\texttt{MB}$

下载

样例数据下载