Description
给出一张四连通网格图,其中有 \(n\) 个点是连通的,维护以下两种操作:
1.把某个点变黑
2.给出一个白点,查询离这个白点最近的黑点的距离
题面
Solution
我们把每一行看作一个节点,建立一棵树
然后点分治维护这两个操作即可
实际上就是动态加入黑点,查询离某个点最近的黑点
唯一的区别在于:
走到这个节点之后还会在这个节点所代表的行里面走,设查询的为 \(x\),某个黑点为 \(u\)
要求: \(min(dis[u]+dis[x]+|y_u-y_x|)\)
\(dis[i]\) 表示从 \(i\) 出发走到这个重心所代表的行的最短路,\(y_i\) 表示走最短路碰到这个节点所代表的行的纵坐标
两者都可以从重心 \(bfs\) 求出
然后对于每一个重心维护数状数组查询 \(min(dis[u]+dis[x]+|y_u-y_x|)\)
把绝对值拆掉,用两个树状数组维护就行了,分别对应前后缀查询
值得注意的是:
这题的重心要是带权重心,否则预处理就会 \(TLE\)
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=3e5+10,M=22,inf=1e9;
int n,m=0,tt=0,cnt=0,b[N],s[N],Lx[N],Ly[N],fa[N];
vector<int>S[N],G[N],E[N];
map<int,int>id[N];
inline void priwork(){
for(int i=1;i<=m;i++){
if(S[i].empty())continue;
sort(S[i].begin(),S[i].end());
for(int j=0,si=S[i].size(),x,k=0;j<si;j++){
x=S[i][j];id[i][x]=++tt;
if(j && S[i][j-1]+1==x)G[tt].pb(tt-1),G[tt-1].pb(tt);
else ++cnt,Lx[cnt]=i,Ly[cnt]=j;
b[tt]=cnt;s[cnt]++;
while(k<(int)S[i-1].size() && S[i-1][k]<x)k++;
if(k<(int)S[i-1].size() && S[i-1][k]==x){
E[b[id[i-1][x]]].pb(cnt),E[cnt].pb(b[id[i-1][x]]);
G[id[i-1][x]].pb(tt),G[tt].pb(id[i-1][x]);
}
}
}
for(int i=1;i<=n;i++){
sort(E[i].begin(),E[i].end());
E[i].erase(unique(E[i].begin(),E[i].end()),E[i].end());
}
}
int son[N]={inf},sz[N],rt=0,sum,p[N][M],dis[N][M];bool vis[N];
inline void getroot(int x,int last){
sz[x]=s[x];son[x]=0;
for(int i=E[x].size()-1;i>=0;i--){
int u=E[x][i];
if(u==last || vis[u])continue;
getroot(u,x);sz[x]+=sz[u];son[x]=max(son[x],sz[u]);
}
son[x]=max(son[x],sum-sz[x]);
if(son[x]<son[rt])rt=x;
}
vector<int>t1[N],t2[N];int dep[N];
inline void add1(int o,int x,int t){
for(int i=x;i<=s[o];i+=(i&(-i)))t1[o][i]=min(t1[o][i],t);
}
inline int qry1(int o,int x){
int ret=inf;
for(int i=x;i>=1;i-=(i&(-i)))ret=min(ret,t1[o][i]);
return ret;
}
inline void add2(int o,int x,int t){
for(int i=x;i>=1;i-=(i&(-i)))t2[o][i]=min(t2[o][i],t);
}
inline int qry2(int o,int x){
int ret=inf;
for(int i=x;i<=s[o];i+=(i&(-i)))ret=min(ret,t2[o][i]);
return ret;
}
inline void build(int x,int d){
queue<int>Q;
for(int i=Ly[x],u;i<Ly[x]+s[x];i++){
u=id[Lx[x]][S[Lx[x]][i]];
p[u][d]=i-Ly[x]+1;dis[u][d]=0;Q.push(u);
}
while(!Q.empty()){
int x=Q.front();Q.pop();
for(int i=G[x].size()-1;i>=0;i--){
int u=G[x][i];
if(vis[b[u]] || p[u][d])continue;
p[u][d]=p[x][d],dis[u][d]=dis[x][d]+1,Q.push(u);
}
}
for(int i=0;i<=s[x];i++)t1[x].pb(inf),t2[x].pb(inf);
}
inline void solve(int x,int d){
vis[x]=1;dep[x]=d;build(x,d);
for(int i=E[x].size()-1;i>=0;i--){
int u=E[x][i];if(vis[u])continue;
rt=0;sum=sz[u];getroot(u,x);
fa[rt]=x;solve(rt,d+1);
}
}
inline void Modify(int y){
int x=b[y],d;
while(x){
d=dep[x];
add1(x,p[y][d],dis[y][d]-p[y][d]);
add2(x,p[y][d],dis[y][d]+p[y][d]);
x=fa[x];
}
}
inline int query(int y){
int ret=inf,d,x=b[y];
while(x){
d=dep[x];
ret=min(ret,dis[y][d]+p[y][d]+qry1(x,p[y][d]));
ret=min(ret,dis[y][d]-p[y][d]+qry2(x,p[y][d]));
x=fa[x];
}
if(ret<N)return ret;
return -1;
}
int main(){
int x,y,Q,op;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&x,&y);
m=max(x,m);S[x].pb(y);
}
priwork();
rt=0;sum=n;getroot(1,1);solve(1,0);
cin>>Q;
while(Q--){
scanf("%d%d%d",&op,&x,&y);
if(op==2)printf("%d\n",query(id[x][y]));
else Modify(id[x][y]);
}
return 0;
}