ACM-ICPC 2018 徐州赛区网络预赛 H Ryuji doesn't want to study(线段树 两种做法)

Ryuji doesn’t want to study

问题分析

我们可以做一个前缀和sum{a[i]}$sum\{a[i]\}$和一个前缀和sum{(n−i)∗a[i]}$sum\{(n-i)\ast a[i]\}$(看起来就像一个三角形，我们这里称之为tangle[i]$tangle[i]$)，如图所示。

假设我们要求区间[2,5]=2⋅4+3⋅3+4⋅2+5⋅1$[2,5]=2\cdot 4+3\cdot 3+4\cdot 2+5\cdot 1$，那么，我们通过图中可以发现答案就是梯形的数值减去平行四边形的数值。即

query(2,5)=(tangle[5]−tangle[1])−(7−5)⋅(sum[5]−sum[1])$$query(2,5)=(tangle[5]-tangle[1])-(7-5)\cdot (sum[5]-sum[1])$$

因此我们只需要用线段树维护两个前缀和即可。

---

这里蒻再补充一个做法。就是线段树维护前缀和的区间和。
我们将题里的要求分解一下。
假设仍然要求query(2,5)$query(2,5)$，
分解开来就会发现

query(2,5)=(2+3+4+5)+(2+3+4)+(2+3)+(2)=(sum[5]−sum[1])+(sum[4]−sum[1])+(sum[3]−sum[1])+(sum[2]−sum[1])=∑i=25sum(i)−(5−3+1)⋅sum(1)(1)(2)(3)$$\begin{array}{}\text{(1)}& query(2,5)& =(2+3+4+5)+(2+3+4)+(2+3)+(2)\text{(2)}& & =(sum[5]-sum[1])+(sum[4]-sum[1])+(sum[3]-sum[1])+(sum[2]-sum[1])\text{(3)}& & =\sum _{i=2}^{5}sum(i)-(5-3+1)\cdot sum(1)\end{array}$$

所以题目所求变为

query(l,r)=∑i=lrsum(i)−(r−l+1)⋅sum(l−1)$$query(l,r)=\sum _{i=l}^{r}sum(i)-(r-l+1)\cdot sum(l-1)$$

代码(第一种做法)

#include <cstdio>
using namespace std;
typedef long long LL;
const int N = 1e6+4;
int n,q,a[N];
struct data {
    int l, r;
    LL val, tangle;
} tr[N<<1];

inline void pushup(int rt) {
    tr[rt].val = tr[rt << 1].val + tr[rt << 1 | 1].val;
    tr[rt].tangle = tr[rt << 1].tangle + tr[rt << 1 | 1].tangle;
}

void build(int k,int s,int t) {//建树
    tr[k].l = s;
    tr[k].r = t;
    if (s == t) {
        tr[k].val = a[s];
        tr[k].tangle = a[s] * 1LL * (n - s + 1);
        return;
    }
    int mid = (s + t) >> 1;
    build(k << 1, s, mid);
    build(k << 1 | 1, mid + 1, t);
    pushup(k);
}

LL query(int k,int x,int y,int len) {//区间求和
    int L = tr[k].l, R = tr[k].r;
    if (x == L && y == R)
        return tr[k].tangle - 1LL * len * tr[k].val;
    int mid = (L + R) >> 1;
    if (y <= mid)
        return query(k << 1, x, y, len);
    else if (x > mid)
        return query(k << 1 | 1, x, y, len);
    else
        return query(k << 1, x, mid, len) + query(k << 1 | 1, mid + 1, y, len);
}

void update(int rt,int L,int R,int x,LL v) {
    if (L == R) {
        tr[rt].tangle = (n - x + 1) * 1LL * v;
        tr[rt].val = v;
        return;
    }
    int mid = (L + R) >> 1;
    if (x <= mid)
        update(rt << 1, L, mid, x, v);
    else
        update(rt << 1 | 1, mid + 1, R, x, v);
    pushup(rt);
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    int op, x, y;
    for (int i = 1; i <= q; i++) {
        scanf("%d%d%d", &op, &x, &y);
        if (op == 2)
            update(1, 1, n, x, y);
        else
            printf("%lld\n", query(1, x, y, n - y));
    }
    return 0;
}

代码(第二种做法)

#include <cstdio>
#define L tree[rt].l
#define R tree[rt].r
typedef long long LL;
using namespace std;
const int N = 1e6+4;
int a[N],n,q;
LL sum[N];
struct data {
        int l,r;
        LL Inc,nSum;
} tree[N];

void pushup(int rt)
{
        tree[rt].nSum = tree[rt<<1].nSum+tree[rt<<1|1].nSum;
}

void pushdown(int rt) {
        if(tree[rt].Inc) {
                int mid = (L+R)>>1;
                tree[rt<<1].Inc += tree[rt].Inc;
                tree[rt<<1|1].Inc += tree[rt].Inc;
                tree[rt<<1].nSum += tree[rt].Inc*(mid-L+1);
                tree[rt<<1|1].nSum += tree[rt].Inc*(R-mid);
                tree[rt].Inc = 0;
        }
}

void build(int rt,int x,int y) {//建树
        tree[rt].l = x; tree[rt].r = y;
        if(x == y) {
                tree[rt].Inc = 0;
                tree[rt].nSum = sum[x];
                return;
        }
        int mid = (x + y) >> 1;
        build(rt<<1,x,mid);
        build(rt<<1|1,mid+1,y);
        pushup(rt);
}

LL query(int rt,int x,int y){//区间求和
        if(x == L && y == R)
                return tree[rt].nSum;
        pushdown(rt);
        int mid=(L+R)>>1;
        if(y<=mid)
                return query(rt<<1,x,y);
        else if(x>mid)
                return query(rt<<1|1,x,y);
        else
                return query(rt<<1,x,mid)+query(rt<<1|1,mid+1,y);
}

void update(int rt,int x,int y,LL v)
{
        if(x == L && R == y) {
                tree[rt].nSum += v*1LL*(R-L+1);
                tree[rt].Inc += v;
                return;
        }
        pushdown(rt);
        int mid = (L+R)>>1;
        if(y <= mid)
                update(rt << 1, x, y,v);
        else if(x > mid)
                update(rt << 1 | 1, x, y,v);
        else{
                update(rt << 1, x, mid,v);
                update(rt << 1 | 1, mid+1, y,v);
        }
        pushup(rt);
}


int main(){
        scanf("%d%d",&n,&q);
        for(int i=1; i<=n; i++) {
                scanf("%d",&a[i]);
                sum[i] = sum[i-1] + a[i];
        }
        build(1,1,n);
        int op,x,y;
        for(int i=1; i<=q; i++) {
                scanf("%d%d%d",&op,&x,&y);
                if(op==2) {
                        update(1,x,n,1LL*(y-a[x]));
                        a[x] = y;
                }
                else{
                        if(x==1) {
                                printf("%lld\n", query(1,x,y));
                        }else
                                printf("%lld\n", query(1,x,y)-1LL*(y-x+1)*query(1,x-1,x-1));
                }
        }
        return 0;
}