用的权值线段树,一开始只对op==1的操作做离散化,得了92pts,改成对除了op==4之外所有操作进行离散化了之后就AC了,但是我的查找用的是二分+找第k小的方式啊,离散化不应该对答案有影响吧...qwq求解
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(i,j,k) for(int i=(j);i<=(k);++i)
const int MAXN=400020;
int R[MAXN<<5],L[MAXN<<5],b[MAXN],id=0,num[MAXN<<5],n,m,T[MAXN<<2];
int build(int l,int r){
int now=++id;
num[now]=0;
if(l>=r){
return now;
}
int mid=(l+r)/2;
L[now]=build(l,mid);
R[now]=build(mid+1,r);
return now;
}
int update(int pre,int l,int r,int x,int val){
int now=++id;
L[now]=L[pre];R[now]=R[pre];
num[now]=num[pre]+val;
if(l>=r)
return now;
int mid=(l+r)/2;
if(mid>=x)
L[now]=update(L[pre],l,mid,x,val);
else
R[now]=update(R[pre],mid+1,r,x,val);
return now;
}
int find(int u,int v,int l,int r,int k){
if(l>=r)
return l;
int hav=num[L[v]]-num[L[u]];
int mid=(l+r)>>1;
if(hav>=k)
return find(L[u],L[v],l,mid,k);
else
return find(R[u],R[v],mid+1,r,k-hav);
}
struct quer{
int op,x;
}Q[MAXN];
int main(){
scanf("%lld",&n);
int x,y;
int cont=0;
for(int i=1;i<=n;i++)
{
scanf("%lld%lld",&Q[i].op,&Q[i].x);
if(Q[i].op==1||Q[i].op==2||Q[i].op==3||Q[i].op==5||Q[i].op==6)
//if(Q[i].op==1)
b[++cont]=Q[i].x;
}
int q=unique(b+1,b+1+cont)-b-1;
T[0]=build(1,q);
T[1]=T[0];
sort(b+1,b+1+cont);
int tot=0;
for(int i=1;i<=n;i++)
{
int cha,l,r;
// cout<<i<<endl;
switch(Q[i].op){
case 1:
tot++;
cha=lower_bound(b+1,b+1+cont,Q[i].x)-b;
T[1]=update(T[1],1,q,cha,1);
break;
case 2:
tot--;
cha=lower_bound(b+1,b+1+cont,Q[i].x)-b;
T[1]=update(T[1],1,q,cha,-1);
break;
case 3:
l=0;r=tot;
while(l+1<r){
int mid=(l+r)/2;
if(b[find(T[0],T[1],1,q,mid)]>=Q[i].x)
r=mid;
else
l=mid;
}
cout<<r<<endl;
break;
case 4:
cout<<b[find(T[0],T[1],1,q,Q[i].x)]<<endl;
break;
case 5:
l=1; r=tot+1;
while(l+1<r){
int mid=(l+r)/2;
if(b[find(T[0],T[1],1,q,mid)]<Q[i].x)
l=mid;
else
r=mid;
}
cout<<b[find(T[0],T[1],1,q,l)]<<endl;
break;
case 6:
int l=0;int r=tot;
while(l+1<r){
int mid=(l+r)/2;
if(b[find(T[0],T[1],1,q,mid)]>Q[i].x)
r=mid;
else
l=mid;
}
cout<<b[find(T[0],T[1],1,q,r)]<<endl;
break;
}
}
}