CodeForcesLuogu分析比较简单的点分治。可是我调了好久先考虑一个简单版的题目:Tree。那道题统计答案是用的双指针。但是这道题多了一个 $L$ 的限制,所以在双指针满足 $W$ 的限制的同时,再用一个树状数组来满足 $L$ 的限制就行了。具体实现及细节见代码。代码// ================================= // author: M_sea // ...
Luogu算法点分治裸题。先考虑暴力做法。在【模板】点分治1的基础上从1到k循环统计一遍答案即可。考虑对暴力做优化。发现算法的主要瓶颈在calc函数内,我们考虑把它从$O(n^2)$降至$O(n\ \log\ n)$。直接排序然后 $\mathrm{two-pointers}$ 即可。细节见代码。代码#include <bits/stdc++.h> #define re regi...