1 条题解

  • 0
    @ 2026-3-15 21:16:58
    #include <bits/stdc++.h>
    #define int long long
    using namespace std;
    const int N=1.5e5+10,LG=__lg(N)+3,inf=1e18;
    int m,K;
    struct node{
        int x[3];
        int val,sum;
        int ls,rs;
        int l[3],r[3];
        int siz,tag;
    }t[N],L,R;
    int rt[LG],cnt=0,n=0,a[N],c;
    #define ls t[p].ls
    #define rs t[p].rs
    void up(int p){
        t[p].sum=t[p].val+t[ls].sum+t[rs].sum;
        t[p].siz=1+t[ls].siz+t[rs].siz;
        for(int k=0;k<K;k++){
            t[p].l[k]=min(t[p].x[k],min(t[ls].l[k],t[rs].l[k]));
            t[p].r[k]=max(t[p].x[k],max(t[ls].r[k],t[rs].r[k]));
        }
    }
    void down(int p){
        if(!t[p].tag) return;
        int x=t[p].tag;
        if(ls) t[ls].tag+=x,t[ls].sum+=x*t[ls].siz,t[ls].val+=x;
        if(rs) t[rs].tag+=x,t[rs].sum+=x*t[rs].siz,t[rs].val+=x;
        t[p].tag=0;
    }
    void release(int &p){
        if(!p) return;
        a[++n]=p;
        down(p);
        release(ls);
        release(rs);
        p=0;
    }
    int build(int l,int r,int k=0){
        if(l>r) return 0;
        int mid=(l+r)>>1;
        nth_element(a+l,a+mid,a+r+1,[k](int x,int y){
            return t[x].x[k]<t[y].x[k];
        });
        int p=a[mid];
        ls=build(l,mid-1,(k+1)%K);
        rs=build(mid+1,r,(k+1)%K);
        up(p);
        return p;
    }
    int query(int p){
        if(!p) return 0;
        for(int k=0;k<K;k++) if(L.x[k]>t[p].r[k] || t[p].l[k]>R.x[k]) return 0;
        bool f=1;
        for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].l[k] && t[p].r[k]<=R.x[k]);
        if(f) return t[p].sum;
        f=1;
        for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].x[k] && t[p].x[k]<=R.x[k]);
        down(p);
        return f*t[p].val+query(ls)+query(rs);
    }
    void update(int p){
        if(!p) return;
        for(int k=0;k<K;k++) if(L.x[k]>t[p].r[k] || t[p].l[k]>R.x[k]) return;
        bool f=1;
        for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].l[k] && t[p].r[k]<=R.x[k]);
        if(f){
            t[p].tag+=c;
            t[p].sum+=t[p].siz*c;
            t[p].val+=c;
            return;
        }
        f=1;
        for(int k=0;k<K;k++) f&=(L.x[k]<=t[p].x[k] && t[p].x[k]<=R.x[k]);
        if(f) t[p].val+=c;
        down(p);
        update(ls);
        update(rs);
        up(p);
    }
    #undef ls
    #undef rs
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0), cout.tie(0);
        cin>>K>>m;
        t[0]={0,0,0,0,0,0,0,inf,inf,inf,0,0,0,0,0};
        for(int op,ans=0;m--;){
            cin>>op;
            if(op==1){
                cnt++;
                for(int i=0;i<K;i++) cin>>t[cnt].x[i],t[cnt].x[i]^=ans;
                cin>>t[cnt].val;t[cnt].val^=ans;
                a[n=1]=cnt;
                for(int i=0;i<LG;i++)
                    if(rt[i]) release(rt[i]);
                    else{
                        rt[i]=build(1,n);
                        break;
                    }
            }
            if(op==2){
                for(int i=0;i<K;i++) cin>>L.x[i],L.x[i]^=ans;
                for(int i=0;i<K;i++) cin>>R.x[i],R.x[i]^=ans;
                cin>>c;c^=ans;
                for(int i=0;i<LG;i++) update(rt[i]);
            }
            if(op==3){
                for(int i=0;i<K;i++) cin>>L.x[i],L.x[i]^=ans;
                for(int i=0;i<K;i++) cin>>R.x[i],R.x[i]^=ans;
                ans=0;
                for(int i=0;i<LG;i++) ans+=query(rt[i]);
                cout<<ans<<"\n";
            }
        }
        return 0;
    }
    
    
    • 1

    信息

    ID
    7197
    时间
    5000ms
    内存
    64MiB
    难度
    10
    标签
    递交数
    4
    已通过
    2
    上传者