P3586 [POI2015] LOG

原题

先写我复杂度错误的一个思路：首先每次选最小的 \(c\) 个做显然是优秀的，贪心性质显然，打表找一下答案？

1 2 3
0 2-1 3-1                              +1         1
0 0 3-2 4-2+1                          +2-1       2
0 0 0 4-3+1 5-3+2                      +3-2       3
0 0 0 0 5-4+2-1 6-4+3-1                +4-3+1     4+1
0 0 0 0 0 6-5+3-2 7-5+4-2+1            +5-4+2-1   5+2
0 0 0 0 0 0 7-6+4-3+1 8-6+5-3+2        +6-5+3-2   6+3
0 0 0 0 0 0 0 8-7+5-4+2-1 9-7+6-4+3-1  +7-6+4-3+1 7+4+1

注意，这里的数字表示的是数组下标

显然答案是 \(\sum\limits_{i=n\rightarrow 0}^{i \leftarrow i-c} a_i \geq s\) ，怎么求和？分块 \(+\) 根号分治，但 \(n \leq 1e6\) 遂寄

首先发现我们的 \(s\) 还没有使用，于是猜想一个和 \(s\) 有关的结论：\(\sum_{i=1}^{n} a_i \geq c \times s\) 时有答案，错误显然

发现影响答案的偏差是可能有一些过大的数，求和时会被认为大的数把小的数补上了，但题目要求不能重复选数，遂寄掉

如何定义过大的数？显然 \(a_i \geq s\) 那他再大也没有，于是我们强制 \(a_i \geq s\) 的 \(a_i \leftarrow s\) ，此时计算答案就正确了

维护？在线 Splay Or 离线 树状数组。复杂度 \(O(n \log n)\)