2021 上学期做题记录

CQOI 2011 动态逆序对 Dynamic Reverse Pair

• https://www.luogu.com.cn/problem/P3157

显然可以考虑先求出一开始的逆序对数，然后减去当前删去元素的贡献值。

设 \(t_i\) 为元素被删去的时间戳，特别的，永远不会删去的 \(t_i=0\)。

那么，一个逆序对 \((i,j)\) 会有贡献，满足 \(t_i，\(val_i，\(id_i>id_j\) 或者 \(t_i，\(val_i>val_j\)，\(id_i。

跑一遍 CDQ 分治即可，时间复杂度 \(O(n\log^2 n)\)。

HAOI 2010 工厂选址 Factory Location

• https://www.luogu.com.cn/problem/P2514

枚举新厂建在哪里，考虑计算出该位置所需的费用。

发现关键瓶颈在每个煤矿运到哪里，显然可以先贪心选择然后调整。

如果贪心选择后，原本的发电厂少了，考虑把分给新厂的煤给它，显然对于一个 \(i\)，需要付出 \(C_{i,0}-C_{i,j}\) 的代价。

那么可以排序后优先选择尽可能小的哪一个，时间复杂度 \(O(nm\log m)\)。

联合省选 2017 期末考试 Final Exam

• https://www.luogu.com.cn/problem/P3745
• https://loj.ac/p/2141

考虑枚举最大发榜时间 \(t\)。

那么显然就只剩下如何将每个时间变回 \(t\)，此时比较 \(A\) 与 \(B\)。

若 \(A，显然尽量用 \(A\)，然后再用 \(B\)。

若 \(B，显然全部用 \(B\)。

那么，一个前缀和就可以轻松维护了。

时间复杂度 \(O(n\log n)\)。