标签：总结 8.2 线段 T3 维护 赛后
比赛概况：坠机了；
\(T1\) ——写了线段树维护区间最大值再向两边扩散，可惜被卡掉了。
正解：维护每个每个点向左和向右能扩展到的最远下标，在加以判断即可。
\(T2\) ——脑抽了把能够 \(O(1)\) 解决的事写了一个循环 （活该被卡），思路和正解一摸一样，可惜了。
正解：对于每一个数，贪心地思考他最少切几刀，更新最小值即可。
\(T3\) ——比赛结束前 \(5min\) 发现写假了
寄！
正解：对于行与列分开来做动态规划，最后求和。
\(T4\) ——被 \(T3\) 卡了没来得及看。
正解：用线段树维护一棵平衡树，或 \(set\) ，线段树上二分求边界更新答案。
总结——在遇到难题是，要及时思考算法的正确性，避免在一个不正确的算法上浪费时间。
标签：总结,
8.2,
线段,
T3,
维护,
赛后
From： https://www.cnblogs.com/optimist-skm/p/18339019