bzoj 4776: [Usaco2017 Open]Modern Art 乱搞

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4776


一道挺有趣的题目

对于有可能作为第一个放的数字,它最后一定不会出现在被1个以上矩形覆盖的位置

所以我们记录一下每个出现的数字的矩形边界,然后把这个矩形的sum[up~down][left~right]全部+1,最后如果sum[i][j]>1,那么在i行j列位置的数字一定不可能是第一个数字。

区间覆盖可以二维树状数组/线段树………但是我们是一次性的更改,所以像前缀和那样,加两次,减两次,然后求一边前缀和就可以了。

如果n>1并且只出现了一个数字,那个数字是不可以做为第一个数字出现的

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注