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

Ptll · 2026-04-09 21:02:50 · 题解

题解

我们发现贪心是好想的，只需考虑每个点所到达的最短时间，按照时间大小从大往小排序即可。

因为不同出发的点都带有权值（即它的出发时间），这个东西是不好维护的，但我们可以发现它的出发时间每次最多只会 +1 或 -1，而这个操作又是区间修改，这提示我们往线段树上想。

我们可以用线段树维护区间最大值，这样查询是 O(1) 的，我们考虑对于未出现的时间，这些点是不需要更新的，所以初始值可以直接赋为 0。

考虑对于时间 \ge 新的时间的点是无需改动的，接下来考虑 < 它的部分。

我们发现加入与删除的性质相同，这里提供加入的解法。

我们发现对于完全 < 加入的时间只需区间 +1 就可以了。

但对于 = 它的点只需修改有多少个数 \ge 它即可，这一点可以用树状数组维护。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#include <queue>
#include <set>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T*lt,T*rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e3+5,M=4e6+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
ll dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
ll n,q,dis[N][N],num[M]; 
bool vis[N][N],bis[N][N];
string s;
queue<pll> pq;
struct BIT {
    ll t[M];
    inline ll lowbit (ll x) {
        return x&(-x);
    }
    inline void add (ll x,ll val) {
        x=n*n-x+1;
        while (x<=n*n) {
            t[x]+=val;
            x+=lowbit(x);
        }
    }
    inline ll query (ll x) {
        x=n*n-x+1;
        ll ans=0;
        while (x) {
            ans+=t[x];
            x-=lowbit(x);
        }
        return ans;
    }
} trl;
struct Segtree {
    ll t[M],lt[M];
    inline void push_up (ll pos) {
        t[pos]=max(t[pos<<1],t[pos<<1|1]);
    }
    inline void push_down(ll pos) {
        if(t[pos<<1]) {
            t[pos<<1]+=lt[pos];
        }
        if(t[pos<<1|1]) {
            t[pos<<1|1]+=lt[pos];
        }
        lt[pos<<1]+=lt[pos];
        lt[pos<<1|1]+=lt[pos];
        lt[pos]=0;
    }
    void addl (ll pos,ll l,ll r,ll L,ll R,ll val) {
        if (L<=l&&r<=R) {
            if (t[pos]) {
                t[pos]+=val;
            }
            lt[pos]+=val;
            return ;
        }
        ll mid=(l+r)>>1;
        push_down(pos);
        if (L<=mid) {
            addl(pos<<1,l,mid,L,R,val);
        }
        if (R>mid) {
            addl(pos<<1|1,mid+1,r,L,R,val);
        }
        push_up(pos);
    }
    void add (ll pos,ll l,ll r,ll x) {
        if (l==r) {
            t[pos]=0;
            if (num[l]) {
                t[pos]=l+trl.query(l);
            }
            return ;
        }
        ll mid=(l+r)>>1;
        push_down(pos);
        if (x<=mid) {
            add(pos<<1,l,mid,x);
        }
        else {
            add(pos<<1|1,mid+1,r,x);
        }
        push_up(pos);
    }
} tr;
void bfs () {
    dis[1][1]=0;
    pq.push({1,1});
    while (!pq.empty()) {
        pll d=pq.front();
        pq.pop();
        ll x=d.first,y=d.second;
        for (ll i=1;i<=4;i++) {
            ll xx=x+dx[i],yy=y+dy[i];
            if (vis[xx][yy]||xx>n||xx<1||yy>n||yy<1) {
                continue;
            }
            if (dis[xx][yy]>dis[x][y]+1) {
                dis[xx][yy]=dis[x][y]+1;
                pq.push({xx,yy});
            }
        }
    }
}
inline void add (ll pos) {
    num[pos]++;
    trl.add(pos,1);
    tr.add(1,1,n*n,pos);
    if (pos!=1) {
        tr.addl(1,1,n*n,1,pos-1,1);
    }
}
inline void del (ll pos) {
    num[pos]--;
    trl.add(pos,-1);
    tr.add(1,1,n*n,pos);
    if (pos!=1) {
        tr.addl(1,1,n*n,1,pos-1,-1);
    }
}
inline void solve () {
    n=read(),q=read();
    for (ll i=1;i<=n;i++) {
        cin>>s;
        for (ll j=1;j<=n;j++) {
            if (s[j-1]=='Z'||s[j-1]=='F') {
                bis[i][j]=1;
            }
            if (s[j-1]=='#') {
                vis[i][j]=1;
            }
            dis[i][j]=inf;
        }
    }
    bfs();
    for (ll i=1;i<=n;i++) {
        for (ll j=(i==1?2:1);j<=n;j++) {
            if (bis[i][j]) {
                add(dis[i][j]);
            }
        }
    }
    print(max(0ll,tr.t[1]-1));
    puts(""); 
    while (q--) {
        ll x=read(),y=read();
        if (bis[x][y]) {
            del(dis[x][y]);
        }
        else {
            add(dis[x][y]);
        }
        bis[x][y]^=1;
        print(max(0ll,tr.t[1]-1));
        puts(""); 
    }
}
int main () {
//  freopen("dostawy.in","r",stdin);
//  freopen("dostawy.out","w",stdout);
    ll T=1;
//  T=read();
    while (T--) {
        solve();
    }
    return 0;
}