关于今天 ABC 的 G
  • 板块学术版
  • 楼主zcz0263
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/8/3 23:22
  • 上次更新2024/8/4 09:37:36
查看原帖
关于今天 ABC 的 G
760433
zcz0263楼主2024/8/3 23:22

我看到有人的做法是对于每个询问去重后直接跑双指针,这种做法能否可以通过构造第一个人在前 m2\frac m2 个时间单位每个时间单位进出一次,后面 m2\frac m2 个人只在最后 m2\frac m2 个时间内进一次,然后对于所有 2≤i≤m22\leq i\leq\frac m2,询问 (1,i)(1,i) 来卡到 O(m24)O(\frac{m^2}4) ?

如果每次询问处理时通过二分在第一个序列中找到第一个可以与第二个序列造成贡献的位置为指针的起始位置,后面和原做法一样跑双指针,这时优化后的做法是什么复杂度,可以被卡掉吗?

2024/8/3 23:22
加载中...