题解：AT_abc442_d [ABC442D] Swap and Range Sum

he_lucky · 2026-01-25 08:45:38 · 题解

题目大意：

给出 N 个数 A=(A_1,A_2,\ldots,A_N)。
有 Q 次操作，每次操作有两种：

• 1 x：交换 A_x 和 A_{x+1} 的值；
• 2 l r：计算下标 l 到 r 和的值。

其实简单模拟即可，但需要考虑数据范围（较大），所以用树状数组优化。
怎样交换 A_x 和 A_{x+1} 的值，将 x 的位置加上 A_{x+1} 的值，减去 A_x 的值，也就是减去自己，加上别人，x+1 的位置同理。

代码：

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n,q,a[N];
int b[N];
template<class T>
struct B{
    LL si;
    T c[N];
    void resize(LL s){
        si = s;
    }
    T query(LL x){
        T s = 0;
        while (x){
            s += c[x];
            x -= x & (-x);
        }
        return s;
    }
    void mo(LL x,T a){
        while (x <= si){
            c[x] += a;
            x += x & (-x);
        }
    }
};
B<LL> c;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> q;
    c.resize(n+1);
    for (int i = 1;i <= n;i++){
        cin >> a[i];
        c.mo(i,a[i]);
    }
    while (q--){
        int k,x,y;
        cin >> k;
        if (k == 1){
            cin >> x;
            c.mo(x,a[x+1]-a[x]);
            c.mo(x+1,a[x]-a[x+1]);
            swap(a[x],a[x+1]);
        }else{
            cin >> x >> y;
            cout << c.query(y) - c.query(x-1) <<endl;
        }
    }
    return 0;
}