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
    
     #define pb push_backusing 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
     
      S[N],G[N],E[N];map
      
       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
       
        =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]
        
         
          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
          
           Q; for(int i=Ly[x],u;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
            
             >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;}