前言

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

思路

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

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

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

转化

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

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

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

实现

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