题解：AT_abc403_g [ABC403G] Odd Position Sum Query

Eterna · 2025-04-28 13:37:50 · 题解

赛时看到已经没有时间写了。

题意大概就是每次插入一个数，然后查询排名是奇数的数的和。

有两种做法。

第一种是我赛时的想法。我们直接维护有序的 a，及其奇数下标和偶数下标的数的和。块状链表，插入一个数直接单块重构一下，其他块不用管。然后查询的话，就是一边算前面的数的数量的奇偶性，就可以考虑当前块查奇数还是查偶数了。

但是 O(n \sqrt{n}) 不一定能过。可以换成平衡树，每次插入按值分裂，然后 pushup 一下，pushup 讨论左边的区间长度奇偶性即可。所以可以 O(n \log n)。提交记录。

第二种是官方题解的想法。对值域开线段树，然后直接就可以和平衡树做法一样合并区间。但是值域太大，直接开是不行的，于是动态开点卡空间。然后 O(n \log m) 跑得没有平衡树快。提交记录。