这里肯定考虑每个点作为lca对答案的贡献
考虑点\(p\)，所代表的区间长度为\(l\)，那么其左右两个子树的叶子节点一定至少选一个，即贡献为$$p \times (2^{\lfloor \frac{l}{2} \rfloor}-1)\times (2^{\lceil \frac{l}{2} \rceil}-1)$$，其中\(\lceil \frac{l}{2} \rceil\)和\(\lfloor \frac{l}{2} \rfloor\)分别为左右子树的长度，减一是因为要去掉一个叶子都不选的情况
然后有一个结论，线段树每层的不同区间的长度至多相差一
考虑用数学归纳法证明，假设对第\(i\)层，长度为\(l\)和\(l-1\)，那么第\(i+1\)层的长度就是\(\lfloor \frac{l}{2} \rfloor,\lceil \frac{l}{2} \rceil,\lfloor \frac{l-1}{2} \rfloor,\lceil \frac{l-1}{2} \rceil\)，根据\(l\)的奇偶讨论即可
那么我们储存每一层的区间的长度，以及每一种区间长度的区间的个数，以及对应的节点的编号和
举个例子，假设线段树的根节点的长度是\(5\)，处于第一层，那么第三层就有四个节点，分别为\((4,[1,2]),(5,[3,3]),(6,[4,4]),(7,[5,5])\)，我们就统计长度为\(2\)的区间有一个，编号和为\(4\)；长度为\(1\)的区间有三个，编号和为\(18\)
那么我们推导下一层的对应信息，就先算出下一层的长度以及对应的区间个数，那么编号和显然一个乘以\(2\)另一个乘以\(2\)再加上区间的个数，可以自己推导一下
这里的推导也启示我们，不用非要记录最终的结果，我们记录结果的每个因子也是可以的
时间复杂度为\(O(log^2n)\)
代码一定也看一下，用了map的迭代器
标签：,lfloor,lceil,frac,区间,长度,rceil From： https://www.cnblogs.com/dingxingdi/p/18033136