WA&MLE0分求调
  • 板块P4148 简单题
  • 楼主Ahler
  • 当前回复1
  • 已保存回复1
  • 发布时间2025/8/1 07:25
  • 上次更新2025/8/1 07:35:35
查看原帖
WA&MLE0分求调
1772213
Ahler楼主2025/8/1 07:25
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define cen cout << endl
#define c1 cout << 1 << " "
#define cs cout << " ";
using namespace std;
using namespace __gnu_pbds;
const float Ar=0.75;
int n,last_ans,root=0,now_wd=0,top=0,sum=0,st[200009];
struct point{int x[2],w;}p[200009];
bool operator<(point a,point b){return a.x[now_wd]<b.x[now_wd];}
struct node{int mi[2],mx[2],sum,ls,rs,sz;point tp;}tr[200009];
int newnode(){
    if(top){return st[top--];}
    else{return ++sum;}
}
void up(int k){
    int l=tr[k].ls,r=tr[k].rs;
    for(int i=0;i<2;i++){
        tr[k].mi[i]=tr[k].mx[i]=tr[k].tp.x[i];
        if(l){
            tr[k].mi[i]=min(tr[k].mi[i],tr[l].mi[i]);
            tr[k].mx[i]=max(tr[k].mx[i],tr[l].mx[i]);
        }
        if(r){
            tr[k].mi[i]=min(tr[k].mi[i],tr[r].mi[i]);
            tr[k].mx[i]=max(tr[k].mx[i],tr[r].mx[i]);
        }
    }
    tr[k].sum=tr[l].sum+tr[r].sum+tr[k].tp.w;
    tr[k].sz=tr[l].sz+tr[r].sz+1;
}
int build(int l,int r,int wd){
    if(l>r){
        return 0;
    }
    int mid=(l+2)/2;
    int k=newnode();
    now_wd=wd;
    nth_element(p+l,p+mid,p+r+1);
    tr[k].tp=p[mid];
    tr[k].ls=build(l,mid-1,wd^1);
    tr[k].rs=build(mid+1,r,wd^1);
    up(k);
    return k;
}
void pia_qwq(int k,int num){
    if(tr[k].ls){
        pia_qwq(tr[k].ls,num);
    }
    p[tr[tr[k].ls].sz+num+1]=tr[k].tp;
    st[++sum]=k;
    if(tr[k].rs){
        pia_qwq(tr[k].rs,tr[tr[k].ls].sz+num+1);
    }
}
void check(int &k,int wd){
    if(max(tr[tr[k].ls].sz,tr[tr[k].rs].sz)>tr[k].sz*Ar){
        pia_qwq(k,0);
        k=build(1,tr[k].sz,wd);
    }
}
void insert(int &k,point temp,int wd){
    if(!k){
        k=newnode();
        tr[k].ls=tr[k].rs=0;
        tr[k].tp=temp;
        up(k);
        return;
    }
    if(temp.x[wd]<=tr[k].tp.x[wd]){
        insert(tr[k].ls,temp,wd^1);
    }
    else{
        insert(tr[k].rs,temp,wd^1);
    }
    up(k);
    check(k,wd);
}
bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
    return(X1>=x1&&x2<=X2&&Y1>=y1&&y2<=Y2);
}
bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2){
    return(x1>X2||x2<X1||y1>Y2||y2<Y1);
}
int query(int &k,int x1,int y1,int x2,int y2){
    if(!k){
        return 0;
    }
    int temp=0;
    if(in(x1,y1,x2,y2,tr[k].mi[0],tr[k].mi[1],tr[k].mx[0],tr[k].mx[1])){
        return tr[k].sum;
    }
    if(out(x1,y1,x2,y2,tr[k].mi[0],tr[k].mi[1],tr[k].mx[0],tr[k].mx[1])){
        return 0;
    }
    if(in(x1,y1,x2,y2,tr[k].tp.x[0],tr[k].tp.x[1],tr[k].tp.x[0],tr[k].tp.x[1])){
        temp+=tr[k].tp.w;
    }
    temp+=query(tr[k].ls,x1,y1,x2,y2);
    temp+=query(tr[k].rs,x1,y1,x2,y2);
    return temp;
}
signed main(){
    cin >> n;
    while(1){
        int op;
        cin >> op;
        if(op==1){
            int a,b,c;
            cin >> a >> b >> c;
            a^=last_ans,b^=last_ans,c^=last_ans;
            insert(root,{a,b,c},0);
        }
        if(op==2){
            int x1,x2,y1,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            x1^=last_ans;
            y1^=last_ans;
            x2^=last_ans;
            y2^=last_ans;
            last_ans=query(root,x1,y1,x2,y2);
            cout << last_ans;
            cen;
        }
        if(op==3){
            break;
        }
    }
	return 0;
}
2025/8/1 07:25
加载中...