CF387E George and Cards 题解

toolong114514 · 2024-06-24 16:07:06 · 题解

CF387E George and Cards 题解

题面大意

传送门。

解题思路

考虑一种贪心的策略：从小到大删数。

由于较大的数总是会对较小的数产生区间的贡献，所以要让较大的数尽可能晚删。如果先删了较大的数，那么答案一定不会更优。

将整个数组从小到大排序，如果当前是要删的数，那么计算出向左最长的区间长，以及向右最长的区间长，加上自己所占的的区间长（值显然为 1），就是这个数的贡献。加完后删掉这个数。最后全部加起来即可。

没那么好的方法

考虑写一颗维护区间最值和区间和的线段树，并记 \operatorname{cnt}(x,y) 为当前区间 [x,y] 剩下的数字个数。

对于当前的点 t，每次分别向左向右二分（在固定一个区间的端点时），找到最小的 l\in[1,t]，满足 \min\{a_l,a_{l+1},\cdots,a_t\}\geqslant a_t，找到最大的 r\in[t,n]，满足 \min\{a_t,a_{t+1},\cdots,a_r\geqslant a_t\}，就可以计算出想要的答案，即 \operatorname{cnt}(l,r)。算完后在线段树上删去当前的 a_t

二分时每一次 check 时间复杂度为 O(\log n)，即一次二分的总体时间复杂度为 O(\log^2{n})。线段树的一次删除操作为 O(\log n)。总共要做 O(n) 次二分，即上述做法总的时间复杂度为 O(n\log^2 n)。

做法比较优秀，但在 1\le k\le n\le10^6 的数据范围和 CF 造的的数据下，会光荣地 Time limit exceeded on test 8。

正解

考虑对刚才的做法进行优化。

我们发现，以删除为主的线段树只能在其上二分，已无优化可能，需要换一个方向：删数变成加数。

先开一颗（权值？）线段树，维护区间最值。

还是顺序扫一遍，记当前数为 a_t。

如果 a_t 不需要删除，那么以 t 为下标，将 t 插入线段树中。

若 a_t 要删除，发现此时线段树里都是限制贡献的数，那么直接找到线段树里最大的 1\le l\le t，最小的 t\le r\le n，当前贡献即为 \operatorname{cnt}(l,r)，\operatorname{cnt} 函数的意义同上。最后在线段树里删掉 a_t，维护一下 \operatorname{cnt} 即可。

每一次删除操作，涉及的线段树操作是 O(\log{n}) 的，一共要删 O(n) 个数，总的时间复杂度即为 O(n\log{n})，可以通过本题。

答案记得要开 long long！

卡常

当然，直接这么写常数太大，会被卡 TLE，需要卡常（听说将权值线段树改为 STL 容器就能过）。

我写的代码卡常内容如下：

1. 开 O4 优化。
2. 加火车头指令集。
3. 手写 std::max 和 std::min 函数。
4. 写快读。

注：CF 允许编译代码中的指令集和优化指令。

如果你有什么更好的卡常方案，欢迎在本文的讨论区分享。

逆天的运行时间：

参考代码