#3351. 「CEOI2020」权力药水

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

题目描述

题目译自 CEOI 2020 Day2 T1「The Potion of Great Power

很久以前,在萨满之岛上,所有人都住在一个如天一样高的豆茎上。每位萨满都有一个独一无二的编号,编号的范围在 0 N-1 之间。第 i 位萨满居住的高度用 H_i 表示。定义两位萨满间的距离为其高度差的绝对值。

所有的萨满之间本来和谐共处,直到一天权力药水的配方被盗。为了掩盖他的行径,那位小偷给整座岛施加了诅咒,大多数居民不再彼此信任了。

虽然情况非常复杂,但是经过调查,某组织还是获得了如下信息:

  • 诅咒刚生效时,所有的萨满停止彼此信任。
  • 诅咒本身是不稳定的,在每天将要结束时(准确来说是午夜),某一对萨满将会建立信任或是停止信任。
  • 不幸地是,一位萨满在任意时刻最多信任 D 位萨满。

该组织还重建了萨满间的信任变化日志,该日志记录了在每个半夜,哪对萨满的信任关系发生了变化(从不信任到信任,或是从信任到不信任)。

该组织的成员相信,小偷还向一位邪恶的萨满通过隔空传话的方式泄露了配方。为了避免被发现,他们俩都各自拜访了一位信任的萨满的家,在拜访的过程中,小偷透过窗户向邪恶的萨满泄露配方。需要注意的是,那位信任的朋友当时不必在家中,事实上,两位萨满可能互相前往对方的家。毕竟萨满都很奇怪。

幸运的是,因为萨满们的听力有限,声音并不能传出太远,这意味着两位朋友(小偷的朋友和邪恶的萨满的朋友)之间的距离必须尽可能近。

现在该组织决定让你来协助调查。他们想要验证自己的猜想:当小偷为 x ,邪恶的萨满为 y ,泄露配方的日子为 v 时,隔空传话的声音需要行进的最小值是多少?也即,你需要在第 v 天时,在 x 信任的所有萨满中找到一位萨满 x' ,在 y 信任的所有萨满中找到一位萨满 y' ,使 x' y' 间的距离最小。

你已经获得了求出答案所需的所有信息,但你需要实时回答每一组询问。

输入格式

输入第一行包含四个整数 N,D,U,Q ,分别代表萨满的数量,一位萨满最多信任的朋友数,日志包含的天数,以及需要回答的询问数。

下一行包含 N 个整数,两两间以一个空格隔开。其中第 i 个整数代表第 i-1 只萨满居住的高度 H_{i-1}

接下来 U 行,第 i 行包含两个整数 A_i,B_i ,代表编号为 A_i B_i 的萨满在第 i-1 天结束的时候,他们之间的信任状态发生了变化。即,如果 A_i B_i 在第 i-1 天互相信任,则他们自第 i 天起不再互相信任,反之同理。

接下来你需要回答 Q 组询问。询问必须实时回答,即你必须回答完一组询问后才能读入下一组询问。

每组询问包含三个整数 x,y,v ,代表小偷为 x ,邪恶的萨满为 y ,泄露配方的日子为第 v 天。


或者也可以利用函数交互,引用 potion.h 头文件并实现以下三个函数:

  • \texttt{void init(int N, int D, int H[])}
    • N,D 的意义同题目描述, \texttt{H[i]} 表示第 i 位萨满的高度。
  • \texttt{void curseChanges(int U, int A[], int B[])}
    • U 是天数, A,B 是大小为 U 的数组。
  • \texttt{int question(int X, int Y, int V)}
    • 代表小偷为 X ,邪恶的萨满为 Y ,泄露配方的日子为第 V 天,此函数返回题目所求答案。

输出格式

对于每组询问,你需要在第 v 天时,在 x 信任的所有萨满中找到一位萨满 x' ,在 y 信任的所有萨满中找到一位萨满 y' ,使 x' y' 间的距离最小,并输出这个最小值。

特别地,

  • 若存在一位萨满同时被 x y 信任,输出 0
  • x y 在第 v 天无信任的朋友,输出 1000000000 10^9 )。

在回答完一组询问后,你需要立刻刷新缓冲区。

对于 C++ 选手,可以通过 fflush(stdout);cout.flush() 来刷新缓冲区。


若采用函数交互,则你不应输出任何内容到标准输出。

样例

样例输入

6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11

样例输出

26
0
1000000000
14

样例解释

下面是询问的情况:

potion1.png

下面是每一天时信任关系的变化情况:

potion2.png

数据范围与提示

所有数据均满足: 2 \leq N \leq 10^5 1 \leq D \leq 500 0 \leq U \leq 2 \times 10^5 1 \leq Q \leq 5 \times 10^4

各子任务的约束条件如下:

子任务编号 分值 约束
1 0 样例
2 17 Q,U \leq 10^3
3 14 所有询问均满足 v=U
4 18 \forall i \in [0,N) H_i\in \{0,1\}
5 21 U,N \leq 10^4
6 30 无特殊约束