题面 传送门：洛谷 Solution 首先，长成这样的题目一定是淀粉质跑不掉了。 考虑到我们不知道K的大小，我们可以开一个splay来统计比某个数小的数的数量。 不会点分治的戳我 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545...

什么是淀粉质点分治？ 就是把分治搬到树上，以某个点为根，分别分治处理子树的答案，再计算子树与子树间的答案的玄学算法。 举个例子： 如何求出一颗树上距离为K且所经过的点最少的点对？ 对于这种题，我们可以把某个点（一般为重心）作为根，然后对左右子树递归处理，先分别得出左右子树的答案，再求出横跨两个子树之间的点对的答案。 为什么要学淀粉质 对于上面那道题，如果我们用传统的暴力做法，最优的复杂度只能...