kdt 20pts RE求条
查看原帖
kdt 20pts RE求条
779369
lijianqiao楼主2024/7/16 15:02
#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;
	}
}

2024/7/16 15:02
加载中...