题解：CF1705E Mark and Professor Koro

wmrqwq · 2025-05-08 20:54:09 · 题解

一句话题解。

注意到题目中的序列可以直接转化成一个二进制数，具体的，对于一个数字 a_i 就给这个二进制数的第 a_i 位 +1，然后进行进位，原问题变成维护 +2^k 或 -2^k。

注意到最多只改变二进制数中的一位，对于每次操作连续段变化数量 \le 2，因此直接 ODT 维护即可。

时间复杂度 O(n + q + V \log V)，其中 V 为值域。