社区讨论

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 条回复,欢迎继续交流。

正在加载回复...