UVA11297 Census（kd-tree）

题意：给定一个 \(n\times n\) 的网格，要求支持修改和询问某个矩阵的最大值和最小值。

解法多样，可以用二维线段树，我用的是 \(kd-tree\)。

那么这题就很裸了，我在这里只提几点需要注意的地方。

首先就是建树以及修改时的比较一定要判断当前维度相等的情况，这时就要比较下一维度。

不然你修改时可能永远找不到你要找的那个点，导致 \(TLE\)。

其次是 \(up\) 的时候一定要判断有没有左右儿子，不然最小值会 \(WA\)。

代码如下：

#include<bits/stdc++.h>

#define N 510
#define lc t[u].ch[0]
#define rc t[u].ch[1]
#define INF 0x7fffffff

using namespace std;

bool D;

struct Point
{
	int num[2],val;
	Point(){};
	Point(int x,int y,int vall)
	{
		num[0]=x,num[1]=y,val=vall;
	}
	bool operator == (Point a)
	{
		return num[0]==a.num[0]&&num[1]==a.num[1];
	}
	bool operator < (const Point &b) const
	{
		if(num[D]==b.num[D]) return num[D^1]<b.num[D^1];//需要注意的地方
		return num[D]<b.num[D];
	}
}p[N*N];

struct kdtree
{
	int ch[2],minn[2],maxn[2],maxval,minval;
	Point x;
}t[N*N];

struct data
{
	int maxn,minn;
	data(){};
	data(int a,int b)
	{
		maxn=a,minn=b;
	}
	data operator + (data a)
	{
		return data(max(maxn,a.maxn),min(minn,a.minn));
	}
};

int n,q,tot,root;

void up(int u)
{
	for(int i=0;i<2;i++)
	{
		t[u].maxn[i]=t[u].minn[i]=t[u].x.num[i];
		if(lc)
		{
			t[u].maxn[i]=max(t[u].maxn[i],t[lc].maxn[i]);
			t[u].minn[i]=min(t[u].minn[i],t[lc].minn[i]);
		}
		if(rc)
		{
			t[u].maxn[i]=max(t[u].maxn[i],t[rc].maxn[i]);
			t[u].minn[i]=min(t[u].minn[i],t[rc].minn[i]);
		}
	}
	t[u].minval=t[u].maxval=t[u].x.val;
	if(lc)t[u].minval=min(t[u].minval,t[lc].minval),t[u].maxval=max(t[u].maxval,t[lc].maxval);//需要注意的地方
	if(rc)t[u].minval=min(t[u].minval,t[rc].minval),t[u].maxval=max(t[u].maxval,t[rc].maxval);
}

int build(int l,int r,bool d)
{
	if(l>r) return 0;
	int u=(l+r)>>1;
	D=d,nth_element(p+l,p+u,p+r+1);
	t[u].x=p[u];
	lc=build(l,u-1,d^1);
	rc=build(u+1,r,d^1);
	up(u);
	return u;
}

bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2)
{
	return x1<=X1&&y1<=Y1&&x2>=X2&&y2>=Y2;
}

bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2)
{
	return x1>X2||y1>Y2||x2<X1||y2<Y1;
}

data query(int u,int x1,int y1,int x2,int y2)
{
	if(out(x1,y1,x2,y2,t[u].minn[0],t[u].minn[1],t[u].maxn[0],t[u].maxn[1])) return data(-INF,INF);
	data ans=data(-INF,INF);
	if(in(x1,y1,x2,y2,t[u].minn[0],t[u].minn[1],t[u].maxn[0],t[u].maxn[1])) return data(t[u].maxval,t[u].minval);
	if(in(x1,y1,x2,y2,t[u].x.num[0],t[u].x.num[1],t[u].x.num[0],t[u].x.num[1])) ans=ans+data(t[u].x.val,t[u].x.val);
	ans=ans+query(lc,x1,y1,x2,y2);
	ans=ans+query(rc,x1,y1,x2,y2);
	return ans;
}

void update(int u,Point x,bool d)
{
	if(t[u].x==x)
	{
		t[u].x.val=x.val;
		up(u);
		return;
	}
	D=d;
	if(x<t[u].x) update(lc,x,d^1);
	else update(rc,x,d^1); 
	up(u);
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			int x;
			scanf("%d",&x);
			p[++tot]=Point(i,j,x);
		}
	}
	root=build(1,n*n,0);
	scanf("%d",&q);
	while(q--)
	{
		char ch=getchar();
		while(ch!='q'&&ch!='c') ch=getchar();
		if(ch=='q')
		{
			int x1,y1,x2,y2;//左上、右下 
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			data ans=query(root,x1,y1,x2,y2);
			printf("%d %d\n",ans.maxn,ans.minn);
		}
		if(ch=='c')
		{
			int x,y,val;
			scanf("%d%d%d",&x,&y,&val);
			update(root,Point(x,y,val),0);
		}
	}
}