NOI2024前训练-一些有趣的国内外比赛资源库 #2

QOJ #4399. [CEOI2022] Abracadabra

Tin 是一位著名的魔术师，他的一个经典魔术与洗牌有关。
Tin 会准备一套牌，总共 \(n\) 张（保证 \(n\) 为偶数），各编号为 \(1\sim n\)，一开始的时候牌是乱的且倒扣在桌子上。紧接着他开始表演洗牌，在洗牌的任意时刻，观众都可以向 Tin 询问从底往上数第 \(t\) 张牌是什么牌，很显然 Tin 一定会立即回答出正确答案。
事实上，Tin 采用如下方式来完成这个魔术，首先他记下了一开始的 \(n\) 张牌的顺序，接着采用如下技巧洗牌：
\(1.\) 拿起自顶向下 \(\dfrac{n}{2}\) 张牌放在右手，自底向上 \(\dfrac{n}{2}\) 张牌放在左手，牌的正面对着桌子。
\(2.\) 借助他的记忆，将左右手最底下的牌进行比较，将编号较小的那张牌放下，重复这个操作直到左右手一边为空。
\(3.\) 将还有牌的那只手上的所有牌放下。
请你写一个程序模拟 Tin 的魔术。
对于全部数据，满足 \(1\le N\le 2\times 10^5\)，\(N\) 为偶数，\(1\le Q\le 10^6\)，\(0\le t\le 10^9\)，\(p\) 为 \(1\sim n\) 的排列，\(1\le i\le N\)。

QOJ #4401. [CEOI2022] Prize

Tomislav 在睡梦中想到了一个问题：给定两棵大小为 \(N\) 的树，树上的节点按 \(1\sim N\) 分别编号，树则分别编号为树 \(1\)，树 \(2\)，树有边权，但是边权被隐藏了起来。
Tomislav 需要向交互库提供一个大小为 \(K\) 的编号的子集 \(S\)，在选择了这个集合后，小 C 可以问 \(Q\) 个格式为 \((a,b)\) 的问题，定义 \(d_t(x,y)\) 表示树 \(t\) 上节点 \(x\) 与节点 \(y\) 的距离，\(l_t\) 表示树 \(t\) 上节点 \(a\) 与节点 \(b\) 的 LCA，交互库会依次回答 \(d_1(l_1,a),d_1(l_1,b),d_2(l_2,a),d_2(l_2,b)\)。
紧接着交互库会询问 \(T\) 个格式为 \((p,q)\) 的问题，其中 \(p,q\in S\)，Tomislav 必须依次回答 \(d_1(p,q)\) 和 \(d_2(p,q)\)。
可怜的 Tomislav 并不会做，请你帮帮他。
对于全部数据，保证所有边权为正整数且不超过 \(2000\)，\(2\le K\le 10^5\)，\(1\le T\le \min(K^2,10^5)\)。

QOJ #4402. [CEOI2022] Drawing

给定平面上的 \(N\) 个点，和一棵大小为 \(N\) 的树 \(T\)，保证这棵树上每个点的度数至多为 \(3\)，树上节点按 \(1\sim N\) 编号。
你需要为平面上的点使用 \(1\sim N\) 的编号重编号之后，对于所有树上的边 \(e=(u,v)\)，将平面上的点 \(u\) 和平面上的点 \(v\) 用线段连接后，任意两条线段除了在端点上相交没有其他的相交点。
试构造一组方案，保证一定有解。
对于所有数据，保证 \(0\le x,y\le 10^9\)。

QOJ #4404. [CEOI2022] Parking

Valerija 在一家饭店的停车场工作，她负责礼貌地接待重要的客人，保管他们的车钥匙并帮助他们停车。
一个晚上，她发现她管理的停车场中恰好有 \(2N\) 辆车，它们共有 \(N\) 种不同的颜色，每种颜色恰有两辆车。我们将颜色按 \(1\) 到 \(N\) 编号。
停车场共有 \(M\) 个车位，按 \(1\) 到 \(M\) 编号，每一个车位可以停下两辆车，一个车位只有一个入口，我们称靠近入口的为「顶上的车」，远离入口的为「底下的车」，一辆车可以从入口开出当且仅当没有车挡着它。Valerija 在停车的时候，保证每个车位要么空，要么停满两辆车，要么只有一辆底下的车。
这张图描述的是第一个样例，同时呈现了唯一的第一次驾驶。
Valerija 想要重新停放车使得每一对相同颜色的车都在一个车位里。我们并不关心车位对应什么颜色以及哪辆车在顶上哪辆车在底下。Valerija 将执行如下操作：
\(•\) 驾驶一辆可以驶出车位的车，将车开到另一个车位，满足以下两个条件的任一条件即可：
\(※\) 这个车位是空的，并把车停在底下的车位；
\(※\) 这个车位有且只有一辆与当前驾驶的车颜色相同的车。
Valerija 想知道最少的操作次数与操作方案，请你解决这个问题。
对于全部数据，\(1\le N\le M\le 2\times 10^5\)。

