主席树单点修改

ps: from AgOH in B站

离散化
数组定义 a[]
临时数组 v
int cnt;
const int maxn;
int root[maxn];
struct hjt{
    int l,r,sum;
}h[40 * maxn];
int getid(int x){
    return lower_bound(v.begin(),v.end(),x)-v.begin()+1;
}

void insert(int l, int r, int pre, int now, int p){
    hjt[++cnt] = hjt[pre];
    now = cnt;
    hjt[now].sum ++;
    if(l==r) return;
    int m = l + r>>1;
    if(p<=m) insert(l, m, hjt[pre].l , hjt[now].l, p);
    else insert(m+1, r, hjt[pre].r, hjt[now].r , p);
}

int query(int l, int r, int L, int R, int k){
    if(l==r) return l;
    int m = l+r>>1;
    int tmp = hjt[hjt[R].l].sum - hjt[hjt[L-1]].sum;
    if(k<=tmp) return query(l, m, hjt[L].l, hjt[R].l, k);
    else return query(m+1, r, hjt[L].r , hjt[R].r , k-tmp);
}

int main(){
    for(int i =1;i<=n;i++){
        cin>>a[i]; v.push_back(a[i]);
    }

    for(int i=1;i<=n;i++){
        insert(1,n,root[i-1],root[i]);
    }

    for(int i=1;i<=m;i++){
        cin>>L>>R>>k;
        return v[query(1, n, L, R, k)-1];
    }
}