AT_abc442_d 题解

fftt52536 · 2026-01-24 21:05:47 · 题解

维护前缀和数组 S，使得 S_i=\sum_{j=1}^i A_j（特殊地，为防止越界，令 S_0=0）。

对于一次查询操作，区间和就是 S_r - S_{l-1}。

对于一次交换操作，我们发现，每一次交换只影响相邻元素的位置关系，而大小（对后续元素的贡献）并没有改变。

也就是说，交换 A_x 和 A_{x+1} 只会影响 S_x 和 S_{x+1}，对其余前缀和不产生影响。所以我们直接重新计算 S_x 和 S_{x+1} 即可。

:::success[AC Code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N, M;
int a[322222], sm[322222];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>N>>M;
    for(int i = 1; i <= N; i++){
        cin>>a[i];
    } 

    for(int i = 1; i <= N; i++){
        sm[i] = sm[i - 1] + a[i];
    }

    for(int i = 1; i <= M; i++){
        int x;
        cin>>x;
        if(x == 1){
            int j;
            cin>>j;
            //交换j和j+1
            int tmp = a[j];
            a[j] = a[j+1];
            a[j+1] = tmp;

            sm[j] = sm[j - 1] + a[j];
            sm[j + 1] = sm[j] + a[j+1]; 
        }else{
            int l, r;
            cin>>l>>r;

            int smm = sm[r] - sm[l - 1];

            cout<<smm<<endl;
        }
    }
}

:::