已过但是有巨大疑问(玄关)
  • 板块CF19D Points
  • 楼主cmach_socket
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/2/23 15:47
  • 上次更新2024/2/23 17:16:25
查看原帖
已过但是有巨大疑问(玄关)
239458
cmach_socket楼主2024/2/23 15:47

树套树代码,在建树的时候区间大小建成离散化后元素个数会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;
}

2024/2/23 15:47
加载中...