QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: Milmon

Posted at: 2026-01-20 20:14:09

Last updated: 2026-01-20 20:14:52

Back to Problem

题解

容易发现题目所给的限制等价于,相邻相同的情况只能出现至多一次并且必须是加号。这限制了减号不能相邻,并且若有相邻加号,可以得出两侧必须是减号。如果假设矩形中间有两个相邻的加号,就能推导出两条相邻方向相同的斜线全是加号。而这样的斜线一定会覆盖短边的一个前缀行或者后缀行,所以至多有两组这样的相邻的全加号斜线,并且方向必须相同且距离有下界限制。维护每条斜线的总体信息,最后就可以通过预处理一些前后缀信息做到快速统计答案。时间复杂度为 $\mathcal{O}(R + C + X)$。

Comments

No comments yet.