铁流-2题解&赛后总结

就是一个带权的LIS问题，二分处理时记得乘一个权值，还有就是乘的是 $len$ 不是 $j$。

NOIP2024 T1

分块贪心处理，暴力+贪心可过80。

首先考虑暴力。

预处理每个数左边比它大的数和右边比它大的数，然后先找右边，再对右边找左边，再对左边找右边即可。注意到从右边找左边可以用二分优化，但优化后无法处理最后一步，于是用前缀和处理。若右边比 $a_i$ 大的数存于 $r_i$ 中，则 $qzh_{i,j}$ 表示对于所有 $k \leq i$，$r_i$ 中下标大于 $j$ 的数有多少个，那么在枚举第二步的时候二分找到所有可作为第二大数的下标区间，并使用前缀和找到其右边大于它且下标大于第三大数下标的个数，相加即可。

不想说了。

乘法原理+分讨秒了。