kdt 20pts RE求条

lijianqiao @ 2024-07-16 15:02:32

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct node{
    int x,y,val;
}poi[1000005];

int n,cnt;

bool cmp1(node xx,node yy){
    return xx.x<yy.y;
}

bool cmp2(node xx,node yy){
    return xx.y<yy.y;
}

struct node2{
    int lx,rx,ly,ry,sum;
}tree[4000005];

unordered_map<int,int> tong;
vector<node> hch;

void build(int cx,int rt,int l,int r){
    if(l==r){
        tree[rt].lx=tree[rt].rx=poi[l].x;
        tree[rt].ly=tree[rt].ry=poi[l].y;
        tree[rt].sum=poi[l].val;
        return;
    }
    int mid=(l+r)>>1;
    nth_element(poi+l,poi+mid,poi+r+1,cx==1?cmp1:cmp2);
    build(1-cx,rt*2,l,mid);
    build(1-cx,rt*2+1,mid+1,r);
    tree[rt].sum=tree[2*rt].sum+tree[2*rt+1].sum;
    tree[rt].lx=min(tree[2*rt].lx,tree[2*rt+1].lx);
    tree[rt].rx=max(tree[2*rt].rx,tree[2*rt+1].rx);
    tree[rt].ly=min(tree[2*rt].ly,tree[2*rt+1].ly);
    tree[rt].ry=max(tree[2*rt].ry,tree[2*rt+1].ry);
}

int query(int rt,int qlx,int qrx,int qly,int qry){
    if(tree[rt].lx>=qlx&&tree[rt].rx<=qrx&&tree[rt].ly>=qly&&tree[rt].ry<=qry)return tree[rt].sum;
    if(tree[rt].lx>qrx||tree[rt].rx<qlx||tree[rt].ry<qly||tree[rt].ly>qry)return 0;
    int res=query(2*rt,qlx,qrx,qly,qry)+query(2*rt+1,qlx,qrx,qly,qry);
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int lst=0,kuai=sqrt(n);
    for(int i=1;i<=n;i++){
        int op;
        cin>>op;
        if(op==1){
            int px,py,pv;
            cin>>px>>py>>pv;
            px^=lst,py^=lst,pv^=lst;
//          cout<<px<<" "<<py<<" "<<pv<<endl;
            hch.push_back({px,py,pv});
            if(tong[n*(px-1)+py])poi[tong[n*(px-1)+py]].val+=pv;
            else poi[++cnt]={px,py,pv},tong[n*(px-1)+py]=cnt;
            if(i%kuai==0)build(1,1,1,cnt),hch.clear();
        }
        else if(op==2){
            int px,py,qx,qy;
            cin>>px>>py>>qx>>qy;
            px^=lst,py^=lst,qx^=lst,qy^=lst;
            int ans=0;
            ans+=query(1,px,qx,py,qy);
            for(int j=0;j<hch.size();j++){
                if(hch[j].x>=px&&hch[j].x<=qx&&hch[j].y>=py&&hch[j].y<=qy)ans+=hch[j].val;//cout<<hch[j].val<<" ";
            }
            cout<<ans<<endl;
            lst=ans;
        }
        else if(op==3)break;
    }
}

by lijianqiao @ 2024-07-16 15:10:21

@flywatre

by lijianqiao @ 2024-07-17 07:49:28

@lijianqiao

bool cmp1(node xx,node yy){
    return xx.x<yy.x;
}

by lijianqiao @ 2024-07-17 07:56:08

过了

by lijianqiao @ 2024-07-17 07:56:30

#include<bits/stdc++.h>
using namespace std;
#define int long long

struct node{
    int x,y,val;
}poi[200005];

int n,cnt;

bool cmp1(node xx,node yy){
    return xx.x<yy.x;
}

bool cmp2(node xx,node yy){
    return xx.y<yy.y;
}

struct node2{
    int lx,rx,ly,ry,sum;
}tree[800005];
vector<node> hch;
void build(int cx,int rt,int l,int r){
    if(l==r){
        tree[rt].lx=tree[rt].rx=poi[l].x;
        tree[rt].ly=tree[rt].ry=poi[l].y;
        tree[rt].sum=poi[l].val;
        return;
    }
    int mid=(l+r)>>1;
    nth_element(poi+l,poi+mid,poi+r+1,cx==1?cmp1:cmp2);
    build(1-cx,rt*2,l,mid);
    build(1-cx,rt*2+1,mid+1,r);
    tree[rt].sum=tree[2*rt].sum+tree[2*rt+1].sum;
    tree[rt].lx=min(tree[2*rt].lx,tree[2*rt+1].lx);
    tree[rt].rx=max(tree[2*rt].rx,tree[2*rt+1].rx);
    tree[rt].ly=min(tree[2*rt].ly,tree[2*rt+1].ly);
    tree[rt].ry=max(tree[2*rt].ry,tree[2*rt+1].ry);
}

int query(int rt,int qlx,int qrx,int qly,int qry){
    if(tree[rt].lx>=qlx&&tree[rt].rx<=qrx&&tree[rt].ly>=qly&&tree[rt].ry<=qry)return tree[rt].sum;
    if(tree[rt].lx>qrx||tree[rt].rx<qlx||tree[rt].ry<qly||tree[rt].ly>qry)return 0;
    int res=query(2*rt,qlx,qrx,qly,qry)+query(2*rt+1,qlx,qrx,qly,qry);
    return res;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    int lst=0,kuai=sqrt(n);
    while(1) {
        int op;
        cin>>op;
        if(op==1){
            int px,py,pv;
            cin>>px>>py>>pv;
            px^=lst,py^=lst,pv^=lst;
            hch.push_back({px,py,pv});
            poi[++cnt]={px,py,pv};
            if(cnt%kuai==0) build(1,1,1,cnt),hch.clear();
        }
        else if(op==2){
            int px,py,qx,qy;
            cin>>px>>py>>qx>>qy;
            px^=lst,py^=lst,qx^=lst,qy^=lst;
            int ans=0;
            ans+=query(1,px,qx,py,qy);
            for(int j=0;j<hch.size();j++){
                if(hch[j].x>=px&&hch[j].x<=qx&&hch[j].y>=py&&hch[j].y<=qy)ans+=hch[j].val;//cout<<hch[j].val<<" ";
            }
            cout<<ans<<endl;
            lst=ans;
        }
        else if(op==3)break;
    }
}