本文主要是介绍HDU 2852(权值线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2852
题目大意：一共存在三种操作，插入一个数字，删除一个数字，查找大于x的第k大数字是几
题目思路：权值线段树维护每个区间内的数字出现过的次数，插入一个数字就是对应的地方+1，删除就是-1，大于x的第k大，首先得到1~x有多少个数字，这样大于x的第k大就相当于第num+k大数字。
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
const int MAXN = 1e5+5;
int m,p,x,y;
struct node{int l,r,val;
}a[MAXN<<2];
void build(int rt,int l,int r){a[rt].l=l,a[rt].r=r,a[rt].val=0;if(l==r)return ;int mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
}
void update(int rt,int pos,int val){if(a[rt].l==a[rt].r&&a[rt].l==pos){if(a[rt].val+val<0){printf("No Elment!\n");return;}a[rt].val+=val;return;}int mid=(a[rt].l+a[rt].r)>>1;if(pos<=mid)update(rt<<1,pos,val);else update(rt<<1|1,pos,val);a[rt].val=a[rt<<1].val+a[rt<<1|1].val;
}
int query1(int rt,int l,int r){if(a[rt].l>=l&&a[rt].r<=r){return a[rt].val;}int mid=(a[rt].l+a[rt].r)>>1;int ans=0;if(l<=mid)ans+=query1(rt<<1,l,r);if(r>mid)ans+=query1(rt<<1|1,l,r);return ans;
}
int query2(int rt,int x){if(a[rt].l==a[rt].r)return a[rt].l;if(x<=a[rt<<1].val)return query2(rt<<1,x);else return query2(rt<<1|1,x-a[rt<<1].val);
}
int main(){while(~scanf("%d",&m)){build(1,1,1e5);while(m--){scanf("%d",&p);if(!p){scanf("%d",&x);update(1,x,1);}else if(p==1){scanf("%d",&x);update(1,x,-1);}else{scanf("%d%d",&x,&y);int num=query1(1,1,x);if(a[1].val<num+y){printf("Not Find!\n");continue;}int ans=query2(1,num+y);printf("%d\n",ans);}}}return 0;
}
这篇关于HDU 2852(权值线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
