主席树单点修改

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];
    }
}















全部评论

相关推荐

宇算唯航:目测实缴资本不超100W的小公司
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 11:24
大家还是用ai改吧,我心疼得要死,就当花钱买教训吧,人家直接拿完钱就跑路了
程序员小白条:简历修改700....神奇,又不是帮你面试,咋的,简历修改从双非变92了还是没实习变成有大厂实习了
点赞 评论 收藏
分享
05-20 13:59
门头沟学院 Java
米黑子米黑子:你这个成绩不争取下保研?
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-07 13:46
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务