[学习笔记] 这就是交互题

(gdb) b 20

Breakpoint 1 at 0x5aad: file name.cpp, line 20.

同理 , 可以用类似的表示法不切换当前文件设断点 .

(gdb) b name.cpp:20

Breakpoint 1 at 0x5aad: file name.cpp, line 20.

申必技巧

可以复制一份 grader.cpp , 参考洛谷对交互题的实现方式 : 把 #include"name.h" 换成对 grader 提供的函数的定义如 void Func (); , 然后把 grader 提供的函数放在代码的最后 , 前面是选手代码的实现 .

这样和多文件编译没有本质区别 , 注意区分不同来源的函数 . ( 可以看成一个 "自对拍" 之类的程序 )

提交的时候别忘了改格式 , 把前面的定义函数换回 include , 然后把 grader 提供的部分删掉 .

这样的好处是调试比较符合习惯 , 坏处就是提交容易爆 , 别忘了放进 SelfEval 测一下 .

如果你非得在 Windows 下搞多文件编译也没有问题 . 虽然在我的印象里 Dev-C++ 的 MinGW 是内封装的 , 但是在机房随机开了几台电脑试了一下 , 好像都是有 MinGW 的 , 所以直接用 cmd 或者 powershell 就行 ( powershell 里可以用 bash 命令的 , 所有操作和 bash 里等价 ) .

如果你非得在 Dev-C++ 下搞多文件编译就有问题了 . 不知道能不能通过编译选项解决 .

这需要我们在 Dev-C++ 中建立项目 (控制台程序console project) , 然后把我们的 .cpp 与 .h 文件导入到项目 .

然后打开 grader.cpp 编译即可 .

正确的运行 .

如果无下发文件或者 grader 码风比较加密 , 你可以自己写 grader , 一般不会涉及过于复杂的代码 , 但是前一种情况下别忘了骂出题人 .

自适应性

如果一个交互程序有自适应性 , 说明它会根据选手程序的操作 , 在不产生自相矛盾的情况下 , 动态构造数据 . 一般自适应性的目的就是卡随机做法 , 这类题目一般需要确定性做法 .

相反 , 不具有自适应性的题目允许期望操作数合理的解法 .

其他注意事项

样例提供的 grader.cpp 与实际评测时使用的 grader.cpp 可以不同 , 一般情况下后者会更强 .

注意样例可能不符合数据范围中给定的值 , 一般也比较弱 .

最好备份好下发文件 , 以防把 grader.cpp 调坏 .

如果是比赛不要过于信任SelfEval .

一般问题 : 最小化操作数

在限制的操作次数下完成操作/查询 .

一般算法背景比较淡 , 不妨提出一些 "想法" :

特殊情况

找性质

最大化信息量

二分

分治

拆分子操作

构造

随机

均摊

热身题-CF2078E

有两个非负整数 \(x,y\) $ (0\le x,y<2^{30}) $ , 询问由选手程序发出 , 每次询问给出一个非负整数 \(n\) \((0\le n <2^{30})\) , 交互程序返回 \((n|x)+(n|y)\) .

要求使用不多于 \(2\) 次操作 , 求出 \((m|x)+(m|y)\) , 其中 \(m\) 由交互程序给出 .

考虑比较特殊的询问 , 询问 \(n=0\) 可以得到 \(x+y\) . 但是这里是加法 , 进位导致 \(x+y\) 反映不了太多我们需要的信息 .

那么还能有什么比较特殊的询问呢 ?

发现返回信息里的加法比较讨厌 , 会产生进位打乱信息 , 考虑查询一个 \((1010\cdots10101)_2\) , 覆盖偶数位 , 此时两个数偶数位必然都取一 , 减去这部分就可以得到两个数奇数位的和 .

而只取奇数位的好处是即使进位 , 也会落在我们空出来的偶数位上 , 奇数位间两两是互不影响的 , 这样就可以求出每个奇数位上 , 两个数总共取了 \(0/1/2\) 个 \(1\) .

同理可以求出偶数位的 , 单独查询还是用 \(n=0\) 求完 \(sum\) 再减都行 .

而我们的答案只关注每个位有多少个 \(1\) , 不关心具体属于 \(x\) 还是 \(y\) . 于是解决 .

基础题-[APIO2016] 最大差分

