A – 找位置
首先发现\(k\)非常的小，且\(n\)也较小，所以考虑直接暴力，枚举经过每一个超市的顺序，然后顺起来就行了（提前处理\(k\)次最短路即可）。
可以把整个思路转换为 CDQ 分治下的二位数点。\(x\)轴就代表正常的物理距离的轴，然后\(y\)轴就代表信号接收的轴，把一个询问拆掉成为容斥的形式即可。
这道题好有意思啊，提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。
我们可以先二分出\(c\)位置的值，然后令所有大于等于\(c\)的值变成\(1\)，小于的则变成\(0\)。然后排序的时候发现，其实就是重新组织零一的位置，所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。
这套题全都是暴力出奇迹系列。
我们枚举一个端点，然后判断以这个点为右端点是否能计入答案。我们把序列做个前缀和\(prefix[]\)，然后发现计入答案的条件当且仅当\(prefix[i – n]\)小于等于\([i – n + 1, i]\)的最小值。这样可以保证所有的前缀都能为非负数。
然后用 sb 线段树搞下就行了，太特么傻逼了。
首先，叶子结点为\(k\)时，整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。
考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点，且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移：
\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]
向新的节点加入统计数据：多了一个叶子结点，要么向左走，加深当前的路径；要么补上最后一个向左走的右节点。
然后就可以写代码了。