https://www.luogu.com.cn/problem/P14638
考场上写了个 \(O(nq\log)\) 的猫树分治。我发现这个东西可以过 \(L=R\) 的所有点，场上我以为只是因为常数小，后来想一想才发现当 \(L=R\) 时这个东西就是线性的。进一步地，当 \(2L\ge R\) 时这个东西也是线性的。所以考虑预处理出所有 \([2^k,2^{k+1})\) 的答案，查询的时候散块部分就满足 \(2L\ge R\)，然后就 \(O(nq)\) 了。
https://qoj.ac/contest/2559/problem/14419
首先考虑求最大子段和不超过 \(k\) 的方案数。
你相当于要做 \(s\gets \max(s+a_i,0)\) 这种过程。如果没有这个取 \(\max\) 是很好做的，一组合法的方案等价于一条从 \((0,0)\) 开始，不经过 \(y=k+1\) 的折线。但是有了这个取 \(\max\) 之后会多一个从 \(0\) 到 \(0\) 的转移，这看起来不太符合折线的性质了。
结论：一组合法的方案等价于一条从 \((0,0)\) 开始，不经过 \(y=k+1\) 和 \(y=-k-2\) 的折线。
证明：考虑把 \((x,0)\) 到 \((x,-1)\) 或 \((x,-1)\) 到 \((x,0)\) 的一条线段看成从 \(0\) 到 \(0\) 的转移，然后沿 \(y=-0.5\) 把坐标系对折，然后方案显然就一一对应了。
然后反射容斥。