有一个长度为 \(N\) 的递增序列 \(a\) , 值域为 \([0,10^{18}]\) .

查询差分数组的最大值 , 即 \(a_i-a_{i-1}\) 的最大值 .

你可以调用 void MinMax(s, t, &mn, &mx) , 交互程序会把所有满足 \(a_i\in[s,t]\) 的 \(a_i\) 中最小值和最大值分别写入 \(mn\) 和 \(mx\) .

\(N\le10^5\)

sub1 : 调用次数不超过 \(\frac{N+1}{2}\) .

sub2 : 设每次调用中满足 \(a_i\in[s,t]\) 的 \(a_i\) 个数是 \(cnt\) , 要求 \(\sum (cnt+1) \le N\times 3\) .

sub1

非常简单 , 考虑对整个值域可以取出全局最大 , 最小值 , 然后把值域设定为 \([mn+1,mx-1]\) , 就可以读出整个数组 , 直接差分即可 .

sub2

考虑能得到的信息 , 也只有取出一个 \(mn,mx\) 先 , 代价 \(n+1\) .

剩下的操作 , 我们对每个数只能 \(O(1)\) 次覆盖 , 这提示我们恰好覆盖整个值域一次 , 那么来自于 \(cnt\) 的贡献就是 \(n-2\) , 那么来自于操作次数的贡献最多只能是 \(n+1\) .

显然 , 把值域均分成 \(n+1\) 段是最合理的办法 . 根据抽屉原理 , 答案不可能 \(<\frac{W}{n-1}\) , 因此答案不可能来自段内 , 因此这样查询就可以得到最大值 .

基础题-[APIO2017] 考拉的游戏

给出 \(N,W\) 和一个从 \(1\) 到 \(N\) 的排列 \(P_0\cdots P_{N-1}\) ( 注意下标! ) .

可以进行游戏 , 每次游戏 , 你先手在位置 \(0\cdots N-1\) 上放石子 , 每个位置可以放任意多 , 总数不超过 \(W\) , 然后 koala 后手放石子 , 每个位置可以放任意多 , 总数不超过 \(W\) . 最后 koala 放置的石子数严格大于你放置的石子数的位置 \(i\) 上的权值 \(P_i\) 属于 koala . koala 会尽可能最大化他得到的权值 , 在此基础上最大化得到的位置数 , 并在所有最优决策中选择一个 .

定义函数 void playRound(*B, *R) , 初始数组 \(B_0\cdots B_{N-1}\) 下要给出你在每个位置上放的石子数 , 然后调用函数 , 结束后数组 \(R_0\cdots R_{N-1}\) 会返回 koala 在每个位置上放的石子数 .

设每一次询问调用上述函数的次数为 \(C\) , 要求解决如下询问 :

sub1

minValue(N, W) 这个函数需要返回权值最小的物品的标号 \(i\) .

\(C\le 2,N=100,W=100\) .

很简单 . 考虑最特殊的 , 随便找个地方扔一个 \(1\) , 有且只有一个物品拿不到 , 不拿的显然就是最小的 .

sub2

maxValue(N, W) 这个函数需要返回权值最大的物品的标号 \(i\) .

\(C\le 4,N=100,W=100\) .

考虑一个最简单的 , 所有都放 \(1\) , 可以区分出 \([1,50]\) 和 \([51,100]\) .

考虑继续缩小类似 \([51,100]\) 的区间直到变成 \([100,100]\) .

发现我们在 \([51,100]\) 放上一个数 \(t\) , 其余放 \(0\) , 相当于降低了它们的权重 , 其中足够强的留下 , 相当于缩小区间 .

那么这个过程就是 :

\([51,100] ,t= 2\to [76,100]\)

\([76,100],t=4 \to [92,100]\)

\([92,100],t=11\to[100,100]\)

正好 \(4\) 次 , 大概也算是一种构造 .

sub3

greaterValue(N, W) --- 这个函数需要比较物品 \(0\) 和物品 $ 1$ 的权值，返回权值较大的物品的标号。具体来说，若\(P_0>P_1\)，它应该返回 \(0\) ，否则返回 \(1\) .

\(C\le 3,N=100,W=100\) .

有了刚才的思路 , 仍然考虑通过调整权重 \(t\) , 目的是让较大的选 , 而较小的不选 .

