主席树单点修改

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















全部评论

相关推荐

07-09 18:28
门头沟学院 Java
写着提前批,结果还要实习4个月以上???
程序员牛肉:这种不用看,直接投了,面试的时候问对应的HR就行。有可能他们是直接复制的暑期实习的模板。
点赞 评论 收藏
分享
积极的小学生不要香菜:你才沟通多少,没500不要说难
点赞 评论 收藏
分享
06-14 19:09
门头沟学院 Java
darius_:给制造业搞的,什么物料管理生产管理,设备管理点检,最最关键的就是一堆报表看板。个人觉得没啥技术含量都是些基本的crud,但是业务很繁琐那种
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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