THUWC2024游记
THUWC 2024 游记
Day -5~-1
我们都去报名了 THUWC 和 PKUWC，有一些人通过了，有一些人没有通过，有点遗憾，但是今年 5 月还有机会，通过之后，我们每天都在做 THUSC/PKUSC/THUWC/PKUWC 的题，人都要做不好了。
还有讲题环节，我最好在讲题之前确认知识点我们有没有学过，小的知识点可以现学，但是大的知识点就不行了。（多项式 天气预报）
帅气的 deaf 学长也来给我们讲题了，只不过跟照片上的有些差距（
这几天压力感觉没有那么大，就像初一去考 THUSC 玩一样。
Day 0
上午在讲题，就是 deaf 学长，讲的题都很神仙，神仙贪心等等，当然有些完全没学过的多项式奇技淫巧就跳过了。
中午简单吃了个饭，和同学打了一下羽毛球，然后就准备着下午的报道。
下午我们乘坐着学校的大巴车到了重庆巴蜀中学（原四十一中），我是第一次来到巴蜀中学本部，被它的地形震惊到了，居然是一个长条形的，直插入山谷里面，记得鲁能巴蜀都很平整，大巴车一直沿着滨江路在走，我一直以为巴蜀中学是在河对面，没想到跟我们学校在河的同一侧。
车上太抖了，什么都干不了，据说有些人在研究非公平博弈，有人也和我商量着非公平博弈，为后文埋下伏笔。（指 dp
到了之后我们拍了照，领了报到证等东西，但是这次的奖励还很丰厚？去年是一件衬衫和一些小玩意，今年发了一个鼠标，和一个带有大师签名的 AI 普及书，感觉赚了不少。（后面听北大的说他们的礼物很寒碜，还好没去）
然后就是去试机，拿过一等的还不让用学校的电脑，于是我们被强迫带电脑过去，然后在物理实验室进行考试，不懂就问，为什么巴蜀那整栋楼都有一种特殊的香味啊。
测试了一共三道题，一道 A+B，一道构造，一道交互，交互题去年就考过，感觉快做腻了，把 A+B 过了，然后打了 T2 部分分就测试完了，学校急着集合我们走，领了 Linux 系统的安装说明然后就离开了。
离开的时候看着某个人戴了一个黑色的猫耳朵，不知道是谁，也没有胆量上去问。
其他人是在地下室考场或者和我们在同一栋楼不过是在计算机教室，地下室考场居然没有分教室，那敲键盘的声音可谓是群魔乱舞吧。
到达集合地点之后发现一堆人玩非公平博弈被教练抓了，但是我并不太觉得这个行为有什么过错，没事，不该我们操心的事就不要去管他，或许这跟玩游戏的性质一样吧，很多人说他是错的他就是错的，却拿不出什么能够说服的理由来。
晚上回寝室早早地睡了个觉，明天要早起去打车去巴蜀。
Day 1
6:00 就起床了，然后抓紧时间洗漱，吃饭，带好一切东西去校门口和教练会面打车去巴蜀。
到了巴蜀中学没有想象中的人山人海，因为实在是太早了，我们到一个小餐馆去吃了顿饭（教练和另外一个同学没吃），顺便还把电脑调试好了。（虚拟机和录屏软件）
最后就是进考场了，途中除了本校的同学，认不得一个人，考场还是有那种特殊的香味。
好，调试好录屏软件开始考试了，首先看 T1，哇，线性规划，网络流怼上去，然后怼了一个小时没有怼出来结果。。。
感觉 T1 怕是调不出来了，打了前三个 Sub 的暴力，就去开 T3，甚至连 $2 \times 2$ 的矩阵我都做了 10 来分钟，不知道脑子怎么想的。
然后第二个 Sub 倍增解决嘛，第三个 Sub 想到了四分，然后用树状数组剪了一下枝就拿到了一共 75 分，还好，不打算继续优化了，这个时候应该是 2 个小时。
接下来是第 2 题，第 2 题首先可以 $n^3$ 优化矩阵转移，轻松通过了很多个 Sub，然后有一个 $n^2$ 但是 $m=1$ 的点，找了一下规律，发现可以差分预处理前面 $i \to j$ 的转移，然后又过了一个 Sub，这个时候又发现矩阵的 $i,j$ 对于 $j-i$ 相同的是固定的，于是矩阵转移就变成了 $O(n^2)$ 的，但是开 long long 跑不过去，改成 int 就过了，成功拿到了 $90$ 分，这个时候定睛一看是多项式相乘，但是我不会 NTT，剩下 $10$ 分就没拿到。
最后看第 4 题，第 4 题第一个 Sub 暴力模拟就可以了，第二个 Sub 感觉可做，离线下来维护最小生成树就可以了，调到了比赛还剩 $20$ 分钟终于调出来了。
后面两个 Sub 猜得到是 LCT 维护最小生成树，但是我不会 LCT，也只能作罢。
最后 $10$ 分钟，灵光乍现，A 题可以直接枚举子集，于是快速写了一个 $O(3^nm)$ 的做法，不出意外 $90$ 分，比赛也结束了。
赛后交流了一下做法，发现 A 题把枚举子集拿到外面去可以获得 $O(3^n+2^nm)$ 的做法就可以 AC，C 题因为数据水（不过有 Sys Test），只访问右下角的矩形可以获得 $96$ 分，如果先访问右半矩形，按照第一个 Sub 来做可以得 $100$ 分，不过是错的，赛后被应该被卡到了 $24$ 分。
B 题 Eznibuil 拿到了 100 分，%%%。
然后集合去吃饭，饭 25 元，因为去的时间晚了，导致没吃到多的，只有两个菜了。。。并且那个啥连我们重庆人都觉得好辣，不知道外地人如何评价，吃完饭去集合地点玩了 surf，然后就去拍照了。
拍照仍然很枯燥，不过有音乐打消，还挺好的，反正这待遇去年是没有，没什么好说的。
不过提问环节有人直接开始问第二天的工程题是不是人工智能（
听讲座那些太枯燥了，我们直接在电脑上写了一个 dp 的程序 dp，只不过电脑耗电比较快，很快就没电了，没 dp 几局就关机了。
晚上回学校，在乡村基吃完饭后看到了 recollect_i 和 Judgelight，他们是去的 P，问了一下情况，考得还不错（至少在同一年级相比），P 的大众分是 $100+11+40=151$，比 T 这边要难许多。
晚自习只有我们三个上，其它人都回去了，于是就开始搞毫（，他们在卷题，我在准备明天工程题的 Linux 系统还有录屏软件。
仍然早早睡了觉，明天是 8:00 集合，故可以睡久一点。
Day 2
自己打车吃饭去巴蜀中学，情况同第一天差不多，有人来得更早，我不说是谁。
道了别，去各自的考场迎接今年的工程题轰炸，果然还是跟人工智能相关，四子棋，我爱死你了。
汲取了去年没有看 ppt 的教训，今年直接开始看 ppt，然后在本机用 Linux 系统测试了一下，测试大概花费了 $1$ 个小时，我对 Linux 的系统操作还不是很熟悉，主要是以为 .so 文件可以运行，实际上只是一个普通的后缀名。。。
ppt 说有极大极小算法，$\alpha-\beta$ 剪枝，还有什么什么树，我感觉不太好理解，于是自己写了一个特判的代码，就是能绝杀一定绝杀，否则不能让对手绝杀自己。
然后完全没有注意到 $2$ 是自己，$1$ 是下发程序，调了 $1$ 个小时，连 $4.so$ 都打不过，交上去 TLE 了，发现是输出太多了，没删除调试语句，删了之后过了 $1.so,3.so$。
于是转去写那个啥啥树，那个还比较好些，稍微卡了一下时间（后面两个小时的主要操作内容），然后把十次机会用完了，得到了 $100+90+80+50+30$ 的好成绩。。。
很遗憾，两天加起来 $291+350=641$，第一天如果拿到 $10$ 分的话，分数也会好看一些，第二天如果写了 $\alpha-\beta$ 剪枝，据说可以拿到 $400$ 分，没事，过去就过去了，没什么好说的，争取下次还按这样的分值总分的话，拿到 $700$ 吧。
比赛结束后据说很多人没有看 ppt 自己写，大部分没有写出来什么，但是 naoliaok_lovely 写的暴搜得到了 $320$，%%%。
这个就没有 Sys test 了，还好。
下午是讲座，讲座上蚌埠住了，那句话我仍然记忆犹新：“你好，我是洛谷的题解审核志愿者……” 好好好
后面就是发纸，我们拿过的因为视频还没有接受审核，还拿不到奖状，所以只有等教练的消息，而我们学校的也是一些人欢喜，一些人忧愁，但是还是祝贺一下 Xseventh 和 naoliaok_lovely。
最后集合解散的时候看到一个人身上别了很多洛谷知名人物的徽章，十分羡慕，但是很无奈没有手机无法确认身份，这是今年最大的一个遗憾。
总之，过去就过去了，下次得想办法让今年的遗憾不在下次比赛中继续产生，尽管如此，我仍然期待着 THUSC 或者 PKUSC 的赛场！
以下是附录：
Day-1 题面
t1 — 小 R 的项目
时间限制： 1.0 秒
空间限制： 1024 MiB
题目描述
小 R 有一个项目，这个项目由 $n$ 项任务构成。由于时间紧迫，他需要请一些同学协助他完成。
小 R 有 $m$ 位同学，请第 $i$ 位同学协助的费用为 $c_i$。不同的同学完成同一项任务的效果可能不同，具体来说，请第 $i$ 位同学完成第 $j$ 项任务的收益为 $a_{i,j}$。
小 R 可以请若干名同学协助他完成这个项目。对于每项任务，小 R 会从他请来的同学中选出收益最高的一位来完成。具体来说，他的总收入将以如下方式计算：
- 每项任务的收益为：所有他请的同学完成该项任务的收益的最大值；
- 小 R 的总收入为：所有任务的收益之和，减去每位他请的同学的费用。
注意，小 R 请一位同学的费用与这位同学最终完成的任务数无关，他请来的每位同学都可以完成零项或大于一项任务，但是费用只计入答案一次。
特别地，如果小 R 没有请任何同学，他的总收入为 $0$。
你需要帮助小 R 求出他能获得的最大总收入。
输入格式
从标准输入读入数据。
输入的第一行包含两个正整数 $n,m$。
接下来 $m$ 行，第 $i$ 行包含 $n$ 个正整数 $a_{i,1},a_{i,2},\dots,a_{i,n}$。
接下来一行包含 $m$ 个正整数 $c_1,c_2,\dots,c_m$。
输出格式
输出到标准输出。
输出共一行，包含一个非负整数，分别表示小 R 能获得的最大总收入。
样例 1 输入
1 | 3 3 |
样例 1 输出
1 | 4 |
样例 1 解释
小 R 能获得的最大总收入是 $4$，共有以下 $6$ 种方式使他获得最大总收入：
- 请第 $1$ 位同学，总收入为 $2+1+4-3=4$；
- 请第 $2$ 位同学，总收入为 $1+4+2-3=4$；
- 请第 $3$ 位同学，总收入为 $4+2+1-3=4$；
- 请第 $1,2$ 位同学，总收入为 $\max(2,1)+\max(1,4)+\max(4,2)-3-3=4$；
- 请第 $1,3$ 位同学，总收入为 $\max(2,4)+\max(1,2)+\max(4,1)-3-3=4$；
- 请第 $2,3$ 位同学，总收入为 $\max(1,4)+\max(4,2)+\max(2,1)-3-3=4$。
样例 2
见题目目录下的 2.in 与 2.ans。
该样例满足子任务 1 的限制。
样例 3
见题目目录下的 3.in 与 3.ans。
该样例满足子任务 5 的限制。
子任务
对于所有测试数据，满足 $1 \le n \le 15$，$1 \le m \le 3000$，$1 \le c_i,a_{i,j} \le 100$。
| 子任务编号 | 分值 | $n \le $ | $m \le$ | 特殊性质 |
|---|---|---|---|---|
| 1 | $21$ | $15$ | $16$ | 无 |
| 2 | $24$ | $4$ | $50$ | 无 |
| 3 | $13$ | $15$ | $3000$ | 保证 $c_{i,j}=1$ 或 $c_{i,j}=50$ |
| 4 | $32$ | $10$ | $3000$ | 无 |
| 5 | $10$ | $15$ | $3000$ | 无 |
t2 — 小 R 的序列
时间限制： 2.0 秒
空间限制： 1024 MiB
题目描述
小 R 有一个长度为 $n$ 的非负整数环状序列 $a_0,a_1,\dots,a_{n-1}$。
小 C 将小 R 的序列拿去做了 $m$ 次操作。小 R 并不知道这些操作是什么，但他知道小 C 会随机选择一段环上的区间，并将区间内的所有数随机打乱。
具体而言，小 C 的每次操作按照如下过程进行：
- 在 $[0,n)$ 中等概率随机选择一个非负整数 $p$，在 $[1,n]$ 中等概率随机选择一个正整数 $l$；
- 将 $a_p,a_{(p+1) \bmod n},\dots,a_{(p+l-1)\bmod n}$ 随机打乱，即在 $0 \sim l-1$ 的所有排列中等概率随机选择排列 $q_0,q_1,\dots,q_{l-1}$，然后将 $a_p,a_{(p+1) \bmod n},\dots,a_{(p+l-1)\bmod n}$ 同时替换为 $a_{(p+q_0) \bmod n},a_{(p+q_1) \bmod n},\dots,a_{(p+q_{l-1}) \bmod n}$。
小 R 想知道小 C 进行 $m$ 次操作后序列上每个位置的数的期望，你只需要告诉他期望对 $998244353$ 取模后的结果。
输入格式
从标准输入读入数据。
输入的第一行包含两个正整数 $n,m$。
输入的第二行包含 $n$ 个非负整数 $a_0,a_1,\dots,a_{n-1}$。
输出格式
输出到标准输出。
输出共一行，包含 $n$ 个非负整数，用空格隔开，分别表示 $m$ 次操作后序列上每个位置的数的期望。
样例 1 输入
1 | 3 1 |
样例 1 输出
1 | 499122178 2 499122179 |
样例 1 解释
在这个样例中，小 C 进行了一次操作：
- 若 $l=1$，得到 ${1,2,3}$；
- 若 $l=2$，有 $\frac 12$ 的概率得到 ${1,2,3}$，各 $\frac 16$ 的概率得到 ${2,1,3},{1,3,2},{3,2,1}$；
- 若 $l=3$，等概率得到 ${1,2,3}$ 的所有排列中的一个。
最终每个位置的期望如下：
- $a_0$ 的期望为 $\frac 13 \times 1+\frac 1 3 \times(\frac 12 \times 1+\frac 16×(2+1+3))+\frac 13\times \frac 16 \times (1+1+2+2+3+3)=\frac 32$；
- $a_1$ 的期望为 $\frac 13 \times 2+\frac 13\times (\frac 12\times2+\frac 16\times(1+3+2))+\frac13\times \frac 16\times(1+1+2+2+3+3)=2$；
- $a_2$ 的期望为 $\frac 13 \times 3+\frac 13\times(\frac 12\times 3+\frac 16\times (3+2+1))+\frac 13\times \frac 16 \times(1+1+2+2+3+3)=\frac 52$；
样例 2
见题目目录下的 2.in 与 2.ans。
该样例满足子任务 3 的限制。
样例 3
见题目目录下的 3.in 与 3.ans。
该样例满足子任务 5 的限制。
样例 4
见题目目录下的 4.in 与 4.ans。
该样例满足子任务 9 的限制。
子任务
对于所有测试数据，满足 $2 \le n \le 131072$，$1 \le m \le 10^9$，$0 \le a_i < 998244353$。
| 子任务编号 | 分值 | $n=$ | $m \le$ |
|---|---|---|---|
| 1 | $3$ | $2$ | $1$ |
| 2 | $9$ | $2$ | $10^9$ |
| 3 | $14$ | $8$ | $1$ |
| 4 | $8$ | $128$ | $1$ |
| 5 | $15$ | $128$ | $10$ |
| 6 | $9$ | $128$ | $10^9$ |
| 7 | $12$ | $2048$ | $1$ |
| 8 | $20$ | $2048$ | $10^9$ |
| 9 | $6$ | $16384$ | $10^9$ |
| 10 | $4$ | $131072$ | $10^9$ |
提示
期望：对于离散型随机变量 $x$，其期望 $E[x]$ 定义为以概率为权，$x$ 所有可能取值的加权平均数，即
$$
E[x]=\sum_{k}Pr[x=k] \cdot k
$$
其中 $Pr[x=k]$ 表示 $x$ 取值为 $k$ 的概率。
t3 — 小 C 的矩阵
时间限制： 1.0 秒
空间限制： 1024 MiB
这是一道交互题。
题目描述
小 C 有一个 $n \times m$ 的 01 矩阵 $A$，他想让小 R 猜一猜，矩阵中最接近 $(n,m)$ 的 $1$ 在哪里。形式化地说，他想让小 R 猜出满足 $A_{i,j}=1$ 的最大的 $i+j$。小 C 保证了他的矩阵里至少有一个 $1$。
小 C 允许小 R 询问他一个子矩形内是否有 $1$。每次询问小 R 可以选定 $1 \le u \le d \le n,1 \le l \le r \le m$，小 C 将会告诉他 $\sum_{i=u}^d \sum_{j=l}^r A_{i,j}$ 是否非零。
小 C 不希望小 R 问他太多个问题，也不希望小 R 询问的子矩形过大。他决定统计小 R 询问的次数（记作 $c_1$），以及小 R 所有询问的 $\max(d-u+1,r-l+1)$ 之和（记作 $c_2$）。
你需要帮助小 R 问出满足 $A_{i,j}=1$ 的最大的 $i+j$，同时保证 $c_1,c_2$ 不超过小 C 的限制。当然，只要你的询问次数不超过 $10^6$，小 C 都会根据 $c_1,c_2$ 给出一部分的分数。如果你的询问次数超过 $10^6$，小 C 将会拒绝你之后的询问并直接判定你回答错误。
实现细节
你不需要，也不应该实现主函数，你只需要实现如下函数：
1 | int Find (int n, int m, int id); |
- $n,m$ 的含义如【题目描述】中所示，$id$ 表示该测试点所属的子任务编号。特别地，样例的子任务编号为 $0$。
- 你需要返回一个正整数表示满足 $A_{i,j}$ 的最大的 $i+j$。
你可以通过调用以下函数来和交互库进行交互：
1 | int Ask (int u, int d, int l, int r); |
- $u,d,l,r$ 的含义如【题目描述】中所示，你需要保证 $1 \le u \le d \le n$，$1 \le l \le r \le m$。
- 该函数返回一个非负整数 $0$ 或 $1$，返回值为 $0$ 代表该子矩形中没有 $1$，返回值为 $1$ 代表该子矩形中有 $1$。
评测时，交互库会恰好调用 Find 一次。
本题保证所使用的矩阵在交互开始之前已经完全确定，不会根据和你的程序的交互过程动态构造，因此题目中的交互操作都是确定性的，你不需要关心这些操作在交互库中的具体实现。
数据保证在调用次数限制下，交互库运行所需的时间不超过 0.1 s；交互库使用的内存大小固定，且不超过 80 MB。
实现方法
该题目录下已经提供了一个 sample_matrix.cpp，请将这个文件拷贝一份，重命名为 matrix.cpp，然后在其基础上答题。
请确保你的程序开头有 #include "matrix.h"。
你需要在本题目录下使用如下命令编译得到可执行程序：
1 | g++ -o matrix matrix.cpp grader.cpp matrix.h -static -O2 -std=c++17 |
对于编译得到的可执行程序：
- 可执行文件将从标准输入读入以下格式的数据：
- 输入的第一行包含三个正整数 $n,m,id$，含义如【题目描述】与【实现细节】中所示；
- 接下来 $n$ 行，每行包含一个长度为 $m$ 的 01 串，表示 $A_{i,1},A_{i,2},\dots,A_{i,m}$。
- 读入完成之后，交互库将调用恰好一次函数
Find，用输入的数据测试你的函数。你的函数正确返回后，交互库会判断你的计算是否正确，若正确则会输出Correct.和评分参数 $c_1,c_2$，否则会输出相应的错误信息。
试题目录下的 grader.cpp 是我们提供的交互库参考实现，最终测试时所用的交互库实现与该参考实现有所不同，因此选手的解法不应该依赖交互库实现。
样例输入
1 | 3 3 0 |
样例输出
1 | Correct. |
样例解释
以下是一种可能的交互过程：
| 选手程序 | 交互库 | 说明 |
|---|---|---|
调用 Find(3, 3, 0) |
||
调用 Ask(2, 3, 2, 3) |
返回 1 | $A_{2,2}+A_{2,3}+A_{3,2}+A_{3,3}=1 > 0$ |
调用 Ask(3, 3, 3, 3) |
返回 0 | $A_{3,3}=0$ |
调用 Ask(2, 2, 2, 2) |
返回 0 | $A_{2,2}=0$ |
| 返回 5 | 输出 Correct. |
$A_{2,3}=1,2+3=5$ |
输出 C_1 = 3, C_2 = 4. |
评分参数 $c_1=3,c_2=4$ |
子任务
| 子任务编号 | 分值 | $n=$ | $m=$ |
|---|---|---|---|
| 1 | $4$ | $2$ | $2$ |
| 2 | $20$ | $1$ | $4096$ |
| 3 | $76$ | $4096$ | $4096$ |
评分方式
对于每个子任务，该子任务得分为其中所有测试点得分的最小值。
对于所有测试点，若询问不符合要求或 $c_1 > 10^6$ 或答案不正确，得 $0$ 分。否则，将根据该测试点所属的子任务编号，按照评分参数 $c_1,c_2$ 分别给出分数 $s_1,s_2$，该测试点的最终得分为 $s_1+s_2$。
对于第一个子任务，$s_1,s_2$ 的计算方式如下：
| $c_1 \in$ | $s_1=$ | $c_2 \in$ | $s_2=$ |
|---|---|---|---|
| $(3,+ \infty)$ | $0$ | $(4,+\infty)$ | $0$ |
| $(2,3]$ | $1$ | $(3,4]$ | $1$ |
| $[0,2]$ | $2$ | $[0,3]$ | $2$ |
对于第二个子任务，$s_1,s_2$ 的计算方式如下：
| $c_1 \in$ | $s_1=$ | $c_2 \in$ | $s_2=$ |
|---|---|---|---|
| $(4096,+\infty)$ | $0$ | $(10^6,+\infty)$ | $0$ |
| $(2048,4096]$ | $2$ | $(10^5,10^6]$ | $1$ |
| $(1024,2048]$ | $3$ | $(5\times 10^4,10^5]$ | $2$ |
| $(160,1024]$ | $4$ | $(2\times 10^4,5\times10^4]$ | $3$ |
| $(80,160]$ | $5$ | $(10^4,2 \times 10^4]$ | $5$ |
| $(16,80]$ | $6$ | $(8192,10^4]$ | $7$ |
| $(13,16]$ | $7$ | $(6144,8192]$ | $8$ |
| $(12,13]$ | $8$ | $(4096,6144]$ | $9$ |
| $[0,12]$ | $10$ | $[0,4096$] | $10$ |
对于第三个子任务，$s_1,s_2$ 的计算方式如下：
| $c_1 \in$ | $s_1=$ | $c_2 \in$ | $s_2=$ |
|---|---|---|---|
| $(10^6,+\infty)$ | $0$ | $(10^9,+\infty)$ | $0$ |
| $(6\times 10^5,10^6]$ | $4$ | $(4 \times 10^7,10^9]$ | $3$ |
| $(3 \times 10^5,6 \times 10^5]$ | $6$ | $(1.7 \times10^7,4 \times 10^7]$ | $5$ |
| $(10^5,3 \times 10^5]$ | $7$ | $(2\times 10^6,1.7 \times 10^7]$ | $7$ |
| $(5 \times 10^4,10^5]$ | $9$ | $(10^6,2 \times 10^6]$ | $25$ |
| $(3.5\times10^4,5 \times 10^4]$ | $10$ | $(3 \times 10^5,10^6]$ | $29$ |
| $(2\times 10^4,3.5\times 10^4]$ | $13$ | $(2 \times 10^5,3 \times 10^5]$ | $31$ |
| $(1.3 \times 10^4,2 \times 10^4]$ | $15$ | $(10^5,2 \times 10^5]$ | $36$ |
| $(8300,1.3 \times 10^4]$ | $17$ | $(8 \times 10^4,10^5]$ | $46$ |
| $(8192,8300]$ | $19$ | $(7.4 \times 10^4,8 \times 10^4]$ | $50$ |
| $[0,8192]$ | $20$ | $[0,7.4 \times 10^4]$ | $56$ |
t4 — 小 C 的连廊
时间限制： 2.0 秒
空间限制： 1024 MiB
题目描述
小 C 有一块 $n \times m$ 的网格状草坪。由于风雨会使在草坪上行动不便，他计划在草坪上修建一些连廊。
这块草坪上的风向是固定的，而风速可以看做一个非负整数 $c$。对于风速 $c$，位于 $(x,y)$ 处的草坪可以经过当且仅当 $(x,y),(x,y+1),\dots,(x+y+c)$ 都已经修建了连廊。注意，当 $c=0$ 时，位于 $(x,y)$ 处的草坪可以经过也需要 $(x,y)$ 已经修建了连廊。
小 C 每次移动能从一块可经过的草坪移动到一条边相邻的另一块可经过草坪，即两块草坪能相互抵达当且仅当这两块草坪属于同一个可以经过的草坪构成的四连通块。
小 C 共有 $q$ 个计划，每个计划为以下两种之一：
- 修建计划：修建一条 $(x,y_l)$ 到 $(x,y_r)$ 的连廊，即在 $(x,y_l),(x,y_l+1),\dots,(x,y_r)$ 处的草坪上修建连廊。
- 出行计划：他想从 $(x_1,y_1)$ 处的草坪走到 $(x_2,y_2)$ 处的草坪。请你帮助他求出最大的非负整数 $c$，使得风速为 $c$ 时这两块草坪能够相互抵达；或者报告无论如何都无法互相抵达。
输入格式
从标准输入读入数据。
输入的第一行包含三个正整数 $q,n,m$。
接下来 $q$ 行，每行包含若干个正整数，表示一个计划：
- 输入的第一个正整数 $o$ 描述这个计划的类型。保证 $o \in {1,2}$。
- 若 $o=1$，接下来给出三个正整数 $x,y_l,y_r$，表示一个修建计划；
- 若 $o=2$，接下来给出四个正整数 $x_1,y_1,x_2,y_2$，表示一个出行计划。
输出格式
输出到标准输出。
对于每一个出行计划，输出一行一个整数，表示满足这两块草坪能够相互抵达的最大的风速 $c$。特别地，如果两块草坪无论风速如何都不能够相互抵达，输出 $-1$。
样例 1 输入
1 | 6 3 10 |
样例 1 输出
1 | 0 |
样例 1 解释
第一个出行计划中，当风速为 $0$ 时，小 C 可以沿 $(1,4)-(2,4)-(2,3)-(2,2)-(2,1)$ 的路径相互抵达；当风速大于 $0$ 时，$(2,4)$ 无法经过。
第二个出行计划中，当风速为 $2$ 时，小 C 可以沿 $(1,4)-(1,5)-(1,6)-(2,6)-(3,6)-(3,5)-(3,4)-(3,3)-(3,2)-(2,2)-(2,1)$ 的路径相互抵达；当风速大于 $2$ 时，$(2,2)$ 无法经过。
样例 2
见题目目录下的 2.in 与 2.ans。
该样例满足子任务 1 的限制。
样例 3
见题目目录下的 3.in 与 3.ans。
该样例满足子任务 4 的限制。
子任务
对于所有测试数据，满足 $1 \le n \le 10^5$，$1 \le m \le 10^9$，$1 \le q \le 3 \times 10^5$，$1 \le x,x_1,x_2 \le n$，$1 \le y_1,y_2,y_l,y_r \le m$，$y_l \le y_r$。保证修建计划的个数不超过 $10^5$，保证出行计划中 $(x_1,y_1),(x_2,y_2)$ 处的草坪均已修建连廊，保证 $(x_1,y_1) \ne (x_2,y_2)$。
| 子任务编号 | 分值 | 限制 |
|---|---|---|
| 1 | $15$ | $n \le 30$，$m,q \le 100$ |
| 2 | $21$ | 保证所有的出行计划在修建计划之后 |
| 3 | $30$ | 保证任意两个修建计划所修建的连廊不相连 |
| 4 | $34$ | 无 |
两个修建计划所修建的连廊 $(x,y_l,y_r),(x’,y_l’,y_r’)$ 不相连当且仅当 $x \ne x’$ 或 $y_r+1<y_l’$ 或 $y_r’+1 <y_l$。
Day-2 文件
合影
