- 技术博客
- luogu 3369
#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
;
}
}
