Submission #70973089

---

Source Code Expand

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 5e5+5;

int ft1[N], ftv[N];

int lsb(int x) {
    return x&(-x);
}

void add(int p, int v, int* ft) {
    ++p;
    while (p < N) {
        ft[p] += v;
        p += lsb(p);
    }
}

int rsq(int p, int* ft) {
    ++p;
    int v = 0;
    while (p) {
        v += ft[p];
        p -= lsb(p);
    }
    return v;
}

int rsq(int l, int r, int* ft) {
    return rsq(r, ft)-rsq(l-1, ft);
}

int a[N];

signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ///
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        add(a[i], 1, ft1);
        add(a[i], a[i], ftv);
    }
    while (q--) {
        int cc, aa, bb;
        cin >> cc >> aa >> bb;
        if (cc == 1) {
            add(a[aa], -1, ft1);
            add(a[aa], -a[aa], ftv);
            a[aa] = bb;
            add(a[aa], 1, ft1);
            add(a[aa], a[aa], ftv);
        }
        if (cc == 2) {
            int l = aa;
            int r = bb;
            if (l >= r) {
                cout << n*l << '\n';
                continue;
            }
            int s1 = rsq(l-1, ft1)*l;
            int s2 = (n-rsq(r, ft1))*r;
            int s3 = rsq(l, r, ftv);
            cout << s1+s2+s3 << '\n';
        }
    }
}

Submission Info

Judge Result