题解：AT_abc442_d [ABC442D] Swap and Range Sum

Star_F · 2026-01-25 07:31:35 · 题解

有史以来最简单的 D 吧。

题目思路：

题意很清楚，首先支持单点修改，区间查询的数据结构都能做，比如树状数组，线段树。时间复杂度 \mathcal{O}(Q\log n)。

由于本题的修改比较特殊，只是交换两个相邻的数字，我们考虑前缀和。设前 i 个数的和为 s_i，发现交换第 x 和第 x+1 个数对 s 的影响只有 s_x-a_x+a_{x+1} \to s_x。对于其他的 s_i 没有任何影响。于是单点修改前缀和数组即可，时间复杂度 \mathcal{O}(Q)。

代码：

namespace Star_F{
    const int N = 200005;
    int n, q, s[N], a[N];
    void Main(){
        cin >> n >> q;
        for (int i = 1; i <= n;i++)
            cin >> a[i], s[i] = s[i - 1] + a[i];
        while(q--){
            int opt, x, l, r;
            cin >> opt;
            if(opt==1){
                cin >> x;
                s[x] = s[x] - a[x] + a[x + 1];
                swap(a[x], a[x+1]);
            }else{
                cin >> l >> r;
                cout << s[r] - s[l - 1] << endl;
            }
        }
    }
}