可以二分 , 如果都选上了说明 \(t\) 小了 , 如果都不选说明 \(t\) 大了 .

发现当 \(t=8\) 的时候 , 不可能选到较小的 , 所以上界是 \(8\) ( 讲的时候现场证明 ) .

发现直接二分最差情况下需要 \(4\) 次 .

发现有的二分位置是不必要的 , 比如如果在 \(t=7\) 合法 , 那么至少在 \(t=8\) 和 \(t=6\) 间有一个合法 , 这种宽松性在后面还会得到说明 .

因此二分最多只会进行 \(3\) 次 , 事实上更加不精细的实现也可以通过 .

sub4

allValues(N, W, P) --- 这个函数需要确定整个排列，并将其存放在给定的数组 P 中 .

\(C=700,N=100,W=200\) .

因为刚才我们得到了两两比较的方法 , 所以考虑套到 std::sort 里 . 需要特别注意 \(W=200\) , 那么只要在两个数的位置上各放 \(100\) 即可 , 必然选一个不选另一个 , 只需一次就可以 .

注意 sort 内部实现比较混乱邪恶 , 为了常数优化 , 会在排序的最后几层用常数更小的插排 . 这会爆掉操作数 , 因此使用 stable_sort 就没那么多事 .

属于是奖励关 .

sub5

allValues(N, W, P) --- 这个函数需要确定整个排列，并将其存放在给定的数组 P 中 .

\(C=100,N=100,W=100\) .

首先 \(sort\) 死光光了 . 应该有一个笼统的直觉 , 一次查询的信息量应该远远大于只用它来实现类似 \(sub3\) 地两两比较 , 因此考虑整体解决 .

采取 \(sub2\) 里缩小区间的办法 , 发现如果我们能不断分开任意区间 \([l,r]\) , 就可以 \(O(N)\) 地建出一颗 leafy tree , 并且把每个下标分配到一个叶子上 , 也就得到了结果 .

考虑操作 \([l,r]\) ,注意到可以不管 \([r+1,n]\) 的部分 , 不扔数上去 , 这些数必然会选 , 相当于只对 \([1,r], n'=w'=r\) 考虑 . 我们需要找到一个给 \([r+1,n]\) 的权重 \(t\) , 让这个区间有数选有数不选 .

结论是这样的权重必然存在 ( 现场证明 ) .

这样就解决了这道题 .

基础题-[NOI2024] 百万富翁

有一个 \(P_0\cdots P_{N-1}\) 的序列 , 保证两两不同 , 选手程序需要求出 \(P_k\) 最大的下标 \(k\) .

选手程序可以调用以下函数 :

vector ask(vector a,vector b);

其中 \(a\) 和 \(b\) 是两个长度为 \(s\) 的下标序列 , 返回的序列 \(c\) 中 \(c_i\) 表示 \(a_i\) 和 \(b_i\) 中对应的 \(P\) 值较大的下标 .

用 \(T\) 表示上述函数的调用次数的上限 , \(S\) 表示所有调用的 \(\sum s\) 的上限.

有两问 : sub1 , \(N=1000,T=1,S=499\ 500\) .

sub2 , \(N=10^6,T=8,S=1\ 099\ 944\) . ( 这里给出的是得到满分需要达到的限制 ) .

交互库具有自适应性

sub1

\(N=1000,T=1,S=499500\) .

白送 15 分 , 只需两两查询即可 , \(S\) 恰好可以装下 \(\begin{pmatrix} 1000\\2\end{pmatrix}\) .

sub2

\(N=10^6,T=8,S=1\ 099\ 944\)

首先可以想到普通的一个二叉树式的两两比较 , 可以得到理论最小的 \(\sum s\) , 但是调用次数过多 . 最朴素的实现可以得到 11 分 .

我们需要一次进行更多比较 , 考虑引入三个数比较 , 因为交互库自适应 , 因此想取出集合 \(R\) 的 \(\max\) , 必须要查询 \(\begin{pmatrix} |R|\\2\end{pmatrix}\) 次 . 那么三个数比较就需要 \(3\) 次 .

在两两比较和三个数比较间手动调整可以获得 20~30 分 .

我们找到一些调整的方法 , 一次比较的个数 \(k\) 越小 , 平均到每个元素的比较次数越小 , 但是调用次数越多 .

因此一定是前几次调用从前到后 \(k\) 递增 .

