P2073 题解

zhangbo1000 · 2024-01-24 18:12:32 · 题解

update 2024.3.21 重新提交以去除旧博客分类。

看了一圈题解居然没有伟大的树状数组的，那么我来写一个。

基础的树状数组操作不再赘述，建议去看模板题题解，这里主要讲下怎么用树状数组水平衡树。

（题目不强制在线，可以离散化，下面我默认值域大小与操作数同阶。）

首先我们假设 c_i 表示 i 的出现次数，那么很显然 (\sum^{n-1}_{i=1}c_i)+1 就是数 n 的排名，很明显，用树状数组维护 c，查询排名就搞定了。

下面是重头戏，也是很多题解图片炸了没讲清楚的地方——查询排名为某值的数。

首先 O(\log^2n) 的算法很好想，二分即可，但实际我们有方法将复杂度降低到 O(\log n)。

想一想，为什么二分需要 O(\log^2n)，因为求每个数排名都需要 O(\log n)，而这一点是因为二分过程中每次查询数的变化与树状数组的性质没有必然联系。我们需要一种新的方法 O(\log n)（不包括对每个答案的验证） 确定答案的方法——倍增。

仔细想一下，一个数 n 的二进制下的位数明显也是 O(\log n) 的，所以我们可以依次尝试将每个 2 的幂加入到答案中，设当前答案为 ans，加入的数为 2^i，那么显然，如果我们倒序枚举 i，就能保证 \operatorname{lowbit}(ans+2^i)=2^i，这样我们就能根据树状数组的定义 O(1) 判断和更新答案，总复杂度就降低到了 O(\log n)。参考代码：

#define N 1000000
int c[N+1];
int findrank(const int& k){
    static const int MAX=log2(N)+1;
    static int ans,cnt,i;
    for(i=MAX,ans=cnt=0;i>=0;i--){
        ans+=1<<i;
        if(ans>N||c[ans]+cnt>=k)ans-=1<<i;
        else cnt+=c[ans];
    }
    return ans+1;
}

是不是比二分还短。

回到这个题上，操作 1 用树状数组维护，再开个数组保存每个价格的花的美丽度，操作 2 维护下当前花的支数 n，再删除 \operatorname{findrank}(n) 即可，操作 3 删除 \operatorname{findrank}(1) 即可，最后答案只需开两个变量存储花的总价值和总价格即可。

题的完整代码就不贴了，一点注释没加码风还不好。（想要看的跳转这里。）

广告。