本文主要是介绍BZOJ 3224 Tyvj 1728 普通平衡树(权值线段树)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3224
题目大意：您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
题目思路：维护每个数字出现的次数，插入x就是第x个节点+1，删除x就是第x个节点-1，查询x数的排名，很简单就是找出1~x-1一共有几个数字，他的排名就是数字个数+1，查询排名为x的数，就进行搜索，当左子树的数字数量大于x时，就进左子树，如果左子树数字数量小于x，就进右子树搜x-num大的数字，前驱就是求出前1~x-1一共有几个数字，假设有num个，那就求第num大是多少，就是小于x的最大数，对于后继，找出1~x一共有几个数字，那么num+1就是他后继的排名。由于数字范围很大需要离线处理，采用离散化
以下是代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define per(i,a,b) for(ll i=a;i>=b;i--)
const ll MAXN = 1e5+5;
struct node{ll l,r,val;
}a[MAXN<<2];
struct query{ll p,x;
}q[MAXN];
ll b[MAXN];
void build(ll rt,ll l,ll r){a[rt].l=l,a[rt].r=r,a[rt].val=0;if(l==r)return ;ll mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
}
void update(ll rt,ll x,ll val){if(a[rt].l==a[rt].r&&a[rt].l==x){a[rt].val+=val;return;}ll mid=(a[rt].l+a[rt].r)>>1;if(x<=mid)update(rt<<1,x,val);else update(rt<<1|1,x,val);a[rt].val=a[rt<<1].val+a[rt<<1|1].val;
}
ll query(ll rt,ll l,ll r){if(a[rt].l>=l&&a[rt].r<=r)return a[rt].val;ll mid=(a[rt].l+a[rt].r)>>1,ans=0;if(l<=mid)ans+=query(rt<<1,l,r);if(r>mid)ans+=query(rt<<1|1,l,r);return ans;
}
ll query1(ll rt,ll x){if(a[rt].l==a[rt].r)return a[rt].l;if(x<=a[rt<<1].val)return query1(rt<<1,x);else return query1(rt<<1|1,x-a[rt<<1].val);
}
int main(){ll n;scanf("%lld",&n);build(1,1,1e5);ll num=0;rep(i,1,n){scanf("%lld%lld",&q[i].p,&q[i].x);if(q[i].p==4)continue;b[++num]=q[i].x;}sort(b+1,b+num+1);num=unique(b+1,b+num+1)-b-1;rep(i,1,n){ll x;if(q[i].p!=4)x=lower_bound(b+1,b+num+1,q[i].x)-b;else x=q[i].x;if(q[i].p==1){update(1,x,1);}if(q[i].p==2){update(1,x,-1);}if(q[i].p==3){ll ans=query(1,1,x-1)+1;printf("%lld\n",ans);}if(q[i].p==4){ll ans=query1(1,x);printf("%lld\n",b[ans]);}if(q[i].p==5){ll pos=query(1,1,x-1);ll ans=query1(1,pos);printf("%lld\n",b[ans]);}if(q[i].p==6){ll pos=query(1,1,x);ll ans=query1(1,pos+1);printf("%lld\n",b[ans]);}}return 0;
}
这篇关于BZOJ 3224 Tyvj 1728 普通平衡树(权值线段树)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