QOJ #6335. [JOISC 2023 Day 2] Belt Conveyor

JOI 公司的工厂里有 \(N\) 张桌子，编号为 \(0\) 到 \(N-1\)。在工厂里，有 \(N-1\) 条传送带，编号为 \(0\) 到 \(N-2\)。传送带 \(i\ (0\le i\le N-2)\) 连接桌子 \(A_i\) 和 \(B_i\)。传送带会从一个桌子向另一个桌子传送产品。然而，我们不知道传送的方向。如果我们忽略传送带的方向，每对桌子被一些传送带所连接。
IOI 君是工厂的厂长。因为它忘了每个传送带的传送方向，他将按顺序进行如下操作几次：
\(1.\) 他选择一些传送带，并反转这些传送带的传送方向。
\(2.\) 他选择一些桌子，每个桌子放置一个产品。
\(3.\) 对于每个他放了产品的桌子，会同时发生以下情况中的一个：
\(•\) 如果没有传送带从这个桌子出发，什么都不会发生。
\(•\) 如果有传送带从这个桌子出发，在这个桌子上的产品会被一个这样的传送带传送。这个产品会停在这条传送带的终点。这个产品不会再移动。
\(4.\) IOI 君会确认每个桌子上是否有一个及以上产品。如果桌子上有产品，IOI 君会收走全部产品。
\(5.\) 对于在第 \(1\) 步操作中反向的传送带，IOI 君会回退它的方向。之后所有传送带的方向的最初的方向相同。
IOI 君希望通过最多 \(30\) 次操作确定每条传送带最初的方向。
给定连接桌子的传送带的信息，写一个程序实现 IOI 君确定原来传送带方向的策略，最多进行上述操作 \(30\) 次。
对于所有输入数据，满足：\(N\leq 10^5\)，\(0\le A_i,B_i\le N-1\)，如果我们忽略传送带的方向，每对桌子都被一系列传送带所连接。

LibreOJ #2818.「eJOI2018」Cycle Sort

给定一个长为 \(n\) 的数列 \(\{a_i\}\) ，你可以多次进行如下操作：
选定 \(k\) 个不同的下标 \(i_1,i_2\cdots,i_k\)（其中 \(1\leq i_j\leq n\)），然后将 \(a_{i_1}\) 移动到下标 \(i_2\) 处，将 \(a_{i_2}\) 移动到下标 \(i_3\) 处，……，将 \(a_{i_{k-1}}\) 移动到下标 \(i_k\) 处，将 \(a_{i_k}\) 移动到下标 \(i_1\) 处。
换言之，你可以按照如下的顺序轮换元素：\(i_1\rightarrow i_2\rightarrow\cdots\rightarrow i_{k}\rightarrow i_1\)。
例如：\(n=4,\{a_i\}=\{10,20,30,40\},i_1=2,i_2=3,i_3=4\) ，则操作完成后的 \(a\) 数列变为 \(\{10,40,20,30\}\)。
你的任务是用操作次数最少的方法将整个数列排序成不降的。注意，所有操作中选定下标的个数总和不得超过 \(s\) 。如果不存在这样的方法（无解），输出 -1。
对于 \(100\%\) 的数据：\(1\leq n\leq 2\times 10^5\)，\(0\leq s\leq 2\times 10^5\)，\(1\leq a_i\leq 10^9\)。

LibreOJ #2839.「JOISC 2018 Day 3」Security Gate

