0分代码求调
查看原帖
0分代码求调
606216
xiaochen_supporter楼主2025/8/4 18:55
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll N=200010;
const double alpha=0.75;
//#define lc t[u].ls;
//#define t[u].rs t[u].rs;
struct Point 
{
	ll dim[2],val;
	Point(){};
	Point(ll x,ll y,ll vall){dim[0]=x,dim[1]=y,val=vall;} 
};
Point order[N];
ll cnt;
struct kd_tree
{
	ll ls,rs;
	ll mi[2],ma[2];
	ll sum;
	ll size;
	Point p;
}t[N];
ll tot,root;
ll top,tree_stack[N];
ll now;
bool cmp(Point a,Point b){return a.dim[now]<b.dim[now];}
void update(ll u) 
{
	for(ll i=0;i<2;i++) 
	{
		t[u].mi[i]=t[u].ma[i]=t[u].p.dim[i];
		if(t[u].ls)
		{
			t[u].mi[i]=min(t[u].mi[i],t[t[u].ls].mi[i]);
			t[u].ma[i]=max(t[u].ma[i],t[t[u].ls].ma[i]);
		}
		if(t[u].rs)
		{
			t[u].mi[i]=min(t[u].mi[i],t[t[u].rs].mi[i]);
			t[u].ma[i]=max(t[u].ma[i],t[t[u].rs].ma[i]);
		}
	}
	t[u].sum=t[t[u].ls].sum+t[u].p.val+t[t[u].rs].sum;
	t[u].size=t[t[u].ls].size+t[t[u].rs].size+1;
}
void slap(ll u)
{
	if(!u) return ;
	slap(t[u].ls);
	order[++cnt]=t[u].p;
	tree_stack[++top]=u;
	slap(t[u].rs);
}
ll build(ll l,ll r,ll d)
{
	if(l>r) return 0;
	ll u;
	if(top) u=tree_stack[top--];
	else u=++tot;
	ll mid=(l+r)>>1;
	now=d;
	nth_element(order+l,order+mid,order+r+1,cmp);
	t[u].p=order[mid];
	t[u].ls=build(l,mid-1,d^1);
	t[u].rs=build(mid+1,r,d^1);
	update(u);
	return u;	
} 
bool notbalance(ll u)
{
	if(t[t[u].ls].size>alpha*t[u].size||t[t[u].rs].size>alpha*t[u].size) 
		return true;
	return false;
}
void Insert(ll &u,Point now,ll d)
{
	if(!u)
	{
		if(top) u=tree_stack[top--];
		else u=++tot;
		t[u].ls=t[u].rs=0,t[u].p=now;
		update(u);
		return ;
	}
	if(now.dim[d]<=t[u].p.dim[d]) Insert(t[u].ls,now,d^1);
	else Insert(t[u].rs,now,d^1);
	update(u);
	if(notbalance(u))
	{
		cnt=0;
		slap(u);
		u=build(1,t[u].size,d);
	}
}
ll query(ll u,ll x1,ll y1,ll x2,ll y2)
{
	if(!u) return 0;
	ll X1=t[u].mi[0],Y1=t[u].mi[1],X2=t[u].ma[0],Y2=t[u].ma[1];
	if(x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2) return t[u].sum;
	if(x1>X2||x2<X1||y1>Y2||y2<Y1) return 0;
	ll ans=0;
	X1=t[u].p.dim[0],Y1=t[u].p.dim[1],X2=t[u].p.dim[0],Y2=t[u].p.dim[1];
	if(x1<=X1&&x2>=X2&&y1<=Y1&&y2>=Y2) ans+=t[u].p.val;
	ans+=query(t[u].ls,x1,y1,x2,y2)+query(t[u].rs,x1,y1,x2,y2);
	return ans;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0); 
	ll n;
	cin>>n;
	ll ans=0;
	while(1)
	{
		ll opt;
		scanf("%d",&opt);
		if(opt==1)
		{
			ll x,y,val;
			scanf("%d%d%d",&x,&y,&val);
			x^=ans,y^=ans,val^=ans;
			Insert(root,Point(x,y,val),0);
		}
		if(opt==2)
		{
			ll x1,x2,y1,y2;
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			x1^=ans,y1^=ans,x2^=ans,y2^=ans;
			ans=query(root,x1,y1,x2,y2);
			printf("%d\n",ans);
		}
		if(opt==3) return 0;
	}
	return 0;
}
2025/8/4 18:55
加载中...