题意:给定一个 \(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);
}
}
}
标签:Census,return,Point,int,tree,UVA11297,num,bool,X2
From: https://www.cnblogs.com/ez-lcw/p/16843064.html