题解：P2617 Dynamic Rankings

· · 题解

P2617 解题报告

前言

大家好，我非常喜欢 STL，所以我用 vector 过了这道题。

思路分析

看题，发现题目要求维护序列上：

  1. 单点修改

  2. 查询区间第 k 大值。

不难发现这就是 P3380 【模板】树套树 的操作 2 和操作 3。

具体来说，可以维护一棵线段树套平衡树，在线段树的每一个节点维护一棵平衡树，平衡树内维护的数就是线段树节点所代表的区间上的数。

这样，两个操作可以这样做：

  1. 在线段树上递归区间，将递归到的节点的平衡树上删除原数值，添加新数值。

  2. 二分答案，问题转化为求一个数在区间内的排名。考虑将询问区间拆分成线段树上节点，在每个节点的平衡树上查询小于当前二分值的数的个数。

使用线段树套平衡树的复杂度为 O(n \log ^3 n)，如果写法优秀，直接在线段树上二分，复杂度为 O(n \log ^2 n)。

但是在考场上写树套树，对于像我一样的普及组选手有点困难 （普及组选手做树套树题？），所以我们考虑降低实现难度。

有请今天的主角：vector!

我们考虑用 vector 替换掉内层的平衡树。

考虑使用 vector 中 insert 和 erase 成员函数，以及 stl 中的 lower_bound 函数，维护一个有序（具体来说是单调不降）的线性表。

这样，两个操作可以这样做：

  1. 外层线段树部分同上，对于内层 vector 的修改先用 lower_bound 函数找到 x 的位置，然后调用 insert/erase 函数。

  2. 二分和外层线段树部分同上，对于内层 vector 的查询在每个线段树节点上的 vector 上用 lower_bound 函数直接查询小于 x 的数的个数。

注意，vector 中 insert 和 erase 成员函数的复杂度都是 O(n) 的。

使用线段树套 vector 的复杂度已经达到了令人发指的 O(n^2 \log^2 n)，甚至不如暴力。但是由于 vector 令人发指的常数，这样实现的时间甚至超越了某些常数巨大的线段树套 Splay。（这是 vector 的胜利！）

代码实现

都用 vector 了还不试着自己写写。

vector 替代平衡树部分（请忽略自欺欺人的变量名）：


struct FHQ{
    vector<int> v;
    void insert(int x){
        v.insert(lower_bound(v.begin(),v.end(),x),x);
    }
    void delate(int x){
        if(!v.size() || x==-1) return;
        v.erase(lower_bound(v.begin(),v.end(),x));
    }
    int get_rk(int x){
        return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
    }
}treap[200005];

线段树部分：


struct segment_tree{
    int val[200005],ls[200005],rs[200005],dcnt;
    void build(int l,int r,int &x){
        x=++dcnt;
        if(l==r){
            val[l]=-1;
            return;
        }
        int mid=(l+r)>>1;
        build(l,mid,ls[x]);
        build(mid+1,r,rs[x]);
    }
    void modify(int l,int r,int pos,int k,int x){
        treap[x].delate(val[pos]);
        treap[x].insert(k);
        if(l==r){
            val[pos]=k;
            return;
        }
        int mid=(l+r)>>1;
        if(pos<=mid) modify(l,mid,pos,k,ls[x]);
        else modify(mid+1,r,pos,k,rs[x]);
    }
    int query_rk(int l,int r,int ql,int qr,int k,int x){
        if(ql<=l && r<=qr) return treap[x].get_rk(k)-1;
        int mid=(l+r)>>1,ans=0;
        if(ql<=mid) ans+=query_rk(l,mid,ql,qr,k,ls[x]);
        if(qr>=mid+1) ans+=query_rk(mid+1,r,ql,qr,k,rs[x]); 
        return ans;
    }
    int query_k(int ql,int qr,int k){
        int l=0,r=1e9,ans=0;
        while(l<=r){
            int mid=(l+r)>>1;
            if(query_rk(1,n,ql,qr,mid,1)+1<=k){
                ans=mid;
                l=mid+1;
            }else{
                r=mid-1;
            }
        }
        return ans;
    }
}tree;

AC 记录（封装版，无卡常，码风良好）

封装的这么好，主函数就自己写吧。

补：关于 vector 替代平衡树的一些测试

临近 CSP/NOIP，大家刷题还是要注重实用性的。

关于是否能在考场上用 vector 来替代平衡树，并且做到不挂分，看网上说法不一。本着实践出真知的理念，这里为大家提供 vector 和现 OI 主流平衡树（Splay，FHQ-Treap，替罪羊树，pbds）的时间耗用对比测试。

代码

vector

Splay（数组实现）

FHQ-Treap（数组实现）

替罪羊树（指针实现）

pbds

评测方式/环境/语言

方式：LemonLime

数据：数据脚造，数据分为三组：

  1. 随机数据，n=100000，对标ds优化题数据强度；

  2. 随机数据，n=1000000，对标纯ds题数据强度；

  3. 构造数据，n不等，卡vector。

本机环境：Windows 11，Intel Core i5，x64，1.70 GHz （省流：很旧，跑的很慢）

语言：C++14 O2 (gcc 9.3.0)

评测结果

here.（提取码 lxt3）

分析总结

所以，我的建议是，vector 模拟赛随便用，正赛慎重使用，当心一场空。

写在最后

祝各位读者 CSP 2024 / NOIP 2024 RP++ ！