区间数颜色
2026-04-22 21:51:40
发布于:广东
为方便表示时间复杂度,假设 同阶。
不带修:P1972
Difficulty:4.1 / Easy
定义 为 相同颜色的后继,即最小的 满足 。显然可以 求出。
定义 为 相同颜色的前继,即最大的 满足 。显然可以 求出。
考虑 固定后, 往右移动 格后会怎么样。显然:
- 如果 出现过了,答案不变。
- 如果 未出现过,答案 。
定义 为区间左端点为 ,由 移动到 的贡献。
注意到 与 的差距只在于 从 变成 与 从 变成 了。
我们可以主席树实现或者扫描线动态维护 。
。
单点修:P1903
Difficulty:4.7 / Easy
考虑修改会产生什么影响。
显然,就是修改了 个位置的 。
而每次修改 会给后面的查询中,区间与 有左交集并且与 有右交集的答案产生 的影响。
哦,这下看懂了。
CDQ 分治即可。
,代码有时间再写。
区间修:P4690
Difficulty:4.8 / Easy
注意到修改 后, 的 会变成 ,其余的只有 和 的 会改变。
假设已经修改了 并且没被动过,现在要修改 。我们可以发现 与 的交集的 不会改变。
所以有一个结论,修改 次后 的总修改次数不超过 。
所以可以和上面一样,CDQ 分治即可。
,代码有时间再写。
全部评论 3
膜拜数颜色大佬
2026-04-19 来自 广东
0评高了(严肃)
2026-04-19 来自 广东
0你想让我评黄吗。严肃
2026-04-19 来自 广东
0不对,4+是黄,那1+是什么
2026-04-19 来自 广东
0
dddqpzc
2026-04-19 来自 广东
0


















有帮助,赞一个