使用 pbds 吧,百度上有详细的用法
by xiaosi4081 @ 2024-01-20 21:29:10
看看这篇?
好像`set`$\operatorname{O}(n\log^2n)$
by louiesun @ 2024-01-20 21:32:27
@[louiesun](/user/443447) 漏了链接……
[link](https://blog.csdn.net/weixin_43907802/article/details/99173187)
by louiesun @ 2024-01-20 21:35:55
谢谢,正经的知识又增加了。
by 2023luojie @ 2024-01-21 15:05:43
@[2023luojie](/user/1070310) set+树状数组能过
```cpp
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
using namespace std;
int c[20000015],cnt[20000015],maxx;
int n,op,x;
set<int> s;
void add(int x,int y){
for(int i=x;i<=20000010;i+=lowbit(i)){
c[i]+=y;
}
}
long long ask(int x){
long long ans=0;
for(int i=x;i;i-=lowbit(i)){
ans+=c[i];
}
return ans;
}
int find(int x,int pos){
int ans,l=0,r=maxx;
if(pos==1){
ans=maxx;
while(l<r){
int mid=(l+r)/2;
if(ask(mid)<x){
l=mid+1;
}
else {
r=mid;
ans=min(ans,mid);
}
}
}
else if(pos==2){
ans=0;
while(l<r){
int mid=(l+r)/2;
int sum=*s.upper_bound(mid);
if(sum<x){
l=mid+1;
ans=max(ans,sum);
}
else {
r=mid;
}
}
while(*s.upper_bound(ans)<x&&s.upper_bound(ans)!=s.end()&&*s.upper_bound(ans)!=ans) ans=*s.upper_bound(ans);
}
else {
ans=*s.upper_bound(x);
}
return ans-10000001;
}
signed main(){
// freopen("P3369_6.in","r",stdin);
// freopen("P3369_6.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>op>>x;
if(op!=4) x+=10000001;
maxx=max(maxx,x);
if(op==1){
cnt[x]++;
add(x,1);
if(cnt[x]==1) s.insert(x);
}
else if(op==2){
if(cnt[x]==0) continue;
cnt[x]--;
add(x,-1);
if(cnt[x]==0) s.erase(x);
}
else if(op==3) {
cout<<ask(x-1)+1<<"\n";
}
else if(op==4){
cout<<find(x,1)<<"\n";
}
else if(op==5){
cout<<find(x,2)<<"\n";
}
else {
cout<<find(x,3)<<"\n";
}
}
return 0;
}
/*
*/
```
by fried_chicken @ 2024-04-24 18:32:15