社区讨论
FHQ求调,WA65,悬棺
题目总版参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lxsyvwws
- 此快照首次捕获于
- 2024/06/24 20:41 2 年前
- 此快照最后确认于
- 2024/06/25 08:20 2 年前
CPP
#include<bits/stdc++.h>
using namespace std;
mt19937 myrand(time(0));
#define int long long
int n,op,a,ct,root,sum;
struct node{
int cnt,val,rnd,siz,ls,rs,fa;
}tr[200005];
int newnode(int x){
tr[++ct].rnd=myrand(),tr[ct].siz=1,tr[ct].val=x;
return ct;
}
void fen(int ii,int k,int &l,int &r){
if(ii==0){
l=0,r=0;
return;
}
if(tr[ii].val<=k){
l=ii;
fen(tr[ii].rs,k,tr[ii].rs,r);
}else{
r=ii;
fen(tr[ii].ls,k,l,tr[ii].ls);
}
tr[ii].siz=tr[tr[ii].ls].siz+tr[tr[ii].rs].siz+1;
}
int he(int l,int r){
if(l==0) return r;
if(r==0) return l;
if(tr[l].rnd<tr[r].rnd){
tr[l].rs=he(tr[l].rs,r);
tr[l].siz=tr[tr[l].ls].siz+tr[tr[l].rs].siz+1;
return l;
}else{
tr[r].ls=he(l,tr[r].ls);
tr[r].siz=tr[tr[r].ls].siz+tr[tr[r].rs].siz+1;
return r;
}
}
void add(int x){
int l=0,r=0;
fen(root,x,l,r);
root=he(he(l,newnode(x)),r);
}
void del(int x){
int l=0,r=0,mid=0;
fen(root,x,l,r);
fen(l,x-1,l,mid);
root=he(l,r);
}
int askrnd(int x){
int l=0,r=0;
fen(root,x-1,l,r);
sum=tr[l].siz+1;
root=he(l,r);
return sum;
}
int askrnd2(int ii,int x){
if(x==tr[tr[ii].ls].siz+1) return tr[ii].val;
if(x<=tr[tr[ii].ls].siz) return askrnd2(tr[ii].ls,x);
return askrnd2(tr[ii].rs,x-tr[tr[ii].ls].siz-1);
}
int ask3(int ii,int x){
return askrnd2(ii,askrnd(x)-1);
}
int ask4(int ii,int x){
return askrnd2(ii,askrnd(x+1));
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld%lld",&op,&a);
sum=0;
if(op==1) add(a);
if(op==2) del(a);
if(op==3) printf("%lld\n",askrnd(a));
if(op==4) printf("%lld\n",askrnd2(root,a));
if(op==5) printf("%lld\n",ask3(root,a));
if(op==6) printf("%lld\n",ask4(root,a));
}
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...