这个题还蛮有意思。
首先有个暴力，\(l\) 在 \(10^7\) 内可以直接 two-pointers；如果在 \(10^7\) 以上，那么发现 \(f(r) – f(l) \leq 1\)。那么我们可以考虑枚举这个连续段的长 \(L = x + y\)，其中 \(x\) 是 \(i\) 个 \(0\) 的部分，而 \(y\) 是 \(i + 1\) 个 \(0\) 的部分。有个等式：\(x \times i + y \times (i + 1) = (x + y)i + y = Li + y = S\)。所以枚举 \(L\) 的时候，如果 \(S \bmod L \equiv 0\)，那么说明 \(y = 0\)，你就把 \(10^i\) 内的左端点个数算出来（其实就是多减一个 \(L – 1\)）。如果 \(S \bmod L \neq 0\)，那么说明 \(x, y\) 确定了，那么就直接 ++ 即可。
Continue reading →好题好题。
我们发现每一个点向左、向右走都是有极限的，算出得到 \((x_i, y_i)\)，其中 \(x\) 代表左边、\(y\) 代表右边。那么，把这个东西放到散点图上，发现我们本质不同的操作是一个单调不降的折线图：因为如果我们把 \(x\) 作为这个路径的「最长向左移动距离」、\(y\) 作为这个路径的「最长向右移动距离」，那么这个折线经过某个点的 \(x\) 帧或是 \(y\) 帧都将导致这个东西 GG，所以我们计算这样的折线图就可以计算对应方案了。
我们可以直接用树状数组来进行转移即可。
这道题还蛮妙的，自己比较顺利的思考出来了。
考虑设置前缀异或和\(\{ S_i \}\)，根据异或按位处理的性质，显然对于所有的\(S_i\)都会小于\(2^n\)。最后，我们可以把限制变成：
针对\(x\)的大小关系，我们可以分成两种情况：
结合一下就可以了。
一眼可以了解到是一道割点题。对于不是割点的情况，那么被计算的点对一定包含此点本身，又因为有序，所以贡献就是\(2(n – 1)\)。如果是割点的话，就比较麻烦，分下面几个来算：
第一个很好算，是\(2(n – 1)\)。第二个，在 Tarjan 枚举搜索子树的时候计算子树大小和全图补集的乘积（注意，这里会多计算一遍与点\(u\)的点对，所以我们第一个改成算\(n – 1\)）；第三个，算「当前整颗搜索树与图的补集大小」与「搜索树的大小」的乘积。
综合起来就是，对于点\(u\)：
\[ ans_u = \sum_{k \in son(u)} (n – size(k)) \times size(k) + (n – 1) + (n – 1 – \sum_{k \in son(u)} size(k)) \times (1 + \sum_{k \in son(u)} size(k)) \]
kal0rona 越来越 sb了。
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：