← 返回题目列表

Codeforces · 1403/A

A. 强大力量药水

中文机器翻译题面 查看原题

很久以前,在萨满之地,所有人都生活在通天魔豆之上。每个萨满都有一个唯一的识别号码 $$$i$$$,介于 $$$0$$$ 和 $$$N-1$$$ 之间,以及一个海拔值 $$$H_i$$$,代表他居住在地面以上的高度。两个高度之间的距离是它们的差的绝对值。

所有萨满都和平地生活在一起,直到其中一个萨满偷走了举世闻名的强力药水的配方。为了掩盖他/她的踪迹,小偷对这片土地施加了诅咒:大多数居民无法再相互信任......

尽管情况非常困难,善良调查员团还是获得了有关诅咒的以下信息:

- 当诅咒首次生效时,每个人都不再相互信任。
- 诅咒不稳定:每天结束时(恰好在午夜),一对萨满会开始或停止相互信任。
- 不幸的是,每个萨满在任何给定时间最多只能信任 $$$D$$$ 个其他人。

他们相信小偷已经向邪恶萨满低声讲述了这个公式。为了避免被发现,他们俩都拜访了他们(各自)信任的朋友之一的家。在拜访期间,小偷透过窗户向邪恶萨满低声讲述了配方。 (注:这位值得信赖的朋友当时并不一定在家。事实上,他们甚至有可能拜访了对方的房子——萨满很奇怪。)

幸运的是,低语只能传播很短的距离,因此凤凰社知道拜访的两个值得信赖的朋友(小偷和邪恶萨满)必须住得很近。

他们请求您帮助他们进行调查。他们想测试一下自己的怀疑:如果小偷是$$$x$$$,邪恶萨满是$$$y$$$,而公式是在$$$v$$$那天悄悄流传的呢?耳语公式必须传播的最小距离是多少?也就是说,一些萨满 $$$x'$$$ 和 $$$y'$$$ 的公寓之间的最小距离是多少(即 $$$\min\left(\left|H_{x'} - H_{y'}\right|\right)$$$),使得 $$$x'$$$ 是 $$$x$$$ 的可信朋友,$$$y'$$$ 是 $$$y$$$ 的可信朋友当天$$$v$$$?

他们将与您分享所有信息,然后问您一些问题。在收到下一个问题之前,您需要立即回答每个问题。

互动

交互将以包含 $$$N$$$、$$$D$$$、$$$U$$$ 和 $$$Q$$$ $$$(2 \leq N \leq 100000$$$, $$$1 \leq D \leq 500$$$, $$$0 \leq U \leq 200000$$$, $$$1 \leq Q \leq 50000)$$$ – 萨满的数量、萨满在任何给定点可以拥有的最大可信任朋友数量、天数和问题数量。

下一行 $$$N$$$ 后面是空格分隔的整数,第 $$$i$$$th $$$(1\leq i \leq N)$$$ 为 $$$H_{i-1}$$$ $$$(0\leq H_{i-1} \leq 10^9)$$$,萨满的高度 $$$i-1$$$。

在接下来的 $$$U$$$ 行中,每行将有两个整数,分别位于第 $$$i$$$ ($$$1 \leq i \leq U$$$) $$$A_i$$$ 和 $$$B_i$$$ $$$(0 \leq A_i, B_i < N$$$ 和 $$$A_i \neq B_i)$$$,表示一对萨满在一天结束时开始或停止信任彼此$$$i-1$$$。也就是说,如果 $$$A_i$$$ 和 $$$B_i$$$ 在 $$$i-1$$$ 天彼此信任,那么他们在 $$$i$$$ 天就不信任对方,反之亦然。读取所有这些整数。

交互者现在会问你 $$$Q$$$ 问题,因此以下交互应该发生 $$$Q$$$ 次:

1. 读取描述当前查询的 $$$3$$$ 整数:$$$x,y$$$ 和 $$$v$$$ ($$$x \neq y$$$, $$$0 \leq x,y < N$$$ 和 $$$0 \leq v \leq U$$$),其中 $$$x$$$ 是可疑的 Thief,$$$y$$$ 是可疑的邪恶的萨满,$$$v$$$ 是可疑的一天..
2. 然后在一行上打印此查询的答案,即您应该打印耳语公式从 $$$x$$$ 的某个值得信赖的朋友 $$$x'$$$ 到 $$$y$$$ 的值得信赖的朋友 $$$y'$$$ 的最小距离。 如果有人同时信任 $$$x$$$ 和 $$$y$$$ (即 $$$x'=y'$$$),您应该打印 $$$0$$$。 如果 $$$x$$$ 或 $$$y$$$ 没有值得信赖的朋友,则打印 $$$10^9$$$。

打印每一行后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

示例

输入 #1

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

输出 #1

26
0
1000000000
14

注意

评分:
$$$ \begin{array}{|c|c|c|} \hline \text{子任务} & \text{点} & \text{约束} \\ \hline 1 & 0 & \text{样本}\\ \hline 2 & 17 & Q,U \leq 1000 \\ \hline 3 & 14 & v=U \: \text{对于所有问题} \\ \hline 4 & 18 & H_i \in \left\{0,1\right\} \: \text{对于所有萨满} \: i \\ \hline 5 & 21 & U,N \leq 10000\\ \hline 6 & 30 & \text{无附加限制}\\ \hline \end{数组} $$$

查询示例:

友谊的演变: