题解：P13981 数列分块入门 6

ningyy · 2025-09-09 19:55:25 · 题解

思路

支持插入一个数以及查询第 i 个数的值，显然平衡树板子，这里用 FHQTreap 实现，分裂操作为按位置分裂，修改直接在对应位置分裂再合并，查询将对应位置前后分别分裂，直接调用中间的值即可。

代码

#include<bits/stdc++.h>
#define pu(p) t[p].sz=t[t[p].ls].sz+t[t[p].rs].sz+1
using namespace std;
const int N=1e6;
int n,a[N];
struct node{
    int vl,ls,rs,sz,ky;
}t[N];
int cnt=0,rt=0;
void split(int p,int &l,int &r,int x){
    if(p==0) return l=r=0,void();
    if(t[t[p].ls].sz+1<=x){
        l=p;
        split(t[p].rs,t[p].rs,r,x-t[t[p].ls].sz-1);
    }
    else{
        r=p;
        split(t[p].ls,l,t[p].ls,x);
    }
    pu(p);
}
int merge(int l,int r){
    if(l==0 || r==0) return l+r;
    if(t[l].ky>=t[r].ky){
        t[l].rs=merge(t[l].rs,r);
        pu(l);
        return l;
    }
    else{
        t[r].ls=merge(l,t[r].ls);
        pu(r);
        return r;
    }
}
void ins(int i,int x){
    int l,r;
    t[++cnt]={x,0,0,1,rand()};
    split(rt,l,r,i-1);
//  cout<<l<<" "<<r<<'\n';
    rt=merge(l,merge(cnt,r));
//  cout<<rt<<"\n";
}
int query(int c){
    int l,r,p,ans;
    split(rt,l,r,c);
    split(l,l,p,c-1);
    ans=t[p].vl;
    rt=merge(l,merge(p,r));
    return ans;
}
signed main(){
    srand(time(0));
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i],ins(i,a[i]);
    for(int i=1,op,l,r,c;i<=n;i++){
        cin>>op;
        if(!op) cin>>l>>r,ins(l,r);
        else cin>>c,cout<<query(c)<<"\n";
    }
    return 0;
}