luogu 3369

tech2023-05-27  62

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<vector> #include<cmath> #include<map> #include<string> #include<queue> #include<stack> #include<bitset> #include<list> #include<set> #include<utility> #include<functional> #include<iomanip> #define IO ios::sync_with_stdio(false) #define eps 1e-7 #define int long long using namespace std; struct node { int l,r,sum; }t[100005*4]; int a[100005],b[100005],n,op[100005],cnt; void build(int rt,int l,int r) { t[rt].l=l,t[rt].r=r; if(l==r) { t[rt].sum=0; return; } int mid=l+r>>1; build(rt*2,l,mid); build(rt*2+1,mid+1,r); t[rt].sum=t[rt*2].sum+t[rt*2+1].sum; } void upd(int rt,int x,int v) { if(t[rt].l==x&&t[rt].r==x) { t[rt].sum+=v; return; } int mid=t[rt].l+t[rt].r>>1; if(x<=mid) { upd(rt*2,x,v); } if(x>mid) { upd(rt*2+1,x,v); } t[rt].sum=t[rt*2].sum+t[rt*2+1].sum; } int kth(int rt,int k) { if(t[rt].l==t[rt].r) { return t[rt].l; } int mid=t[rt].l+t[rt].r>>1; if(k<=t[rt*2].sum) { return kth(rt*2,k); } else { return kth(rt*2+1,k-t[rt*2].sum); } } int ran(int rt,int x) { if(t[rt].l==t[rt].r) { return (int)1; } int mid=t[rt].l+t[rt].r>>1; if(x<=mid) { return ran(rt*2,x); } else { return t[rt*2].sum+ran(rt*2+1,x); } } signed main() { IO; cin>>n; for(int i=1;i<=n;i++) { cin>>op[i]>>a[i]; if(op[i]!=4)b[++cnt]=a[i]; } sort(b+1,b+cnt+1); int len=unique(b+1,b+cnt+1)-(b+1); build(1,1,len); for(int i=1;i<=n;i++) { if(op[i]!=4)a[i]=lower_bound(b+1,b+len+1,a[i])-b; if(op[i]==1)upd(1,a[i],1); if(op[i]==2)upd(1,a[i],-1); if(op[i]==3)cout<<ran(1,a[i])<<endl; if(op[i]==4)cout<<b[kth(1,a[i])]<<endl; if(op[i]==5)cout<<b[kth(1,ran(1,a[i])-1)]<<endl; if(op[i]==6)cout<<b[kth(1,ran(1,a[i]+1))]<<endl; } }
最新回复(0)