这是本文档旧的修订版!
题目 | 蒋贤蒙 | 王赵安 | 王智彪 |
---|---|---|---|
B | 0 | 0 | 0 |
E | 0 | 0 | 0 |
F | 0 | 0 | 0 |
G | 2 | 0 | 0 |
H | 0 | 0 | 0 |
K | 0 | 0 | 0 |
二分答案 $+$ 滑动窗口,赛后一分钟过样例 $\to$ 过题,乐。
给定 $n\times m$ 的矩阵,每个位置一个植物,种类为 $a(i,j)$。接下来 $q$ 个操作,每次选定一个矩形区域施加种类为 $k$ 的药水。
当植物的种类与被施加的药水种类不同时植物死亡。问最后死亡的植物数。
二维线段树维护区间赋值,最后查询时将所有操作下放到子节点暴力修改,时间复杂度 $O(nm\log n\log m)$。
二维树状数组维护矩形区间加,先将所有操作加入矩阵,最后枚举种类,枚举种类 $k$ 的植物时先消除 $k$ 类药水的影响查询完成后再加回去。
时间复杂度同为 $O(nm\log n\log m)$,但常数小。
随机给每个种类 $k$ 赋一个值 $f(k)$,然后哈希处理矩阵加,当种类 $k$ 的植物的所在位置的权值恰好为 $f(k)$ 的倍数时该植物存活。
如果不放心可以二重哈希,时间复杂度 $O(nm)$。