Submission #72699023

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define endl '\n'
const int N=500100,INF=2e18,MOD=998244353;
int t,n,k,x,y,z,m,h,j,u,cnt,mi,tt,rr,mx,res,ans,ll,q,kk;
int a[N],b[N],c[N];
template <class T>
struct BIT {
    int n;
    vector<T> w;

    BIT(int n = 0) { init(n); }

    // 用原数组 in[1..n] 建树（O(n log n)）
    BIT(int n, const vector<T> &in) {
        init(n);
        for (int i = 1; i <= n; i++) {
            add(i, in[i]);
        }
    }

    void init(int n_) {
        n = n_;
        w.assign(n + 1, 0);
    }

    // 单点加
    void add(int x, T v) {
        for (; x <= n; x += x & -x) {
            w[x] += v;
        }
    }

    // 前缀和 [1..x]
    T ask(int x) const {
        T ans = 0;
        for (; x > 0; x -= x & -x) {
            ans += w[x];
        }
        return ans;
    }

    // 区间和 [l..r]
    T ask(int l, int r) const {
        return ask(r) - ask(l - 1);
    }
};
signed main(){
    cin>>n>>q;
    vector<int>f(n+5);
    for(int i=1;i<=n;i++){
        cin>>f[i];
    }
    BIT<long long> bit(n,f);
    while(q--){
        cin>>x;
        if(x==1){
            cin>>y;
            z=y+1;
            tt=bit.ask(y,y);
            rr=bit.ask(z,z);
            bit.add(y,-tt);
            bit.add(y,rr);
            bit.add(z,-rr);
            bit.add(z,tt);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<bit.ask(l,r)<<endl;


        }

    }

}

Submission Info

Judge Result