题解：P16162 [ICPC 2016 NAIPC] Whiteboard

lailai0916 · 2026-08-30 18:50:56 · 题解

题意简述

画笔从白板左下角沿给定路径移动。干涸前，经过一个格子会把它涂黑；干涸后，经过一个格子会把它擦白。求能得到目标图案的最早与最晚干涸时刻。

解题思路

一个格子的最终颜色只由最后一次访问决定。设格子 c 的最后访问时刻为 v_c，从未访问则记为 0。若画笔在时刻 d 干涸，它仍会在时刻 d 涂黑，而从时刻 d+1 开始擦除。因此：

记整条路径的最后时刻为 T。所有目标黑格都要求 d\ge v_c，所有被访问过的目标白格都要求 d<v_c。于是可行时刻构成一个整数区间：

若目标黑格从未被访问，直接无解。否则，只需再判断 L\le R。

问题转化为求所有格子的最后访问时刻。路径总长度可能远大于白板面积，不能逐步模拟，但白板最多只有 10^6 个格子。倒序处理命令时，一个尚未赋值的格子第一次出现在某条线段中，这条线段就是最后一次访问它的命令。

对每一行建立一个后继并查集。位置 j 的代表元表示本行中不小于 j 的第一个尚未赋值位置，行末额外放一个哨兵。对每一列也建立同样的结构。

倒序扫描一条横向线段 [l,r] 时，从 root(l) 开始。若得到的位置仍不超过 r，就计算它的最后访问时刻，并把它同时从所在行和所在列删除。随后再次查询当前位置的后继，直到越过右端点。纵向线段完全对称。

必须同时在两套并查集中删除。一个格子可能先由横向命令确定，也可能先由纵向命令确定；从两边同时删除，才能保证它不会在更早的其他方向命令中再次出现。

设某条命令从 (x_1,y_1) 开始，起始时刻为 t。它是水平或竖直线段，格子 (x,y) 在该命令中的访问时刻为：

读取命令时保存起点、终点与起始时刻。起始格第一次接触画笔的时刻是 1，所以总路径的最后时刻为 1 加所有移动距离之和。线段包含两个端点；相邻命令的公共端点虽然会重复出现，但倒序删除会保留其中较晚的一次。

每个命令只产生常数次额外操作，每个格子最多被枚举和删除一次。时间复杂度为 O((hw+n)\alpha(hw))，空间复杂度为 O(hw+n)。

正确性证明

对任意格子，只看最后一次访问。若它发生在干涸时刻以前或恰好等于干涸时刻，最后一次操作是涂黑；若发生在其后，最后一次操作是擦除。更早的所有访问都会被最后一次覆盖。因此，由 v_c 推出的黑白条件充要，可行时刻正是区间 [L,R]。

倒序处理命令。归纳假设在处理某条命令前，已经删除的格子都已得到真实的最后访问时刻，未删除格子在所有更晚命令中均未出现。当前线段中每个未删除格子因此把本命令作为最后一次访问，时间公式准确；赋值后从两套并查集中删除，使归纳条件继续成立。

后继并查集从线段左端开始，反复返回下一个未删除位置，直到越过右端。它不会跳过线段内的未删除格子，也不会返回已删除格子。因此，每个被访问过的格子恰好在其最后一条命令中赋值，从未被访问的格子保持为零。

最后逐格汇总得到所有黑格下界与白格上界。若存在未访问黑格或 L>R，确实不存在合法时刻；否则区间中的每个整数都满足全部格子的最终颜色要求，所以输出的两个端点正确。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=1000005;
const int M=2000005;
struct seg
{
    int x1,y1,x2,y2;
    ll t;
}q[N];
char a[N];
int h,w;
int row[M],col[M];
ll lst[N];
int root(int f[],int x)
{
    return f[x]==x?x:f[x]=root(f,f[x]);
}
void del(int x,int y)
{
    int p=x*(w+1)+y;
    row[p]=root(row,p+1);
    p=y*(h+1)+x;
    col[p]=root(col,p+1);
}
void scan_row(const seg &s)
{
    int l=min(s.y1,s.y2),r=max(s.y1,s.y2);
    int b=s.x1*(w+1);
    int y=root(row,b+l)-b;
    while(y<=r)
    {
        lst[s.x1*w+y]=s.t+abs(y-s.y1);
        del(s.x1,y);
        y=root(row,b+y)-b;
    }
}
void scan_col(const seg &s)
{
    int l=min(s.x1,s.x2),r=max(s.x1,s.x2);
    int b=s.y1*(h+1);
    int x=root(col,b+l)-b;
    while(x<=r)
    {
        lst[x*w+s.y1]=s.t+abs(x-s.x1);
        del(x,s.y1);
        x=root(col,b+x)-b;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>h>>w>>n;
    string s;
    for(int i=0;i<h;i++)
    {
        cin>>s;
        for(int j=0;j<w;j++)a[i*w+j]=s[j];
    }
    int x=h-1,y=0;
    ll t=1;
    for(int i=0;i<n;i++)
    {
        int d;
        cin>>s>>d;
        q[i]={x,y,x,y,t};
        if(s[0]=='u')q[i].x2-=d;
        else if(s[0]=='d')q[i].x2+=d;
        else if(s[0]=='l')q[i].y2-=d;
        else q[i].y2+=d;
        x=q[i].x2;
        y=q[i].y2;
        t+=d;
    }
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<=w;j++)row[i*(w+1)+j]=i*(w+1)+j;
    }
    for(int i=0;i<w;i++)
    {
        for(int j=0;j<=h;j++)col[i*(h+1)+j]=i*(h+1)+j;
    }
    for(int i=n-1;i>=0;i--)
    {
        if(q[i].x1==q[i].x2)scan_row(q[i]);
        else scan_col(q[i]);
    }
    ll mn=0,mx=t;
    bool ok=1;
    for(int i=0;i<h*w;i++)
    {
        if(a[i]=='#')
        {
            if(!lst[i])ok=0;
            mn=max(mn,lst[i]);
        }
        else if(lst[i])mx=min(mx,lst[i]-1);
    }
    if(!ok||mn>mx)cout<<-1<<' '<<-1<<'\n';
    else cout<<mn<<' '<<mx<<'\n';
    return 0;
}