[ABC355E] Guess the Sum 题解

前言

非常好交互题，使我的思维旋转。大概是最近几场 abc 里唯一一道比较值得带脑子做的 E 题。

思路

按照题意模拟后，可以画出一张允许被查询的区间的示意图：

你会发现这个东西长得跟线段树很像，但如果把线段树的递归查询函数照葫芦画瓢写上就会发现 WA 了三分之二的测试点，原因则是交互次数不能保证最优，比如说图里的 $[1,7]$ 实际上只用查 $[0,7],[0,0]$ 两次，用这种方法需要查 $[1,1],[2,3],[4,7]$ 三次。

上面的乱搞给了我们一个启示，那就是最优的询问次数很可能小于 $\log n$ ，从而我们可以推断，我们需要使用的询问方式并不是一种基于复杂度分析的通用策略（因为不管什么固定策略都不会比 $\log$ 的询问复杂度更优秀了），而是会根据输入动态调整的。此时可以开始考虑如何转化题意，使问题更加可做。

转化

看了官方题解的应该都知道是把询问转化成图上的边然后跑最短路，这里解释一下这样做的实际意义，便于理解。

我们可以利用一个比较经典的 trick，在差分约束算法的经典例题 Intervals 中就能见到，简单来讲就是把区间问题转化成前缀和上的问题。

假装我们已经知道了序列里下标为 $l-1$ 的前缀和，并且 $[l,r]$ 是一个可询问的区间，那么通过一次询问，我们就能知道 $r$ 的前缀和，反之亦然。于是可以把这种关系干到图上，对每个可询问区间 $[l,r]$ 都从 $l-1$ 向 $r$ 连双向边。由于每次询问的代价为 $1$ ，因此边权也全为 $1$ ，直接跑 bfs 求 $L-1$ 到 $R$ 的最短路即可。

实现

实现方面，我们可以用一个 from 数组记录使每个点到达最短路的边，这样方便我们求完最短路之后进行询问。同时对于每条边可以加上一个 id 值代表这条边是正边还是反边，如果是反边就在询问时减掉这次询问的结果，否则加上询问结果。同时因为本题下标从 $0$ 开始，可以直接改为从 $l$ 向 $r+1$ 连边再求 $L$ 到 $R+1$ 的最短路，否则 $l=0$ 时会访问到负下标。至于对区间 $[l,r]$ 的询问格式，推一个比较简单的式子即可，这里不再赘述，参见代码：link。