P7636 [COCI2010-2011#5] SLIKA 题解

· · 题解

题目：[COCI2010-2011#5] SLIKA

思路

逆序存储

顺序存储只能得到 60 分，原因在于浪费了太多的时间在无用的 PAINT 函数中。考虑如下片段：

SAVE
PAINT ...
...
PAINT ...
LOAD 1

此时 LOAD 函数会使得很多 PAINT 函数被清除，但是朴素的算法会把这些函数全部都执行一遍，浪费了很多时间。因此，我们需要判断哪些 PAINT 函数是真正被调用的。

但是从前往后扫描有可能无法得出正确的顺序。考虑如下片段（从隔壁题解看到的）：

PAINT ...
SAVE
*PAINT ...
SAVE
LOAD 1
LOAD 2

带 \small* 号的 PAINT 函数实际上是被调用的。但是如果只是单纯地删除，这个函数就会被认为是无效的，从而得到错误的答案。

此时我们就需要从后往前判断 PAINT 函数真正的执行顺序。这同时启发我们，不仅可以找到 PAINT 函数的调用顺序，或许我们还可以用另外一种角度去调用这些函数。

调用 PAINT 函数的另外一种方案

回到曾经写过的一道题：铺地毯。在这道题中，我们按照顺序在平面上覆盖矩形，最后询问某点上最后一个覆盖的矩形编号。

然而，这道题还有另外一种做法：从最后覆盖平面的矩形开始，倒序查找。只要找到某个矩形 \text{M} 覆盖了该点，则 \text{M} 必定是该点上最后一个覆盖的矩形。

这样做的正确性显然：后盖上的矩形必定在先盖上的矩形之上。所以只要 \text{M} 覆盖了点 P，\text{M} 之前的矩形就不可能是最后一个覆盖的矩形。

我们再考虑如下问题：如何判断每一个点上最后一个覆盖的矩形编号？

相信你也已经得到了答案：倒序查找每一个矩形，在其范围内覆盖没有被覆盖过的点。正确性也显然。

回到 SLIKA 这道题。既然可以倒序调用 PAINT 函数，那么我们就模仿着铺地毯的方式去覆盖这个画布。

显然我们能写出如下的伪代码片段：

倒序遍历操作:
    如果操作为 LOAD:
        返回到对应的 SAVE 处
    如果操作为 PAINT:
        遍历所有能绘制的位置:
            如果这个格子颜色为 1 (没有上过色):
                给这个格子上色

但是我们很快就会发现：到了后面，每一个 PAINT 函数都会经过很多次上过色的格子，从而浪费了很多的时间。显然这个方法还需要改进。

每个格子最多只会被修改一次

我们考虑用这样的方式来优化：对于每一个格子，记录它之后（包括它本身）的第一个还可以被上色的格子。这样我们就可以像链表一样修改这些格子，只需要同时修改这些格子的后继就可以了。完全可以实现每个格子最多只会被修改一次。

你可能已经想到了一个方法：并查集。我们使用并查集来满足如上的要求。修改后继对应的就是并查集中的 union 函数；查找下一个可修改的格子对应的就是 find 函数。存在的问题被完美解决了。

以行为单位建立并查集，每一次绘制图形之后，都需要执行 union(x,x+2) 的操作（绘制是每两格执行一次的），查找后继直接使用 find(x) 即可。

值得提出的是，union(x,x+2) 当中，\text{x} 的取值有可能就是 n，程序中为了防止数组越界或造成死循环，将并查集的范围稍稍调大了一点。当然，你也可以尝试着写一下特判，判断当前的 union 操作是否合法。

代码

代码省略了头文件。个人的习惯是下标 +1。

typedef long long ll;
ll read(){
    char c=getchar();ll d=0,f=1;
    while(c<'0' || c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){d=(d<<3)+(d<<1)+(c^48);c=getchar();}
    return d*f;
}

const ll MAXM = 1e5+10;
const ll MAXN = 1e3+10;

ll n,k,m;
struct Oper{
    ll op;
    ll a1,a2,a3,a4,a5;
}a[MAXM];
ll slot[MAXM];// 存档
ll slots;// 存档数量
ll fa[MAXN][MAXN];// 并查集
ll p[MAXN][MAXN];// 颜色

ll find(ll id,ll x){// 此处的 id 和 unionn 函数的一样，都指明了数组的第一维编号
    if(fa[id][x]!=x){
        fa[id][x]=find(id,fa[id][x]);
    }
    return fa[id][x];
}
void unionn(ll id,ll x,ll y){
    x=find(id,x);
    y=find(id,y);
    fa[id][x]=y;
}

int main(){
    n=read();k=read();m=read();
    for(ll i=1;i<=n;++i){
        for(ll j=1;j<=n+2;++j){
            fa[i][j]=j;
            p[i][j]=1;
        }
    }
    for(ll i=1;i<=m;++i){
        string s;cin>>s;
        if(s=="PAINT"){
            a[i].op=1;
            a[i].a1=read();
            a[i].a2=read()+1;
            a[i].a3=read()+1;
            a[i].a4=read()+1;
            a[i].a5=read()+1;
        }if(s=="SAVE"){
            a[i].op=2;
            slot[++slots]=i;
        }if(s=="LOAD"){
            a[i].op=3;
            a[i].a1=read();
        }
    }
    for(ll i=m;i>=1;--i){
        if(a[i].op==3)i=slot[a[i].a1];// 退回对应的存档
        if(a[i].op==1){
            ll ybegin=a[i].a3;
            for(ll j=a[i].a2,ptr=0;j<=a[i].a4;++j,ptr=!ptr){
                for(ll k=find(j,ybegin);k<=a[i].a5;k=find(j,k)){// 跳至其后继
                    p[j][k]=a[i].a1;
                    unionn(j,k,k+2);// 调整后继
                }
                if(!ptr)ybegin=a[i].a3+1;// 模拟棋盘状
                else ybegin=a[i].a3;
            }
        }
    }
    for(ll i=1;i<=n;++i,putchar('\n')){
        for(ll j=1;j<=n;++j){
            printf("%lld ",p[i][j]);
        }
    }
    return 0;
}

祝您 AC 愉快。