首页 > 代码库 > 【BZOJ4066】简单题 KDtree

【BZOJ4066】简单题 KDtree

2024-09-28 04:49:39   220人阅读

【BZOJ4066】简单题

Description

你有一个N*N的棋盘，每个格子内有一个整数，初始时的时候全部为0，现在需要维护两种操作：

命令

参数限制

内容

1 x y A

1<=x,y<=N，A是正整数

将格子x,y里的数字加上A

2 x1 y1 x2 y2

1<=x1<= x2<=N

1<=y1<= y2<=N

输出x1 y1 x2 y2这个矩形内的数字和

3

无

终止程序

 

Input

输入文件第一行一个正整数N。
接下来每行一个操作。每条命令除第一个数字之外，
均要异或上一次输出的答案last_ans，初始时last_ans=0。

Output

对于每个2操作，输出一个对应的答案。

Sample Input

4
1 2 3 3
2 1 1 3 3
1 1 1 1
2 1 1 0 7
3

Sample Output

3
5

HINT

数据规模和约定
1<=N<=500000,操作数不超过200000个，内存限制20M，保证答案在int范围内并且解码之后数据仍合法。

题解：想了一上午KDtree为什么不能旋转，发现显然不能啊~（但听说能搞成替罪的？蒟蒻表示不懂~）

依旧是改一改估价函数就行了，这题需要每加入一些点就暴力重构整棵树

 

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define rep for(int i=0;i<=1;i++)using namespace std;struct kd{	int sm[2],sn[2],v[2],sum,s,ls,rs;	kd (int a,int b,int c)	{ls=rs=0,sm[0]=sn[0]=v[0]=a,sm[1]=sn[1]=v[1]=b,s=sum=c;}	kd (){}};kd t[200010],p[200010];int n,m,A,B,C,D,root,ans;bool cmp(kd a,kd b){	return (a.v[D]==b.v[D])?(a.v[D^1]<b.v[D^1]):(a.v[D]<b.v[D]);}void pushup(int x,int y){	rep	t[x].sm[i]=max(t[x].sm[i],t[y].sm[i]),t[x].sn[i]=min(t[x].sn[i],t[y].sn[i]);	t[x].sum+=t[y].sum;}int build(int l,int r,int d){	if(l>r)	return 0;	int mid=l+r>>1;	D=d;	nth_element(p+l,p+mid,p+r+1,cmp);	t[mid]=p[mid];	t[mid].ls=build(l,mid-1,d^1),t[mid].rs=build(mid+1,r,d^1);	if(t[mid].ls)	pushup(mid,t[mid].ls);	if(t[mid].rs)	pushup(mid,t[mid].rs);	return mid;}void ins(int y){	int x=root,d=0;	while(x!=y)	{		pushup(x,y);		if(t[y].v[0]==t[x].v[0]&&t[y].v[1]==t[x].v[1])		{			t[x].s+=t[y].s,n--;			return ;		}		if(t[y].v[d]<t[x].v[d])	t[x].ls=(!t[x].ls)?y:t[x].ls,x=t[x].ls;		else	t[x].rs=(!t[x].rs)?y:t[x].rs,x=t[x].rs;		d^=1;	}}int query(int x){	if(!x||t[x].sm[0]<A||t[x].sn[0]>C||t[x].sm[1]<B||t[x].sn[1]>D)	return 0;	if(t[x].sm[0]<=C&&t[x].sn[0]>=A&&t[x].sm[1]<=D&&t[x].sn[1]>=B)	return t[x].sum;	int ret=0;	if(t[x].v[0]>=A&&t[x].v[0]<=C&&t[x].v[1]>=B&&t[x].v[1]<=D)	ret+=t[x].s;	ret+=query(t[x].ls)+query(t[x].rs);	return ret;}int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int main(){	rd();	int i,j,e;	root=1,m=10000;	while(1)	{		e=rd();		if(e==3)	break;		if(e==1)		{			A=rd()^ans,B=rd()^ans,C=rd()^ans;			t[++n]=kd(A,B,C),ins(n);			if(n==m)			{				for(i=1;i<=n;i++)	p[i]=kd(t[i].v[0],t[i].v[1],t[i].s);				root=build(1,n,0),m+=10000;			}		}		else		{			A=rd()^ans,B=rd()^ans,C=rd()^ans,D=rd()^ans;			ans=query(root);			printf("%d\n",ans);		}	}	return 0;}

 

【BZOJ4066】简单题 KDtree


联系
我们