树套树代码,在建树的时候区间大小建成离散化后元素个数会RE#57,建成n才能过,这是为什么?
问题在78行
#include<iostream>
#include<algorithm>
#include<set>
#include<unordered_map>
#define MAXN 300005
#define lk k<<1
#define rk k<<1|1
using namespace std;
class node{
public:
int l,r,w;
}t[MAXN<<2];
int n,qx[MAXN],qy[MAXN],qo[MAXN],li[MAXN],tot,cnt,ask,v[MAXN];
set<int>st[MAXN];
unordered_map<int,int>m;
char op[10];
int x,po,r,l;
pair<int,int>inf=make_pair(2e9,2e9);
void build(int k,int ll,int rr){
t[k].l=ll,t[k].r=rr;
if(ll==rr){
return;
}
int mid=(ll+rr)>>1;
build(lk,ll,mid);
build(rk,mid+1,rr);
}
void change(int k){
if(t[k].l==t[k].r){
if(r)st[t[k].l].insert(x),t[k].w=*(--st[t[k].l].end());
else{
st[t[k].l].erase(x);
if(st[t[k].l].size())t[k].w=*(--st[t[k].l].end());
else t[k].w=0;
}
return;
}
int mid=(t[k].l+t[k].r)>>1;
if(po<=mid)change(lk);
else change(rk);
t[k].w=max(t[lk].w,t[rk].w);
}
int findd(int k){
if(l<=t[k].l and t[k].r<=r){
if(t[k].w<=x)return 2e9;
if(t[k].l==t[k].r){
return t[k].l;
}
int tmp=2e9;
if(t[lk].w>x)tmp=min(tmp,findd(lk));
else if(t[rk].w>x)tmp=min(tmp,findd(rk));
return tmp;
}
int mid=(t[k].l+t[k].r)>>1,ans=2e9;
if(l<=mid)ans=min(ans,findd(lk));
if(r>mid)ans=min(ans,findd(rk));
return ans;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++){
cin>>op>>qx[i]>>qy[i];
if(op[0]=='a'){
li[++tot]=qx[i];
}
else if(op[0]=='r')qo[i]=1;
else qo[i]=2;
}
sort(li+1,li+1+tot);
cnt=unique(li+1,li+1+tot)-li-1;
for(int i=1;i<=cnt;i++){
m[li[i]]=i;
v[i]=li[i];
}
build(1,1,n);//RE#57:build(1,1,cnt)
for(int i=1;i<=n;i++){
x=qy[i];
if(!qo[i]){
r=1;po=m[qx[i]];
change(1);
}
else if(qo[i]&1){
r=0;po=m[qx[i]];
change(1);
}
else{
ask=upper_bound(v+1,v+1+cnt,qx[i])-v;
if(ask>cnt){
cout<<"-1\n";
continue;
}
l=m[v[ask]];r=cnt;
auto an=findd(1);
if(an==2e9){
cout<<"-1\n";
continue;
}
else{
auto anss=st[an].upper_bound(x);
cout<<v[an]<<' '<<*anss<<'\n';
}
}
}
return 0;
}