相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4548
神犇题解:http://www.cnblogs.com/lcf-2000/p/6204367.html
解题报告
自己做的时候怎么都只会$O(n^2)$的算法啊……
看来还是我太年轻了 QwQ
我们来枚举是哪一种颜色不在所选集合中
枚举之后问题变成选择一个不含特定颜色的矩形,使其内部的点最多
下面我们来分情况讨论这个问题:
1. 我们所选矩形没有上下边界的限制
这个我们扫一遍,顺便记录一下就可以了
2. 我们所选的矩形有上/下边界的限制
这个东西我们可以用一个水平的扫描线从上往下扫描一遍
途中需要差前驱,后继这个用平衡树就可以了(似乎这一块可以用并查集优化掉$\log$?)
然后这题就做完啦!