社区讨论

关于WC T1

BBinah
灌水区参与者 4已保存回复 7

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@lo3bbh7q
此快照首次捕获于
2023/10/24 03:50
2 年前
此快照最后确认于
2023/10/24 03:50
2 年前
查看原帖
我考场上想了这么个做法：
  1. +相当于维护边界在某两个指定的竖边(V)直接增加b个横边(H)
  2. -移除某竖边后之多b个横边后在其前面加入若干个横边，如果是第一个之前则跳过（相当于拆成全部移除和+两部）
  3. R相当于直接做前若干个+的逆操作，在某两个V之间之间减去b个

我使用了动态开点线段树去维护每个V右侧的H

每次询问k的时候考虑第1,1+k,...,1+xk1,1+k,...,1+xk个边，易知边界总长等于1+xk1+xk，于是第一条一定是V，最后一条一定是H，所以一定有相邻两条前面是V后面是H，二分查找，总复杂度O(nlog(n)log(na))O(nlog(n)log(na)),特判掉后面连续H段最长的V之后能优化到O(nlog(n)log(a))O(nlog(n)log(a))

但是我在计算当前总边界长的时候使用了当前线段树里和根联通的最靠右的节点并且在R操作的时候忘了在把节点减至0的时候断掉网上的边

而且我进行了#define int long long导致常数回到了优化之前
所以我大概会爆到多少分

回复

共 7 条回复，欢迎继续交流。

正在加载回复...