进一步可以发现 , 假设上一层待比较的个数为 \(g_1\) , 到下一层为 \(g_2\) , 那么中间一定是平均分配最优 , 即 $k=\left \lceil \frac{g_1}{g_2} \right \rceil,\left \lfloor \frac{g_1}{g_2} \right \rfloor $ , 这样就总结出了一套构造策略的思路 , 在这个基础上调整策略 , 可以得到 50~60 分 .

考虑上面的方法让最后的 \(\sum s\) 只取决于决策序列 \(g\) , 考虑把这个 \(g\) 序列 dp 出来 .

如果直接暴力 dp , 复杂度是 \(O(N^2T)\) , 至少在场上的时间里跑不出来 .

发现前几层显然两两是足够优的 , 因此钦定前几项为 \(1000000,500000,250000,125000\) , 这样单层的状态数大约为 \(10^5\) 级别的 , 同时后面状态的上限分别是 \(62500,31250,15625,7813,1\), 把剪枝加上去 , 大约 1 分钟就能跑完 .

跑完后发现最小操作次数恰好是 \(1099944\) , 因此限制还是很严格的 .

使用模拟退火可以更快地找到可行序列 .

基础题-[JOISC 2024] 环岛旅行

有一棵大小为 \(N\) 的树 . 给出函数 int query(int u,int k) , 返回树上除 \(u\) 之外离 \(u\) 第 \(k\) 近的点 ( 树上距离为第一关键字 , 编号大小为第二关键字 ) . 最多允许调用上述函数 \(L\) 次 , 要求还原出树的 \(N-1\) 条边 .

\(N\le 300,L\ge2N\)

考虑最特殊的 \(k=1\) 的询问 , 可以得出很多确定的边 , 但是剩下的边的性质不算明显 .

还有一个性质 , 跟 \(u\) 有边的 \(v\) 肯定是前 \(k\) 近的若干个点 .

