Gym 101630A（线段树）

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int N=1e6+10;
const ll mod=998244353;
struct node{
    int l,r;
    set<int> s;
}tr[N<<3];
struct seg{
    int t;
    ll x,y;
}in[N];
pll ans[N];
pll res[N];
int dx[N];
int n;
vector<int> num;
set<int> tmp;
int find(int x){
    return lower_bound(num.begin(),num.end(),x)-num.begin()+1;
}
void build(int u,int l,int r){
    if(l==r){
        tr[u]={l,r};
    }
    else{
        tr[u]={l,r};
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
    }
}
void modify(int u,int l,int r,int x,int sign){
    if(tr[u].l>r||tr[u].r<l)
        return ;
    if(tr[u].l>=l&&tr[u].r<=r){
        if(sign){
            tr[u].s.insert(x);
        }
        else{
            tr[u].s.erase(x);
        }
    }
    if(tr[u].l==tr[u].r)
        return;
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)
        modify(u<<1,l,r,x,sign);
    if(r>mid)
        modify(u<<1|1,l,r,x,sign);
}
void query(int u,int l){
    if(tr[u].l==tr[u].r){
        for(auto x:tr[u].s){
            tmp.insert(x);
        }
        return ;
    }
    int mid=tr[u].l+tr[u].r>>1;
    if(l<=mid)
        query(u<<1,l);
    else
        query(u<<1|1,l);
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    int i;
    for(i=1;i<=n;i++){
        int t,x,y;
        cin>>t>>x>>y;
        in[i]={t,x,y};
        num.push_back(x);
        if(t==1){
            num.push_back(x-y);
            num.push_back(x+y);
        }
        if(t==1){
            ans[i].first=x,ans[i].second=y;
        }
    }
    sort(num.begin(),num.end());
    num.erase(unique(num.begin(),num.end()),num.end());
    for(i=1;i<=n;i++){
        if(in[i].t==1){
            int posx=find(in[i].x-in[i].y);
            int posy=find(in[i].x+in[i].y);
            res[i]={posx,posy};
        }
        else{
            dx[i]=find(in[i].x);
        }
    }
    build(1,1,(int)num.size()+100);
    for(i=1;i<=n;i++){
        if(in[i].t==1){
            int posx=res[i].first;
            int posy=res[i].second;
            modify(1,posx,posy,i,1);
        }
        else{
            tmp.clear();
            int pos=dx[i];
            query(1,pos);
            int flag=0;
            for(auto x:tmp){
                ll da=(ans[x].first-in[i].x)*(ans[x].first-in[i].x);
                ll db=(ans[x].second-in[i].y)*(ans[x].second-in[i].y);
                if(da+db<ans[x].second*ans[x].second){
                    int posx=res[x].first;
                    int posy=res[x].second;
                    modify(1,posx,posy,x,0);
                    cout<<x<<endl;
                    flag=1;
                    break;
                }
            }
            if(!flag){
                cout<<-1<<endl;
            }
        }
    }
    return 0;
}