社区讨论
RE了,不知道为啥
P3369【模板】普通平衡树参与者 3已保存回复 5
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 5 条
- 当前快照
- 1 份
- 快照标识符
- @lo11vtwl
- 此快照首次捕获于
- 2023/10/22 13:50 2 年前
- 此快照最后确认于
- 2023/11/02 13:20 2 年前
CPP
#include <bits/stdc++.h>
using namespace std;
int n,cnt=1,root=1;
struct Node{
int val,ls,rs;
}tr[1000006];
void push_up(int p){
tr[p].val=tr[tr[p].ls].val+tr[tr[p].rs].val;
}
void update(int &root,int l, int r, int p, int v){
if (!root){
root=++cnt;
tr[root].ls=tr[root].rs=tr[root].val=0;
}
if (l==r){
tr[p].val+=v;
if(tr[root].val<0)tr[root].val=0;
return;
}
int mid=(l+r)>>1;
if (p<=mid)update(tr[p].ls,l,mid,p,v);
else update(tr[p].rs,mid+1,r,p,v);
push_up(p);
}
int query(int p,int l,int r,int pl,int pr){
if(!p)return 0;
if(pl<=l&&r<=pr){
return tr[p].val;
}
int mid=(l+r)>>1,ans=0;
if (pl<=mid)ans+=query(tr[p].ls,l,mid,pl,pr);
if (mid<pr)ans+=query(tr[p].rs,mid+1,r,pl,pr);
return ans;
}
int kth(int p,int l,int r,int v){
if (l==r){
return l;
}
int mid=(l+r) >> 1;
if (v<=tr[tr[p].ls].val) return kth(tr[p].ls,l,mid,v);
else return kth(tr[p].rs,mid+1,r,v-tr[tr[p].ls].val);
}
int pre(int x){
int temp = query(1, -1e7, 1e7, -1e7, x-1);
return kth(1, -1e7, 1e7, temp);
}
int next(int x){
int temp = query(1, -1e7, 1e7, -1e7, x) + 1;
return kth(1, -1e7, 1e7, temp);
}
int main(){
cin>>n;
for (int i=1;i<=n;++i){
int op,x;
cin>>op>>x;
if (op==1)update(root,1,2*1e7,x+1e7,1);
else if (op==2)update(root,1,2*1e7,x+1e7,-1);
else if (op==3)cout<<query(1,1,2*1e7,1,x+1e7-1)+1<<endl;
else if (op==4)cout<<kth(1,1,2*1e7,x)<<endl;
else if (op==5)cout<<pre(x)<<endl;
else if (op==6)cout<<next(x)<<endl;
}
return 0;
}
紫莹莹一片,
真叫人头秃
回复
共 5 条回复,欢迎继续交流。
正在加载回复...