题解：AT_abc442_d [ABC442D] Swap and Range Sum

XsIeEiKcEk · 2026-01-25 10:39:44 · 题解

题面不予赘述。

一眼前缀和。\ 先定义 pre_i 为 \sum_{i=1}^n a_i。

• 如果为交换 a_x 与 a_{x+1}，为了维护前缀和，我们肯定要改变 pre 的值。注意到交换后 \sum_{i=1}^{x+1}a_i 的值仍然不变，所以 pre_{x+1} 不用变。由于 a_x 换成了 a_{x+1}，所以 pre_x 先减去 a_x，再加上 a_{x+1} 就行了。记得还要交换 a_x 与 a_{x+1}，不要只维护。
• 如果为查询 \sum_{i=l}^r a_i，直接输出 pre_r-pre_{l-1} 就行了。