P6881 [JOI 2020 Final] 火事
题意转化：求 \(\sum_{i=l}^{r} \max_{j=i-t}^{i}\{a_j\}\)。
考虑离线，询问按 \(t\) 从小到大排一遍，思考什么时候 \(a_i\) 的值会改变。我们可以找到 \(a_i\) 前第一个比它大的值的位置 \(l\) 和后面第一个比它大的值的位置 \(r\)。那么当 \(t \ge (l-i)\) 时 \(a_l\) 会对 \([i,r-1]\) 的 \(a\) 会有一个按时间增加不断向后覆盖的贡献，而 \(t < r-l\) 时这个贡献便会停止往后覆盖。考虑用线段树维护贡献的加减，我们对于不同的覆盖情况分讨一下，最后容斥一下即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF283E Cow Tennis Tournament
傻逼题，赛事出题人把这道题放最后一道，赛时灵光一现这个做法时感觉不会这么简单，然后其实是对的。
就是容斥。你考虑当一个三元组不合法时一定会有一个点出了 \(2\) 条边，那么设每个点的度数为 \(d_i\)，答案即为 \(\begin{pmatrix} n \\ 3 \end{pmatrix}-\sum\begin{pmatrix} d_i \\ 2 \end{pmatrix}\)。
然后考虑怎么去计算 \(d_i\)，发现这就是个弱智东西，直接把操作离线差分下来再 \(1\) 到 \(n\) 扫描一下就行了。然后你的线段树要支持区间取反和全局求和，这是 TJOI 的一道题叫做开关。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1635F Closest Pair
方便表述，下文设 \(\mathcal{f}(i,j)=(x_j-x_i)(w_j+w_i)\)。
考虑证明一个很启发式的结论：对于 \(l_i = \max_{j<i,w_j\leq w_i}\{j\}\) 与 \(r_i = \min_{j>i,w_j\leq w_i}\{j\}\)，\(\min\{f(l_i,i),f(i,r_i)\}\) 为答案
证明：对于数对 \((i,j)\)，其中 \(i<j\)，我们对其做一个小分讨：
-
\(w_i\leq w_j\)，可以发现，\(i=l_j\) 时 \(|x_i-x_j|\) 最小。但是如果 \(l_j\) 后面的点有 \(w_i\) 更小的怎么办？设其位置为 \(p\)，明显 \(f(p,l_j)<f(l_j,i)\)，所以这样取一定是最优的。
-
\(w_i \ge w_j\) 同上。
那么原问题转化为：有 \(2n\) 个区间，每个区间有权值，还有 \(q\) 个询问区间，要求询问区间包含区间的权值最小值。
一眼离线，把询问挂在右端点，用线段树或者树状数组维护左端点信息即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
标签：log,记录,复杂度,离线,好题,pmatrix,区间,mathcal,DS From： https://www.cnblogs.com/kowenxrz/p/17624331.html