ICPC-2018 徐州网络赛H题 （树状数组/线段树/数学）

题目链接

观察可以发现
$$ \sum_{i=l}^{r} {a_i \times (r-i+1)} $$
$$ = \sum_{i=l}^{r} {a_i \times (r+1)} -
\sum_{i=l}^{r} {a_i \times i}$$
$$ = (r+1)\times\sum_{i=l}^{r} {a_i } -
\sum_{i=l}^{r} {a_i \times i} $$

这样就能用两个树状数组或线段树来维护了

树状数组写法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 1e5 + 10;

int n, q;
ll a[N], c1[N], c2[N];

ll lowbit(ll x) {
    return x & (-x);
}
void add1(ll x, ll val) {
    for(int i = x; i <= n; i += lowbit(i)) {
        c1[i] += val;
    }
}
void add2(ll x, ll val) {
    for(int i = x; i <= n; i += lowbit(i)) {
        c2[i] += val;
    }
}
ll query1(int x) {
    ll res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += c1[i];
    }
    return res;
}
ll query2(int x) {
    ll res = 0;
    for(int i = x; i; i -= lowbit(i)) {
        res += c2[i];
    }
    return res;
}

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
        add1(i, a[i]);
        add2(i, a[i]*i);
    }
    ll op, l, r;
    for(int i = 1; i <= q; i++) {
        scanf("%lld%lld%lld", &op, &l, &r);
        if(op == 1) {
            printf("%lld\n", (r + 1)*(query1(r) - query1(l-1)) - (query2(r) - query2(l-1)) );
        } else {
            add1(l, r - a[l]);
            add2(l, l*r - l*a[l]);
            a[l] = r;
        }
    }

    return 0;
}

线段树写法

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int N = 2e5 + 10;
int n, q;
ll sum1[N*4], a[N], sum2[N*4];

void change1(int k1) {
    sum1[k1] = sum1[k1*2] + sum1[k1*2+1];
}
void change2(int k1) {
    sum2[k1] = sum2[k1*2] + sum2[k1*2+1];
}

void buildtree1(int k, int l, int r) {
    if(l == r) {
        sum1[k] = a[l];
        return;
    }
    int mid = l+r >> 1;
    buildtree1(k*2, l, mid);
    buildtree1(k*2+1, mid+1, r);
    change1(k);
}
void buildtree2(int k, int l, int r) {
    if(l == r) {
        sum2[k] = a[l]*l;
        return;
    }
    int mid = l+r >> 1;
    buildtree2(k*2, l, mid);
    buildtree2(k*2+1, mid+1, r);
    change2(k);
}

void update1(int k1, int l, int r, int p, int q) {
    if(l == r) {
        sum1[k1] = q;
        return;
    }
    int mid = l+r >> 1;
    if(p <= mid) {
        update1(k1*2, l, mid, p, q);
    } else update1(k1*2+1, mid+1, r, p, q);
    change1(k1);
}

void update2(int k1, int l, int r, int p, int q) {
    if(l == r) {
        sum2[k1] = 1LL * p * q; //注意 
        return;
    }
    int mid = l+r >> 1;
    if(p <= mid) {
        update2(k1*2, l, mid, p, q);
    } else {
        update2(k1*2+1, mid+1, r, p, q);
    }
    change2(k1);
}

ll Find1(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum1[k1];
    int mid = l+r >> 1;
    return Find1(k1*2, l, mid, L, R) + Find1(k1*2+1, mid+1, r, L, R);
}

ll Find2(int k1, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(L <= l && r <= R) return sum2[k1];
    int mid = l+r >> 1;
    return Find2(k1*2, l, mid, L, R) + Find2(k1*2+1, mid+1, r, L, R);
}

int main() {
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        scanf("%lld", &a[i]);
    }
    buildtree1(1, 1, n);
    buildtree2(1, 1, n);
    for(int i = 1; i <= q; i++) {
        ll op, l, r;
        scanf("%lld%lld%lld", &op, &l, &r);
        if(op == 1) {
            ll tmp = (1ll*r+1)*Find1(1, 1, n, l, r) - Find2(1, 1, n, l, r);
            printf("%lld\n", tmp);
        } else if(op == 2) {
            update1(1, 1, n, l, r);
            update2(1, 1, n, l, r);
        }
    }

    return 0;
}