题解：P13981 数列分块入门 6

libu2333 · 2025-09-06 17:42:40 · 题解

平衡树板子题。

我们用 pb_ds 的平衡树存一个带有逻辑位置 key 的节点，初始每个元素的 key 取稀疏值（如 i \times 10^9），这样顺序就由 key 决定；插入时在相邻元素 key 之间取中点作为新 key，插入在在最前面则取更小的 key。

查询时用 find_by_order 直接按排名取第 c 个元素即可，全程每次操作都是 O(\log n)。

代码如下。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
struct node{
    ll k;
    int v;
    bool operator<=(const node&o)const{
        return k<=o.k;
    }
};
typedef tree<node,null_type,less_equal<node>,rb_tree_tag,tree_order_statistics_node_update> ost;
int n;ost t;
ll gap=1e9;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        t.insert({i*gap,x});
    }
    for(int i=0;i<n;i++){
        int op;
        cin>>op;
        if(op==0){
            int l,r;
            cin>>l>>r;
            ll nk;
            if(l==1){
                auto it=t.find_by_order(0);
                nk=it->k-gap/2;
            }else{
                auto it1=t.find_by_order(l-2);
                auto it2=t.find_by_order(l-1);
                nk=(it1->k+it2->k)/2;
            }
            t.insert({nk,r});
        }else{
            int c;cin>>c;
            auto it=t.find_by_order(c-1);
            cout<<it->v<<"\n";
        }
    }
}