考虑对 \(u\) 把所有有边的 \(v\) 求出来 , 关键在于 check 出第一个不是直接与 \(u\) 有边相连的 \(v'\).

注意到如果把 \(u\) 视作根 , 那么 \(v'\) 就是最小的 \(dep=2\) 的点 , 必然和 \(dep=1\) 的某个点 \(v_0\) 相连 .

那么 \(v'\) 应该就是 $query(v_0,1) $ , 不过可能出现 \(query(v_0,1)=u\) 的情况 , 那么我们从大到小枚举 \(u\) 就可以解决了 .

基础题-LOJ#6669 Nauuo and Binary Tree

Nauuo 是一个喜欢二叉树的女孩子。

这天，她创造了一个有 \(n\) 个节点的二叉树。节点的编号从 \(1\) 到 \(n\)，其中 \(1\) 是二叉树的根节点。

不过，她不记得这棵二叉树具体长什么样子了，她只记录了二叉树上任意两个节点之间的距离。你可以通过向她询问有关距离的信息来还原这棵二叉树，两个节点之间的距离定义为它们之间最短路上的边数。

你可以向 Nauuo 询问不超过 \(30000\) 次有关距离的信息。你只需要告诉她 \(2\sim n\) 号节点的父亲的编号就可以了。

这道题大家比较熟悉 . 直接给出 : 使用树剖优化 .

先搞出所有点的深度.

考虑对链尾查询就可以得出这个点切轻边的位置 . 加上树剖的小肠数就可以过 .

考试题-[NOI2019] I 君的探险

一张 \(N\) 个点、\(M\) 条边的无向简单图从 \(0 \sim n - 1\) 编号。目前你并不知道边有哪些。

每个点有权值 \(s_i\) , 初始 \(s_i=0\) . 可以进行以下操作 :

modify(x) 给定一个编号 \(x\) , 把 \(x\) 以及与 \(x\) 号有边直接相连点的 \(s_i\gets s_i \ \mathrm{xor} \ 1\) .

query(x) 给定一个编号 \(x\)，返回当前的 \(s_x\) .

report(x, y) 给定两个编号 \(x, y\)，表示你确定有一条连接 \(x\)与 \(y\) 号边，并让交互程序记录 .

check(x) 给定一个编号 \(x\)，返回与 \(x\) 相连的边是否都已被记录 .

每种操作的使用次数都有限制，分别为 \(L_m, L_q, M, L_c\) . 要求在限制次数内用操作 3 返回图中所有的边 .

注意原题面反复强调了交互库不是自适应性 .

下面默认 \(N=2\times 10^5\) , 原题中给出了更复杂的测试点设计 , 下面只以 \(2\times 10^5\) 作为举例讲解特殊性质 .

sub1

\(L_m=19N, L_q=19N, M=\frac {N}{2}, L_c=0\)

保证每个点的度数都为 \(1\) .

算得上是全题的基础 . 考虑基本的调整一个点 , 全局查询所有与它有边的的点过于浪费操作次数 .

因此我们考虑分治 , 求出每个点的配对点 .

假设我们当前有一个配对点的可选集合 \(S\) , 对它的任意一个子集 \(T\) 做一轮修改 , 然后查询所有点 , 就可以得出所有点的配对点是否属于子集 \(T\) , 也就完成了对 \(S\) 的分治 .

如果我们每次均分 \(S\) , 就相当于整体二分 , 可以通过 .

但是有更简单的实现 , 考虑二进制分组 , 每次点亮在第 \(k\) 位为 \(1\) 的点 , 就可以逐位确定每个点的配对点 . 本质上和整体二分没有差别 .

这个东西有更通用的意义 : 一个点的相邻所有点的异或和 .

sub2

\(L_m=19N, L_q=19N, M=N-1, L_c=0\)

保证形成一棵树 , 而且可以视作满足任意点 \(u\ne1\) , \(fa_u

考虑一个点的相邻所有点的异或和 . 对于一度点 , 这就是它的父亲 .

而这棵树的拓扑序是确定的 , 因此从大到小逐一确定父亲就好了 .

sub3

\(L_m=10^7， L_q=10^7, M=N-1, L_c=2M\)

保证形成一棵树 .

这次不知道拓扑序了 .

考虑仍然逐一确定父亲 , 假设当前点是一度点 , 那么它邻点的异或和就是它的父亲 . 可以 \(O(1)\) 次操作它相邻点的异或和是否是它的父亲 , 如果是的话就找到了一条边 .

这个过程事实上相当于把拓扑序构造出来 . 因此除了首先对每个点都尝试一下这个过程 , 剩下的只需要按照拓扑排序的思路 , 不断把每次成功找到父亲的点对应的父亲放到队列里查询 , 操作数是 \(O(N+M)\) .

注意哪怕当前不是叶子也可能找到边 , 但是这种情况并不影响正常的拓扑过程 , 也不影响复杂度 .

sub2.5

\(L_m=10^7， L_q=10^7, M=N-1, L_c=2M\)

保证形成一个链 .

这里可以把所有点都操作求一下度数 , 然后找出一度点 , 就相当于得到了拓扑序 .

因为感觉思维连续性不太好就没单拿出来 .

sub4

\(L_m=10^7， L_q=10^7, M\le 3\times 10^5, L_c=2M\)

没有额外限制 .

提示 : 正解与部分分没有必然联系 ; 题目反复强调了交互库不自适应 .

考虑在刚才的树基础上做这道题 , 我们可以尝试通过重编号 , 类似于 sub2 , 随机出一个拓扑序 .

但是形成的并非树结构 , 而是一个 DAG . 我们转到树上的操作并没有获得收益 .

事实上就是目前没有看到题解能基于树性质做这道题 , 所以是时候把树和拓扑序从脑子里扔掉了 ( 当然如果你能想出这个角度的做法那我请你吃麦当劳 )

我们发现当前的问题是 , 一直以来我们在使用异或和作为信息 , 然而在不保证稳定的一度点的情况下 , 异或和信息的用处不大 .

因此我们回到 sub1 , 找回整体二分的思路 , 并且找到这个思路的扩展性 .

假设每个点与待定集合 \(|S|\) 中有多条边 , 选出 \(T\) 子集 , 操作 \(T\) 集合并查询所有点 , 得到的是每个点 \(u\) 到 \(T\) 的边数的奇偶性 , 假如这个数是 \(1\) , 也就是奇数 , 那么 \(T\) 子集必然到 \(u\) 有边 ; 否则 , 假如 \(u\) 到 \(S\) 的边数为奇数 , 那么 \(T\) 的补集必然到 \(u\) 有边 .

因此 , 这个整体二分可以保证 , 对所有度数为奇数的点 , 稳定地求出一条邻边 .

显然 , 这个策略在所有点都是偶数度数时会失效 . 我们需要引入一些变化 .

( 或许是借着拓扑序的想法 ) , 给每条边定向 , 让每条边由权值较大的点访问到 , 这样保证了哪怕全偶度数 , 也可以通过调整定向来构造出奇度点 . 然后不断 shuffle 权值 .

实现上 , 可以让所有操作都从权值从小到大进行 , 然后在线查询 , 就可以实现这个定向 .

考虑一下复杂度 , 对于 query 操作 , 我们可以只对奇度点操作 , 每次稳定用 \(O(\log N)\)拿到一条边 , 次数是 \(O(M\log N)\) .

对于 modify 操作 , 仍然可以进一步优化 , 考虑每次找到一条边就用一次 check , 可以做到始终只保留有边的点 .

在这种情况下 , 考虑奇度点期望能有多少 , 也就是期望找到多少条边 . 这里不严谨地认为每个点是否是奇度点独立 , 那么一个度数为 \(d_u\) 的点成为奇度点的概率是 \(\frac{d_u/2}{d_u+1}\) , 最差为 \(\frac{1}{3}\) , 因此每次期望用 \((N'\log N')\) 时间找到 \(O(N')\) 条边 , 期望每条边是 \(O(\log)\) 的 .

奇怪做法

根据数据范围可以看出图很稀疏 , 同时如果用逆向思维 , 考虑交互程序怎么写 , 发现图邻域是很难维护的 , 所以大概率真正的 grader 也是写暴力 , 因此甚至连稠密子图都不应该出现 .

这个观察有两个意义 :

它证明了上述做法在常数方面的可行性 .

这提供了又一个思路 . 假设我们没有想到整体二分 , 只有异或和信息 , 那么我们只能不断地得到一度点 . 但是因为图的稀疏性质 , 可以乱搞 : 取出一个大小为 \(B\) 的点集 , 把所有连向这个点集中 , 边数恰好为 \(1\) 的点统计出来 . 不断随机点集直到所有边都被发现 .

luogu 其中一篇题解提到在 \(B=\frac{n}{100}\) 时该算法可以通过 .

考试题-andrew

有一个 \(N\) 个点的无向图 , 要求判断是否具有以下性质 :

存在两两不同的 \(x,y,z\) 三点 .

满足边 \((x,y)\) , \((y,z)\) 存在 ,边 \((x,z)\) 不存在 .

对于不是 \(x,y,z\) 的点 \(u\) , 满足边 \((u,x)\) 存在 , 边 \((u,y)\) , \((u,z)\) 不存在 .

你可以调用 query(u,v) 不超过 \(Lim\) 次 , 返回边 \((u,v)\) 是否存在 .

\(N\le 10^6,Lim=N\times 5\) .

出题人把这个形状称为 "蝎子" .

查询其实没有什么太玄妙的 , 能得到更多信息的东西 , 只能先查询一个点连接的所有边 , 考虑下一步怎么做 .

考虑在这个点有一些特殊性的时候我们可以讨论出来 , 设查询 \(u\) , 度数为 \(d_u\) , 与它有边的点是 \(v_1\cdots v_{d_u}\) :

若 \(d_u=1\) ,

如果 \(u\) 是 \(z\) , 那么 \(v_1\) 就是 \(y\) , 其度数为 \(2\) , $ y$ 连接的另一个点就是 \(x\) .

否则 \(v_1\) 只能是 \(x\) .

若 \(d_u=2\) ,

如果 \(u\) 是 \(y\) , 那么它分别连着 \(x\) 和 \(z\) .

否则 \(v_1\) 或 \(v_2\) 中有一个是 \(x\) .

若 \(d_u=n-1\) , \(u\) 就是 \(x\) .

考虑上面几种情况的操作数 , 首先 , 可以 \(N\) 次验证出一个点是否是 \(x,y\) 或 \(z\) .

其次 , 如果我们确定了 \(x,y\) 或 \(z\) 中的一个 , 需要 \(N\times 2\) 次来确定图是否合法 .

那么上面几种情况的操作数都不超过 \(N\times 5\) .

剩下的情况里 \(u\) 都确定是一个普通点 , 这些情况又该如何应对呢 ?

考虑这种情况下我们已有的信息 : 一部分点与 \(u\) 有边 , 一部分没有 , 把这两个点集分别称为 \(S_1\) 和 \(S_0\) .

考虑它们的构成 .

有边点集 \(S_1\) : \(x\) , \(V_1\) ( 表示与 \(u\) 有边的普通点 ) .

无边点集 \(S_2\) : \(y\) , \(z\) , \(V_0\) ( 表示与 \(u\) 无边的普通点 ) .

它们之间的连边情况如图 . 黑边表示必然有边 , 绿边表示可以有边 .

现在我们应该致力于把 \(x,y\) 或 \(z\) 中的一个可能点找出来 , 找出后仍然需要 \(3N\) 来分别验证 \(x,y,z\) ( 因为我们显然不能在这个过程中把我们要的点的邻域取出来 ) , 我们有 \(N\) 次机会 .

通过观察这个图找出 \(z\) 具有特殊性 : \(z\) 是 \(S_0\) 中唯一一个和 \(S_1\) 无边的点 .

同理 \(x\) 具有弱一些的性质 : \(S_1\) 唯一一个和 \(S_0\) 中除了 \(z\) 以外所有点都有边的点 .

因此我们可以不断找上下两个点 \(u_1,u_0\) 查询一次 :

如果有边 , \(u_0\) 不可能是 \(z\) , 排除 \(u_0\) .

如果无边 , 那么 \(u_0=z\) 或者 \(u_1\ne x\) . 其中 \(u_0=z\) 属于特殊情况 , 不妨认为 \(u_1\ne x\) 并把它排除 .

假如真的 \(u_0=z\) 且 \(u_1=x\) , 那么即使排除 \(x\) 也无所谓 , 因为当前的 \(u_0\) 会不断把所有 \(S_1\) 排除 , 并且得到我们希望的 \(z\) .

这可以理解成一个打擂台的过程 , 结果一定是 \(S_1\) 变成空集 , 此时的 \(u_0\) 就是 \(x\) . 因为排除了不超过 \(N\) 个点 , 所以操作数是合法的 .

附加题-CF1372F

本来真不想额外写题解了 , 怒做此题一晚上 3 小时 , 红红又温温 .

有一个隐藏的长度为 \(n\) 的序列 \(a\) , 保证 \(a_i\in [1,10^9]\) 且 \(a\) 序列单调不降 . 你需要还原这个序列 .

每次可以询问区间 \([l,r]\) 的众数的 数值 \(x\) 和 在区间内出现次数 \(f\).

设 \(a\) 内部有 \(K\) 种不同的值 ( 注意 \(K\) 值并不给定 ) , 那么限制次数就是 \(4K\) , 交互库会在超出限制时结束程序 .

\(n\le 10^5,K\le 2.5\times 10^4\) .

首先来句闲话 , 这个数据范围显然是因为交互库的区间众数是 \(\sqrt n\) 的 .

然后显然我们第一次查询是 \([1,n]\) 查询 .

考虑对每个 "发现" 的数字都直接求出它在原序列对应的区间 \([L,R]\) , 这样就可以分治 , 并且保证已经处理完的部分不会再贡献复杂度 .\

设当前我们处理 \(x,f\) .

发现我们可以把序列按 \(f\) 分块查询 , 肯定能遇到一块众数是 \(x\) , 而且用这一块就可以读取出 \(x\) 的具体区间了 .

但是每次都查询显然很不优 , 我们期望能复用找到 \(x\) 之前的那些查询的信息 .

目前的形式复用并不方便 , 把之前的方法等价转换一下 .

我们可以隔 \(f\) 进行单点查询 , 必定能找到一个 \(x\) , 然后对其左右的长为 \(f\) 的区间查询就好了 .

而单点查询的信息显然复用起来很容易 .

如果认为每个 \(x\) 单点查询只被查询一次 , 那么发现所有 \(x\) 的开销是 \(K\) , 单点查询的开销是 \(K\) , 左右查区间的开销是 \(2K\) , 正好 .

现在还有最后一个问题 , 虽然我们实现了复用 , 但是 \(x\) 仍有可能被查重 .

发现我们可以限制单点查询从 \(x\) 的前驱开始 , 这样就保证了不会查重所有 \(x\) 的也不可能查重 .

燃尽了 .//