自动搬运

查看原文

来自洛谷，原作者为

	seac_blue Cogito ergo sum.

搬运于2025-08-24 22:31:46，当前版本为作者最后更新于2021-11-18 21:23:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目：[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 愉快。