树状数组为何能通过？

P2367 语文成绩

Cosine_Func @ 2024-05-03 15:57:44

树状数组复杂度应为O(n\log n)，理论上来说无法通过5e6的数据，为何AC？是否数据太水？ 提交记录

by ___Furina___ @ 2024-05-03 16:06:10

@XiaoJingCheng

  1. 跑不满 5e6，并且常数较小；
  2. 大部分包括 luogu 评测机往往有 1e8 的评测速度。

by _xm_ @ 2024-05-03 17:04:38

树状数组常数小，这有啥， std::sort 能跑 1e7

|