Submission #72696285

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Fenwick {
    int n;
    vector<long long> bit;
    Fenwick(int n) : n(n), bit(n + 1, 0) {}
    void add(int idx, long long val) {
        for (; idx <= n; idx += idx & -idx)
            bit[idx] += val;
    }
    long long sum(int idx) {
        long long s = 0;
        for (; idx > 0; idx -= idx & -idx)
            s += bit[idx];
        return s;
    }
    long long rangeSum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, Q;
    cin >> N >> Q;
    vector<long long> A(N + 1);
    Fenwick fw(N);
    for (int i = 1; i <= N; i++) {
        cin >> A[i];
        fw.add(i, A[i]);
    }
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            long long a = A[x];
            long long b = A[x + 1];
            swap(A[x], A[x + 1]);
            fw.add(x, b - a);
            fw.add(x + 1, a - b);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << fw.rangeSum(l, r) << "\n";
        }
    }

    return 0;
}

Submission Info

Judge Result