你知道「净是一些鬼畜发明公司」（Just Odd Inventions Co., Ltd.）吗？这家公司就是发明一些鬼畜玩意的。现在我们就叫它 JOI 公司。
为了防止机密信息泄露，公司门口装有一个安全门。进出这家公司必须通过这个门，并且每次只能容纳一人通过，无法两人或多人同时通过。
一旦有人通过这个安全门，安全门就会记录一条信息，表示行人是进入公司还是离开公司。公司的一名雇员 IOI 君得到了某天安全门的一份记录。我们用一个括号序列 S 代表这份记录，用 \(S_i\) 表示 \(S\) 的第 \(i\) 个字符。若 \(S_i=\)(，则第 \(i\) 个通过安全门的人进入了公司；若 \(S_i=\) )，则第 \(i\) 个通过安全门的人离开了公司。已知在当天开始和结束时，公司内都没有人。注意：存在字符串 \(S\) 只包含 ( 和 ) 但不表示一个合法记录。如：这样的两份记录：())( 和 (() 就不是合法记录。第一条记录会导致 JOI 公司内有负数个人，第二条记录表示这天下班之后 JOI 公司还有一个人。
IOI 君检查完 \(S\) 后，\(S\) 就被病毒修改了！经过一些调查，他猜测病毒修改 \(S\) 的方法如下：

\(•\) 先将「\(S\) 里面连续的一段字符串」中每一个 ( 修改为 )，每一个 ) 则修改为 (。用 \(S'\) 表示这次修改后的字符串。注意，该操作可能并没有执行，因此有可能出现 \(S'=S\) 的情况。

\(•\) 然后将 \(S'\) 中的某些字符改为 \(x\)。用 \(S''\) 表示这次修改后的字符串。该操作也可能并没有执行，因此有可能出现 \(S''=S'\) 的情况。
IOI 君不记得 \(S\) 了，所以他想将 \(S''\) 恢复到 \(S\)。为了达到这个目的，他首先想知道有多少可能的 \(S'\)（注意，不是 \(S\)）。
任务
给出字符串 \(S''\)，写一个程序计算有多少可能的 \(S'\) 字符串，模 \(10^9+7\) 输出。
对于所有数据，满足 \(1\le N\le 300\)。

LibreOJ #2842.「JOISC 2018 Day 4」Wild Boar

JOI 君是生活在 IOI 森林里的一头野猪。森林可视为一个包含 \(N\) 个结点，\(M\) 条带权无向边的连通图。结点的编号分别为 \(1\ldots N\)。\(i\) 号边连接结点 \(A_i\) 和 \(B_i\)，权值为 \(C_i\)。保证 \((A_i,B_i)\neq(A_j,B_j)\)，并且保证：对于任意两点互相可达。
开始时有一个长度为 \(L\) 的序列 \(X_1,\) \(X_2\) \(\ldots\) \(X_L\)，表示 JOI 君开始时在 \(X_1\)，它要依次访问结点 \(X_2\) \(\ldots\) \(X_L\)。序列中可能有重复结点，但保证序列中相邻两结点不同，即保证序列中 \(X_j\not=X_{j+1}\)。注意，不要求从 \(X_j\) 直达 \(X_{j+1}\)，JOI 君可以从 \(X_j\) 出发，经过其他结点作为中转，再到达 \(X_{j+1}\)。但是，JOI 君不能沿原路返回前一个到达的结点。参见样例。
接下来有 \(T\) 次修改，每次修改会给出两个整数 \(P_k, Q_k\)，表示将 \(X_{P_{\scriptsize k}}\) 修改为 \(Q_k\)。每次修改后，JOI 君想知道：他能否找到满足要求的路径。如果能，请输出最短路的长度，反之则输出 -1。
对于所有数据，\(2\le N\le 2000\)，\(N-1\le M\le 2000\)，\(1\le T\le 10^5\)，\(2\le L\le 10^5\)。\(1\le A_i<B_i\le N\)，保证图是连通图。\(1\le C_i\le 10^9\)。\(X_j\neq X_{j+1}\)。

LibreOJ #3034. 「JOISC 2019 Day2」Two Dishes

厨师比太郎正在参加一个厨艺比赛。在这场比赛中参赛者要烹饪两道料理：IOI 盖饭和 JOI 咖喱。
IOI 盖饭的烹饪过程中需要 \(N\) 个步骤。第 \(i (1\le i\le N)\) 步的用时是 \(A_i\) 分钟，最初他只能进行第 \(1\) 步，想要进行第 \(i (2\le i \le N)\) 步的条件是已经完成了第 \(i - 1\) 步。
JOI 咖喱的烹饪过程中需要 \(M\) 个步骤。第 \(j (1\le j\le M)\) 步的用时是 \(B_j\) 分钟，最初他只能进行第 \(1\) 步，想要进行第 \(j (2\le j \le M)\) 步的条件是已经完成了第 \(j - 1\) 步。
做料理过程中需要专心致志，所以当他开始进行一个步骤时，就不能中断。当完成了一个步骤，他也可以选择进行另一道料理的下一个步骤。比赛开始后，在两道料理都完成之前，他不能停下来休息。
在这场比赛中，参赛者会按照接下来的方式得到艺术感的打分：

\(•\) 如果他在比赛的前 \(S_i (1\le i \le N)\) 分钟内完成了 IOI 盖饭的第 \(i\) 个步骤，那么从中他会得到 \(P_i\) 点的分数，分数有可能是负的。

\(•\) 如果他在比赛的前 \(T_j (1\le j \le M)\) 分钟内完成了 JOI 咖喱的第 \(j\) 个步骤，那么从中他会得到 \(Q_j\) 点的分数，分数有可能是负的。
请你帮助比太郎设计做料理过程，最大化他做料理的艺术感评分。
对于全部数据，\(1\le N, M\le 10^6\)，\(1\le A_i, B_j \le 10^9 (1\le i\le N, 1\le j\le M)\)，\(1\le S_i, T_j\le 2\times 10^{15} (1\le i\le N, 1\le j\le M)\)，\(|P_i|, |Q_j| \le 10^9(1\le i\le N, 1\le j\le M)\)。

LibreOJ #3038.「JOISC 2019 Day3」Bitaro

在河狸国，一条路上有 \(N\) 座城市，依次编为 \(1\ldots N\) 号；连接城市 \(i\) 和城市 \(i+1\) 的那段路被称为 \(i\) 号路。在河狸国，一天有 \(10^9\) 秒，依次称为时刻 \(0\ldots 10^9-1\)。从城市 \(i\) 沿路到达与之相邻的城市——城市 \(i-1\) 或城市 \(i+1\) 需要 \(1\) 个单位时间。\(i\) 号路每天在时刻 \(L_i\) 到时刻 \(R_i\) 之间开放通行。具体说来，为了通过 \(i\) 号道路，我们必须在满足 \(L_i\le x\le R_i-1\) 的时刻 \(x\) 从城市 \(i\) 或城市 \(i+1\) 出发，在 \(x+1\) 时刻到达另一城市。
Bitaro 原本是一位住在河狸国的普通河狸，然而，为了改掉自己迟到的坏习惯，他最终获得了穿越时空的技能。每次使用这个技能，他能回到一秒前。但他不能回到前一天：也就是说，如果他在 \(0\) 时刻与 \(1\) 时刻之间使用技能，他只能回到这一天的 \(0\) 时刻。他只能在城市里使用这个技能。使用这个技能不会改变他的位置。
穿越时空会让 Birato 变累。为了找到能从一个城市到另一个城市且使用技能次数最少的方法，他决定进行一个 \(Q\) 步的想象试验。第 \(j\) 步实验是以下两种情况之一：

\(•\) 改变 \(P_j\) 号道路的开放时间，改后 \(P_j\) 号道路在时刻 \(S_j\) 到时刻 \(E_j\) 开放通行；

\(•\) 假设时刻 \(B_j\) 他在城市 \(A_j\)，然后计算在这一天的时刻 \(D_j\) 他要到达城市 \(C_j\) 的话至少需要使用多少次技能。
他很想知道实验结果。
对于全部数据：\(1\le N,Q\le 3\times 10^5\)，\(0\le L_i\lt R_i\le 10^9-1\ (1\le i\le N-1)\)。当 \(T_j=1\) 时，\(1\le P_j\le N-1,0\le S_j\lt E_j\le 10^9-1\ (1\le j\le Q)\)；当 \(T_j=2\) 时，\(1\le A_j,C_j\le N,0\le B_j,D_j\le 10^9-1\ (1\le j\le Q)\)。

LibreOJ #3378.「eJOI2020」Dots and Boxes

小 T 和小 A 在玩一种点格游戏。
首先，小 T 拿出了一张拥有 \((N+1) \times (M+1)\) 个格点的方格纸（这些格子从上到下，从左到右可以编号为第 \(1 \sim N+1\) 行第 \(1 \sim M+1\) 列的格点），每个格点向上下左右的那个格点（如果那个方向有格点的话）连边，不难发现，会形成一个 \(N \times M\) 的方格矩阵。但是小 T 拿出的是没有连边的格点方格纸，小 T 和小 A 的目标就是在格点之间连线。
游戏规则是这样的，每一轮玩家可以在两个格点之间连线，如果连完线能连好一个格子，那么这个格子就属于这个玩家了。然后玩家可以继续连线，直到连完线不能获得格子为止，就换到下一个玩家。当所有玩家都不能连线时，游戏结束。
比如下面这张图即为当 \(N=2,M=3\) 时两位玩家可能的连线结果：

其中虚线为这一轮玩家连的线。
小 A 和小 T 已经玩了许久了，你发现他们现在的方格纸满足每一个格子周围的四条边都有 \(0\) 条或 \(2\) 条未被连线，比如下面这张图就满足要求，上面这张图除了第一幅图也都满足要求：

并且刚好轮到小 A 了。
定义小 A 和小 T 的分数 \(S_A,S_T\) 为玩家从现在开始得到的分数，那么整个游戏的分数即为 \(S_A-S_T\)，小 A 要让整个游戏的分数变得越大越好，小 T 则反之，他们都会按照他们的目标做最优策略。
你要求出他们做最优策略下得到的分数。
对于 \(100\%\) 的数据，\(3 \le N, M \le 20\)，每一个格子周围的四条边都有 \(0\) 条或 \(2\) 条未被连线。

LibreOJ #3471. 「JOI 2021 Final」Robot

给定一个 \(N\) 点无向图，这 \(N\) 个点编号为 \(1 \sim N\)，由 \(M\) 条边连接，这 \(M\) 条边编号为 \(1 \sim M\)，分别连接点 \(A_i\) 与点 \(B_i\)。这 \(M\) 条边染上了颜色，第 \(i\) 条边的颜色为 \(C_i\)，保证 \(C_i \in [1,M]\) 但不保证 \(C_i\) 互不相等。
你很智能，如果我说一种颜色 \(L\)，满足下面这些要求的话：

\(•\) 存在一条边的颜色为 \(L\) 且一个端点为你现在在的点。

\(•\) 不存在大于等于两条边满足颜色为 \(L\) 且一个端点为你现在在的点。
你就会移动到这条边走向对面的端点，否则你就会原地不动。
你现在在点 \(1\) 处，我要你移动到点 \(N\) 处，我可以告诉你一些颜色你按照这些颜色走。但这个图有可能不满足能从 \(1\) 走向 \(N\) 这个条件，因此我要改变一些边的颜色。改变第 \(i\) 条边的颜色使其变为另一个在区间 \([1,M]\) 里的数需要的代价为 \(P_i\)，我想问，至少需要多少代价才能让你成功移动到点 \(N\)？
对于 \(100\%\) 的数据，\(2 \le N \le 10^5\)，\(1 \le M \le 2 \times 10^5\)，\(1 \le A_i<B_i \le N\)，\(1 \le C_i \le M\)，\(1 \le P_i \le 10^9\)，保证图无重边。

LibreOJ #3472.「JOI 2021 Final」Dungeon 3

有一个 \(N+1\) 层的地牢，在地牢里有 \(M\) 个玩家。地牢的每层从入口开始，用 \(1\) 到 \(N+1\) 的整数编号。玩家从 \(1\) 到 \(M\) 标号。
玩家使用能量从一层移动到下一层。玩家从第 \(i\ (1\le i\le N)\) 层移动到第 \(i+1\) 层所用的能量为 \(A_i\)。因为这是一个单向通行的地牢，所以玩家只能从第 \(i\) 层移动到第 \(i+1\) 层，并且要保证 \(1\le i\le N\)。
在第 \(1\) 到第 \(N\) 层的每层（包括第 \(1\) 和第 \(N\) 层）都有治疗泉。在第 \(i\) 层的治疗泉处，玩家可以花 \(B_i\) 金币，使自己的能量增加 \(1\)。只要玩家有足够的金币，他就可以多次使用治疗泉。但是，每个玩家都有最大能量，使用治疗泉的话也不能使自己的能量超过最大值。
现在玩家 \(j\ (1\le j\le M)\) 在第 \(S_j\) 层。他目前的能量为 \(0\)。他的最大能量是 \(U_j\)。他想要到第 \(T_j\) 层。在路上他的能量不能小于 \(0\)。他需要多少金币呢？
给定这个地牢和玩家的信息，写一个程序计算对于每个玩家，是否可以在移动过程中能量不小于 \(0\) 的情况下到达目的地。如果可以的话，计算他最少需要多少金币才能达成目标。
对于所有数据，满足：\(1\le N,M\le 2\times 10^5\)，\(1\le A_i,B_i\le 2\times 10^5\ (1\le i\le N)\)，\(1\le S_j<T_j\le N+1\ (1\le j\le M)\)，\(1\le U_j\le 10^8\ (1\le j\le M)\)。

LibreOJ #3489.「JOISC 2021 Day1」Food Court

有 \(N\) 家书虫食品店，有 \(M\) 个家庭来享受用书虫制作的美味食物。
因为食品店十分火爆，所以顾客需要排队，刚开始所有队列都是空的。
今天食品店又全部开张了，发生了 \(Q\) 个事件：
\(•\) 加入事件：编号位于区间 \([L,R]\) 内的所有食品店中，都有编号为 \(C\) 的家庭加入队尾，每个满足要求的食品店队尾都加入了 \(K\) 个人。
\(•\) 离开事件：编号位于区间 \([L,R]\) 内的所有食品店中，如果队列有超过 \(K\) 个人，那么队列的前 \(K\) 个人离开队列，否则队列里的所有人离开队列。
\(•\) 白嫖事件：如果编号为 \(A\) 的食品店的队列中有大于等于 \(B\) 个人，那么食品店就会赠送从队列开头开始数第 \(B\) 个人一份秘制书虫，否则店员会吃掉书虫。
求每次 白嫖事件 是否有顾客被赠送了秘制书虫，如果有的话，求顾客所在的家庭。
对于 \(100\%\) 的数据：\(1 \le N,M,Q \le 25 \times 10^4\)，\(T \in \{1,2,3\}\)，对于所有 加入事件，\(1 \le L \le R \le N\)，\(1 \le C \le M\)，\(1 \le K \le 10^9\)。对于所有 离开事件，\(1 \le L \le R \le N\)，\(1 \le K \le 10^9\)；对于所有 白嫖事件，\(1 \le A \le N\)，\(1 \le B \le 10^{15}\)。至少有一个 白嫖事件。

LibreOJ #3490.「JOISC 2021 Day1」Escape Route

IOI 王国的国民使用 Byou 作为时间单位。
IOI 王国中，一天被划分为 \(S\) Byou，其中第 \(x\) 个 Byou(\(0\leq x < S\)) 被称为时刻 \(x\)。
IOI 王国中有 \(N\) 个城市（标号 \(0\sim N-1\)）和 \(M\) 条双向道路（标号 \(0 \sim M-1\)），你可以通过道路从一个城市移动到另一个城市。第 \(i\) 条道路直接连接着城市 \(A_i\) 和 \(B_i\)，通过这条道路需要 \(L_i\) Byou。每天，从时刻 \(C_i\) 开始要对第 \(i\) 条道路进行检查，直到这一天结束。
JOI 集团是 IOI 王国中的一个秘密组织，出于其保密性，JOI 集团的成员不应该在道路上受到检查，这意味着如果 JOI 王国的成员如果想要通过道路 \(i\)，那么他必须在时刻 \(C_i-L_i\) 之前踏上这条路。
现在有 \(Q\) 名 JOI 集团的成员（标号 \(0 \sim Q-1\)），第 \(j\) 名成员在某一天的时刻 \(T_j\) 想要从城市 \(U_j\) 出发旅行去城市 \(V_j\)。成员可以在城市内停留任意长的时间。这名成员可能要花费多天才能到达城市 \(V_j\)。
现要求计算每个成员完成旅行所需要的最少时间。
对于 \(100\%\) 的数据，保证：\(2 \leq N \leq 90\)，\(N-1 \leq M \leq \dfrac{N(N-1)}{2}\)，\(2 \leq S \leq 10^{15}\)，\(1 \leq Q \leq 3 \times 10^6\)，\(0 \leq A_i,B_i \leq N-1 (0 \leq i \leq M-1)\)，\(A_i \ne B_i(0 \leq i \leq M-1)\)。\(\forall i,j \in [0,M-1]\)，若 \(i \ne j\)，则有 \((A_i,B_i) \ne (A_j,B_j),(A_i,B_i) \ne (B_j,A_j)\)。\(1 \leq L_i \leq C_i < S\)。你可以从某个城市经过若干条道路到达任意另一个城市。\(0\leq U_j,V_j \leq N-1(0 \leq J \leq Q-1)\)，\(U-j \ne V_j\)，\(0 \leq T_j < S\)。

LibreOJ #3498.「JOISC 2021 Day4」Worst Reporter 4

Bitaro 是一名主要写关于 OI 的报道的记者。再过几天，就要举行 IOI 了，B 太郎决定写一篇关于 IOI 的文章。
比赛将有 \(n\) 名选手参加，每位选手的编号从 \(1\) 到 \(n\)。每位选手都有一个 Rating，这是衡量其实力的标准。Rating 用 \(1\) 至 \(10^9\) 之间的整数表示。
Bitaro 采访了每位选手，并获得了以下信息：

\(•\) 选手 \(i\ (1\le i\le N)\) 的 Rating 大于等于选手 \(a_i\ (1\le a_i \le n)\) 的 Rating。（\(a_i\) 可以等于 \(i\)）。
在所有的采访结束后，B 太郎从管理 Rating 系统的公司收到了一张表格，上面有每个选手的 Rating。 表上写着以下信息：

\(•\) 选手 \(i\ (1 \le i \le n)\) 的 Rating 是 \(h_i\)。
当 Bitaro 试图根据这些信息写一篇文章时，他发现每个选手的 Rating 表可能存在错误。
由于临近截止时间，没有时间去弄正确的 Rating 表。因此，B 太郎决定重写表中选手的 Rating，使其与采访中获得的信息不相矛盾。
Bitaro 在表中改写选手 \(i\ (1\le i \le n)\) 的 Rating 需要 \(c_i\) 日元。
也就是说，Bitaro可以通过支付 \(c_i\) 元，将列表中选手 \(i\) 的 Rating 更改为 \(1\) 到 \(10^9\) 之间的任意整数。为了在截止日期前完成任务，B 太郎想要最小化更改列表中 Rating 的总成本。
编写一个程序，给定选手的数量、采访获得的信息、Rating 列表、和更改每个选手 Rating 所用的花费。请你计算不与采访信息矛盾的情况下，最少需要花费多少元。
对于全部数据，\(2\le N\le 2\times 10^5\)，\(1\le A_i\le N\ (1\le i\le N)\)，\(1\le H_i,C_i\le 10^9\ (1\le i\le N)\)。

LibreOJ #3560.「BalticOI 2021 Day1」From Hacks to Snitches

给定一个 \(N\) 个点 \(M\) 条边的无向图，有 \(K\) 个守卫第 \(i\) 个守卫会经过 \(\ell_i\) 个节点，这 \(\ell_i\) 个节点分别为 \(v_1,v_2,\cdots,v_{\ell_i}\)，运行机制为守卫刚开始位于第 \(v_1\) 个节点，设其为第 \(0\) 分钟，\(1\) 分钟时从第 \(v_1\) 个节点走到第 \(v_2\) 个节点，\(2\) 分钟时从第 \(v_2\) 个节点走到第 \(v_3\) 个节点，……，\(\ell_i-1\) 分钟时从第 \(v_{\ell_i-1}\) 个节点走到第 \(v_{\ell_i}\) 个节点，\(\ell_i\) 分钟时从第 \(v_{\ell_i}\) 个节点走到第 \(v_1\) 个节点，以此类推，无限循环。
您是一个小偷，您要从第 \(1\) 个节点到达第 \(N\) 个节点，即 \(0\) 分钟时您位于 \(1\) 号节点，您可以一个节点直接到另一个节点，但是要经过这两个节点之间的路径，您要保证这条路径上没有一个节点上有守卫，且守卫也不经过这些组成路径的边。您经过每一条边的时间都是一分钟。保证任意两个守卫的路径不相交，并且起点和终点均不在任意守卫的路径上。
您想知道不被守卫发现的情况下需要最短多少分钟或者提出无解。
对于 \(100\%\) 的数据，\(1 \le N \le 2.5 \times 10^5\)，\(1 \le M \le 3 \times 10^6\)，\(3 \le ℓ_i \le 1500\)，\(\sum ℓ_i \le 2750\)。

LibreOJ #3883.「eJOI2022」Adjacent Pairs

如果对于任意满足 \(1\le i\le m-1\) 的 \(i\)，都有 \(b_i\neq b_{i+1}\)，我们就称数组 \(b_1,b_2,\ldots,b_m\) 是好的。
给定一个长度为 \(n\) 的好数组 \(a_1,a_2,\ldots,a_n\)。你可以对这个数组进行如下操作：
\(•\) 选择任意下标 \(i\ (1\le i\le n)\) 和一个数字 \(x\ (1\le x\le 10^9)\)。然后将 \(x\) 赋给 \(a_i\)。在此操作后，数组必须仍然是好的。
你想要进行一些操作，使得最终得到的数组只包含恰好两个不同的值。请确定为了达成目标所需的最小操作次数。
对于全部数据，满足 \(1\le t\le 10^5\)，\(2\le n\le 2\cdot 10^5\)，\(1\le a_i\le n\)。保证一组数据的所有测试点中 \(n\) 的总和不超过 \(2\cdot 10^5\)。

LibreOJ #3884.「eJOI2022」Where Is the Root?

这是一道交互题。
给定一个有 \(n\) 个节点的树。树是满足任意两不同点之间恰好有一条简单路径的图。同时保证至少有一个节点，这个节点与至少三个节点直接有边相连。其中一个节点是根，你的任务是找到它。为了完成这个任务，你允许问如下格式的问题：
\(•\) 对于给定的点集 \(a_1,a_2,\ldots,a_m\)，检查它们的最近公共祖先是否在集合中。
如果所有 \(S\) 中的点到根的路径都经过 \(v\)，那么就称节点 \(v\) 是点集 \(S\) 的公共祖先。点集 \(S\) 的最近公共祖先（LCA）就是点集 \(S\) 的公共祖先中距离根最远的那个。
对于全部数据，满足 \(n\leq 500\)。

LibreOJ #3885.「eJOI2022」Bounded Spanning Tree

给定一个有 \(n\) 个点 \(m\) 条边的连通无向有边权图。图中没有自环（即，没有从一个点出发的边连向它本身），但是一些点对之间可能有重边。
你的朋友告诉了你关于这张图的如下信息：
\(•\) 边权是在 \([1,m]\) 范围中互不相同的整数。换句话说，它们形成了整数 \(1\) 到 \(m\) 的某个排列。
\(•\) 对于 \(i\) 从 \(1\) 到 \(m\)，第 \(i\) 条边的边权在 \([l_i,r_i]\) 范围中。
\(•\) 下标为 \(1,2,\ldots,n-1\) 的边（输入中前 \(n-1\) 条边）形成了这个图的一棵最小生成树。
你想要知道这是否是可能的。确定是否存在满足上述条件的一个边权分配方案，并且如果存在，找出一种方案。
注：图的一棵生成树是图上任何一个边的子集，这些边可以构成树（\(n\) 个点 \(n-1\) 条边的连通图）。图的最小生成树是图的所有生成树中边权和最小的生成树。
对于全部数据，\(1\le t\le 10^5\)，\(1\le n-1\le m\le 5\cdot 10^5\)，\(1\le u_i<v_i\le n,1\le l_i\le r_i\le m\)。保证对于每个测试点，下标为 \(1,2,\ldots,n-1\) 的边会形成给定图的一棵生成树。保证对于一组数据中的所有测试点，\(m\) 的总和不超过 \(5\cdot 10^5\)。

LibreOJ #3886.「eJOI2022」Game With Numbers

两个玩家正在玩一个游戏。给定他们两个数组 \(a_1,a_2,\ldots,a_n\) 和 \(b_1,b_2,\ldots,b_m\)。
游戏包含 \(m\) 轮。玩家按轮交替操作。在第 \(i\) 轮（\(i\) 从 \(1\) 到 \(m\)），玩家（如果 \(i\) 是奇数，则为第一位玩家，如果是偶数，则为第二位玩家）需要进行如下操作中的恰好一个：
\(•\) 移除数组 \(a\) 中所有能被 \(b_i\) 整除的元素，
\(•\) 移除数组 \(a\) 中所有不能被 \(b_i\) 整除的元素。
第一位玩家想要最小化 \(m\) 次操作后 \(a\) 中剩余元素的和，第二位玩家想要最大化 \(m\) 次操作后 \(a\) 中剩余元素的和。请计算如果双方均使用最优策略操作，\(m\) 次操作后数组 \(a\) 中剩余元素的和是多少。
对于全部数据，\(1\le n\le 2\cdot 10^4,1\le m\le 2\cdot 10^5\)，\(-4\cdot 10^{14}\le a_i\le 4\cdot 10^{14}\)，\(1\le b_i\le 4\cdot 10^{14}\)。

LibreOJ #3887.「eJOI2022」Longest Unfriendly Subsequence

我们称一个序列 \(b_1,b_2,\ldots,b_m\) 是不友好的，如果它满足如下条件：
\(•\) 如果对于 \(1\le i<j\le m\) 且 \(j-i\le 2\)，有 \(b_i\neq b_j\)。
换句话说，一个序列是不友好的，如果任意距离至多为 \(2\) 的两个元素是不同的。
给定一个序列 \(a_1,a_2,\ldots,a_n\)，找到它最长不友好子序列的长度。
如果一个序列 \(d\) 可以通过删除一些（可能不删，也可能删除全部）元素得到序列 \(c\)，则称序列 \(c\) 是序列 \(d\) 的子序列。例如 \((1,3,5)\) 是 \((1,2,3,4,5)\) 的一个子序列，而 \((3,1)\) 不是。
对于全部数据，\(1\le t\le 10^5\)，\(1\le n\le 2\cdot 10^5\)，\(1\le a_i\le 10^9\)。保证一组测试数据中所有测试点的 \(n\) 的总和不超过 \(2\cdot 10^5\)。

LibreOJ #3888.「eJOI2022」LCS of Permutations

对于两个序列 \(x,y\)，定义 \(\text{LCS}(x,y)\) 为它们最长公共子序列的长度。
给定四个整数 \(n,a,b,c\)。确定是否存在三个长度为 \(n\) 的从 \(1\) 到 \(n\) 的整数的排列 \(p,q,r\)，满足：
\(•\) \(\text{LCS}(p,q)=a\)
\(•\) \(\text{LCS}(p,r)=b\)
\(•\) \(\text{LCS}(q,r)=c\)
如果这样的排列存在，找出这样排列的三元组。
从 \(1\) 到 \(n\) 的整数排列 \(p\) 是一个长度为 \(n\) 的序列，序列中所有元素都在 \([1,n]\) 中并且两两不同。例如，\((2,4,3,5,1)\) 是一个从 \(1\) 到 \(5\) 的整数排列，而 \((1,2,1,3,5),(1,2,3,4,6)\) 不是。
如果一个序列 \(d\) 可以通过删除一些（可能不删，也可能删除全部）元素得到序列 \(c\)，则称序列 \(c\) 是序列 \(d\) 的子序列。例如 \((1,3,5)\) 是 \((1,2,3,4,5)\) 的一个子序列，而 \((3,1)\) 不是。
序列 \(x\) 和 \(y\) 的最长公共子序列是满足同时为 \(x\) 和 \(y\) 的子序列中最长的一个。例如，\(x=(1,3,2,4,5)\) 和 \(y=(5,2,3,4,1)\) 的最长公共子序列是 \(z=(2,4)\)，因为它是两个序列的子序列，并且是最长的。\(\text{LCS}(x,y)\) 是最长公共子序列的长度，上述例子中这个值为 \(2\)。
对于全部数据，\(1\le t\le 10^5\)，\(1\le a\le b\le c\le n\le 2\cdot 10^5,0\le output\le 1\)。保证一组测试数据中所有测试点的 \(n\) 的总和不超过 \(2\cdot 10^5\)。