Solution：P14645 [POI 2025/2026 #1] 传话 / Dostawy

一：题意

在一个 $n \times n$ 的网格中，存在堡垒和障碍物。每天早上，每过一个单位时间，会有一个英雄出现在 $(1,1)$，其目的地为任意一个堡垒，并且所有英雄每过一个单位时间，可以移动到一个相邻的位置。每天晚上，会有一个堡垒被修建或者被拆除。求每一天，所有堡垒都被到达所需的最小时间。

二：思路

首先，我们尝试处理没有修改的情况。

有一个比较显然的贪心策略为让先出现的英雄前往尽可能远的堡垒，这样显然是更优的。我们可以用 BFS 求出每个堡垒和起点的距离，按照距离从远到近排序后，每个堡垒被到达所需的时间为 $v_{i} = d_{i} + i - 1$（其中 $d_{i}$ 为堡垒和起点的距离），答案为 $\max v_{i}$。

接下来考虑修改会对答案造成什么影响。

无论如何修改，每个点和起点的距离是不变的（因为不会出现新的障碍物，修改不影响路径）。

按照 $v_{i} = d_{i} + i - 1$，由于 $d_{i}$ 不变，每次修改只是在原先的堡垒之间插入或删除堡垒，于是我们只需要维护在某个堡垒前面有多少个已经被建造的堡垒即可。单独维护堡垒需要维护插入操作，不妨直接维护所有坐标，按照距离从近到远排序，那么修建操作就是让前面的堡垒答案加 $1$，当前堡垒答案设为 $d_{i} + c_{i}$（$c_{i}$ 为距离更远的堡垒数量），拆除就是让前面的堡垒答案减 $1$，当前堡垒答案设为负无穷。用线段树维护区间加，单点覆盖和区间最大值即可。

三：实现

线段树上需要额外维护区间堡垒的数量。为了将网格塞入线段树，需要坐标一维化。

code：

#include<iostream>
#include<cstring>
#include<queue>
#include<bitset>
#include<algorithm>
using namespace std;

const int DIR[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
int n,q,cnt[1000005],pos[1000005];		//cnt用来暂存该点前被激活点的数量，pos[i]表示原本编号为i的点排序后所在的位置
char c[1001][1001];
bitset<1000005> mark;			//标记某个点是否有堡垒 

struct NodeT{
	int l,r;
	int mx,add,sum;			//add为mx的懒标记，sum为区间内堡垒的数量 
}node[4000005];

struct NodeQ{			//用于bfs时塞入队列的节点 
	int x,y;
};

struct NodeA{		//v表示该点的距离，i表示该点排序前的编号 
	int v,i;
	bool operator < (const NodeA &n) const		//将可达点按距离从小到大排序 
	{
		return v < n.v;
	}
}a[1000005];

inline void push_up(int i){
	node[i].mx = max(node[i << 1].mx,node[i << 1 | 1].mx);
	node[i].sum = node[i << 1].sum + node[i << 1 | 1].sum;
	return;
}

inline void push_down(int i){
	int &add = node[i].add;
	node[i << 1].add += add;
	node[i << 1].mx += add;
	node[i << 1 | 1].add += add;
	node[i << 1 | 1].mx += add;
	add = 0;
	return;
}

void build(int i,int l,int r){
	node[i].l = l;
	node[i].r = r;
	if(l == r)
	{
		node[i].mx = (mark[a[l].i] ? cnt[a[l].i] + a[l].v : 0x80808080);		//没有堡垒的地方设为负无穷 
		node[i].sum = (mark[a[l].i] ? 1 : 0);
		return;
	}
	int mid = (l + r) >> 1;
	build(i << 1,l,mid);
	build(i << 1 | 1,mid + 1,r);
	push_up(i);
	return;
}

void modify_add(int i,int l,int r,int k){
	if(node[i].l > r || node[i].r < l)
	{
		return;
	}
	if(node[i].l >= l && node[i].r <= r)
	{
		node[i].add += k;
		node[i].mx += k;
		return;
	}
	push_down(i);
	modify_add(i << 1,l,r,k);
	modify_add(i << 1 | 1,l,r,k);
	push_up(i);
	return;
}

void modify_cov(int i,int x,int k){
	if(node[i].l > x || node[i].r < x)
	{
		return;
	}
	if(node[i].l == x && node[i].r == x)
	{
		node[i].add = 0;
		node[i].mx = k;
		return;
	}
	push_down(i);
	modify_cov(i << 1,x,k);
	modify_cov(i << 1 | 1,x,k);
	push_up(i);
	return;
}

void modify_sum(int i,int x,int k){
	if(node[i].l > x || node[i].r < x)
	{
		return;
	}
	if(node[i].l == x && node[i].r == x)
	{
		node[i].sum = k;
		return;
	}
	push_down(i);
	modify_sum(i << 1,x,k);
	modify_sum(i << 1 | 1,x,k);
	push_up(i);
	return;
}

int query(int i,int l,int r){
	if(node[i].l > r || node[i].r < l)
	{
		return 0;
	}
	if(node[i].l >= l && node[i].r <= r)
	{
		return max(0,node[i].mx);
	}
	push_down(i);
	return max(query(i << 1,l,r),query(i << 1 | 1,l,r));
}

int query_sum(int i,int l,int r){
	if(node[i].l > r || node[i].r < l)
	{
		return 0;
	}
	if(node[i].l >= l && node[i].r <= r)
	{
		return node[i].sum;
	}
	push_down(i);
	return query_sum(i << 1,l,r) + query_sum(i << 1 | 1,l,r);
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	memset(a,0x80,sizeof(a));		//初始化为负无穷 
	a[1].v = 0;
	cin>>n>>q;
	for(int i = 1;i <= n;i += 1)
	{
		for(int j = 1;j <= n;j += 1)
		{
			cin>>c[i][j];
			a[(i - 1) * n + j].i = (i - 1) * n + j; 		//坐标一维化 
		}
	}
	queue<NodeQ> que;
	que.push(NodeQ{1,1});
	while(!que.empty())			//bfs求距离 
	{
		int x = que.front().x,y = que.front().y,j = (x - 1) * n + y;
		for(int i = 0;i <= 3;i += 1)
		{
			int cx = DIR[i][0] + x,cy = DIR[i][1] + y,k = (cx - 1) * n + cy;
			if(1 <= cx && cx <= n && 1 <= cy && cy <= n && c[cx][cy] != '#' && a[k].v == (int)(0x80808080))
			{
				a[k].v = a[j].v + 1;
				que.push(NodeQ{cx,cy});
			}
		}
		que.pop();
	}
	sort(a + 1,a + 1 + n * n);				//将可达点排序
	for(int i = n * n,j = 0;i >= 1;i -= 1)			//按顺序处理每个点前面被激活点的数量 
	{
		int x = (a[i].i - 1) / n + 1,y = a[i].i - (x - 1) * n;
        cnt[a[i].i] = j;
        pos[a[i].i] = i;
		if(c[x][y] == 'F')						//标记有堡垒的地方
		{
			mark[a[i].i] = true;
			j += 1;
		}
	}
	build(1,1,n * n);
	for(int i = 0;i <= q;i += 1)
	{
		cout<<query(1,1,n * n)<<'\n';
		if(i != q)
		{
			int x,y,j;
			cin>>x>>y;
			j = (x - 1) * n + y;		//j是所给坐标的编号，pos[j]是所给坐标在线段树上的位置 
			if(mark[j])		//拆除堡垒 
			{
				modify_add(1,1,pos[j] - 1,-1);
				modify_cov(1,pos[j],0x80808080);
				modify_sum(1,pos[j],0);
				mark[j] = false;
			}
			else		//修建堡垒 
			{
				modify_add(1,1,pos[j] - 1,1);
				modify_cov(1,pos[j],a[pos[j]].v + query_sum(1,pos[j] + 1,n * n));
				modify_sum(1,pos[j],1); 
				mark[j] = true;
			}
		}
	}
	return 0;
}

四：写在最后

代码细节很多，有疑问可以私信或者评论，我会尽可能解答的。