线段树求助
  • 板块CF19D Points
  • 楼主mystic_qwq
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/5/8 00:03
  • 上次更新2024/5/8 16:28:11
查看原帖
线段树求助
246331
mystic_qwq楼主2024/5/8 00:03
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+1;
struct FastIO{
  template<class T>
  inline FastIO&operator>>(T&x){
    #ifdef ONLINE_JUDGE
    #define G getchar_unlocked()
    #else
    #define G getchar()
    #endif
    static char c;
    while((c=G)<48);
    for(;c>47;c=G)x=x*10+(c^48);
    return*this;
  }
}qin;
vector<int>X,Y;
#define pb push_back
struct{
  char op[7]; int x,y;
} qq[N];
int n,d[N*4];
set<int>b[N];
#define Tree int u,int l,int r
#define mid (l+r>>1)
#define ls u<<1
#define rs ls|1
#define Lson ls,l,mid
#define Rson rs,mid+1,r
#define pushup(u) d[u]=max(d[ls],d[rs])
#define bg(x) x.begin()
#define ed(x) x.end()
#define Ed(x) *x.rbegin()
#define all(x) bg(x),ed(x)
void build(Tree){
  d[u]=-1;
  if(l==r) return;
  build(Lson),build(Rson);
}
void modify(Tree,int x,int y){
  if(l==r) return void(d[u]=y);
  if(x<=mid) modify(Lson,x,y);
  else modify(Rson,x,y);
  pushup(u);
}
void query(Tree,int x,int y,int&t){
  if(l==r) return void(d[u]<y&&(t=l));
  if(x<=mid&&d[ls]>=y) query(Lson,x,y,t);
  if(t<0&&d[rs]>=y) query(Rson,x,y,t);
}
main(){
  X.pb(-1),Y.pb(-1);
  qin>>n,build(1,1,n);
  for(int i=1;i<=n;++i){
    auto&[op,x,y]=qq[i];
    cin>>op,qin>>x>>y;
    if(*op=='f')++x,++y;
    X.pb(x),Y.pb(y);
    b[i].insert(-1);
  }
  sort(all(X)),sort(all(Y));
  X.erase(unique(all(X)),ed(X));
  Y.erase(unique(all(Y)),ed(Y));
  for(int i=1;i<=n;++i){
    auto&[op,x,y]=qq[i];
    x=lower_bound(all(X),x)-bg(X);
    y=lower_bound(all(Y),y)-bg(Y);
    switch(*op){
      case'a':{
        if(Ed(b[x])<y)
          modify(1,1,n,x,y);
        b[x].insert(y);
        break;
      }
      case'r':{
        b[x].erase(b[x].find(y));
        modify(1,1,n,x,Ed(b[x]));
        break;
      }
      default:{
        int res;query(1,1,n,x,y,res);
        if(res==-1) cout<<"-1\n";
        else cout<<X[x]<<' '<<Y[*b[x].lower_bound(y)]<<'\n';
        break;
      }
    }
  }
}

2024/5/8 00:03
加载中...