容易发现题目所给的限制等价于,相邻相同的情况只能出现至多一次并且必须是加号。这限制了减号不能相邻,并且若有相邻加号,可以得出两侧必须是减号。如果假设矩形中间有两个相邻的加号,就能推导出两条相邻方向相同的斜线全是加号。而这样的斜线一定会覆盖短边的一个前缀行或者后缀行,所以至多有两组这样的相邻的全加号斜线,并且方向必须相同且距离有下界限制。维护每条斜线的总体信息,最后就可以通过预处理一些前后缀信息做到快速统计答案。时间复杂度为 $\mathcal{O}(R + C + X)$。
QOJ.ac
QOJ
Discussion #752 for Problem #16294. Pluses and Minuses
Type: Editorial
Status: Open
Posted by: Milmon
Posted at: 2026-01-20 20:14:09
Last updated: 2026-01-20 20:14:52
题解
Comments
No comments yet.