P3730 的非值域分块算法

· · 题解

本题解思路来源：AiRC0S（提交此题解已经过本人允许）

前置知识：莫队

其实本题无需使用值域分块，思路也并不复杂。（感谢 AiRC0S 大佬思路）

莫队算法

首先，由于本题系不带修查询，直接考虑先使用莫队算法对询问进行分块。

struct query{
    int l, r, k, id;
} q[N]; //询问结构体 

bool cmp(query a, query b){
    return a.l/L == b.l/L? a.r<b.r : a.l<b.l;
    //排序 ，L为块长
}

Solution

然后，很多人在这里使用了值域分块，来维护区间第 k 小。实际上，我们考虑这个算法的本质。定义一个数组 cnt 表示股票的热度，所谓的值域分块，不过是结合莫队的询问分块，每次在这个数组中进行一次单点修改（参见其他题解）。我们仔细考虑在这里单点修改的重要性质：只会对其中的一个值进行一次差为 1 的更改。于是考虑对此数组进行排序（不妨由大到小）。排序后，如何保证始终使此序列有序？

解法应当相当明显了：如果要增加，就将该数字的序列中（必定连在一起）最左侧的数字增加 1，否则将最右侧的减少 1，这样序列始终保持有序。

这样一来，时间复杂度 O(1) 修改，O(\sqrt{n}) 查询的值域分块，就可以完全被时间复杂度均 O(1) 的数组单修代替，至此算法结束，代码完成。

//lf表示每段连续数字的左端点，rf为右端点
//f为排序数组（由大到小） 
//cnt即热度数组 
void add(int x){
    f[lf[cnt[x]]] = cnt[x]+1;
    lf[cnt[x]]++;
    cnt[x]++;
    rf[cnt[x]]++;
}
void del(int x){
    f[rf[cnt[x]]] = cnt[x]-1;
    rf[cnt[x]]--;
    cnt[x]--;
    lf[cnt[x]]--;
}
//理论上，lf与rf可以通过+1-1的操作得到
//可以略去一个节省空间，但没有必要

在一切之前，注意到值域大小，直接先离散化。

核心代码已给出，其余部分与其他题解中值域分块算法大致相同，不再给出。

Final

此题给予了我们很好的启示。这样的思路明显各方面优于值域分块，但明显这样的思路建立在值域分块上，又对其进行了大幅的优化。在做题时，先写基础代码是很好的习惯，但在算法完成后需要优化时，可以考虑从性质上分析，在思路上基于基础算法，但在实现上完全重做，而不局限于常数优化和数据结构优化。

最后再次鸣谢 AiRC0S 的思路以及给我在 OI 学习上的帮助。