POJ3468

博客图片

题目链接

POJ3468

题目概述

给出一个包含有 N N N个元素的数组 a a a,然后是 m m m次操作,操作有以下两种类型:

Q x y( x ≤ y ) x \leq y) x≤y)计算 ∑ i = x y a [ i ] \sum_{i = x}^y a[i] ∑i=xya[i]
C x y d ( x ≤ y ) (x \leq y) (x≤y)将区间 [ x , y ] [x,y] [x,y]内部的每一个 a [ i ] a[i] a[i]加上 d d d.

对于第一种查询操作输出对应的结果,数据规模:
1 ≤ N , M ≤ 1 0 5 , − 1 0 9 ≤ A i ≤ 1 0 9 , − 1 0 4 ≤ d ≤ 1 0 4 . 1\leq N,M\leq 10^5, -10^9 \leq A_i \leq 10^9, -10^4\leq d\leq 10^4. 1≤N,M≤105,−109≤Ai≤109,−104≤d≤104.

题目分析

经典的树状数组区间修改和区间查询的题目,利用初始的前缀和数组和用两个树状数组维持区间修改后的 ∑ i = 1 n a [ i ] \sum_{i=1}^na[i] ∑i=1na[i].

利用差分转换的原理可以看看这个差分–OIwiki

通过:
∑ i = 1 r + 1 ( r + 1 − i + 1 ) ⋅ f i − ∑ i = 1 l ( l − i + 1 ) ⋅ f i \sum_{i=1}^{r+1}(r+1-i+1)\cdot f_i - \sum_{i=1}^{l}(l-i+1)\cdot f_i i=1∑r+1(r+1−i+1)⋅fi−i=1∑l(l−i+1)⋅fi

代码

/*
 * @Author: Shuo Yang
 * @Date: 2020-08-04 15:46:50
 * @LastEditors: Shuo Yang
 * @LastEditTime: 2020-08-04 16:58:19
 * @FilePath: /Code/POJ/3468.cpp
 */
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
ll t1[N];
ll t2[N];
ll a[N];
int n;
inline int lowbit(int x){
    return x & -x;
}
void add(ll*  t, int k, int x){
    while( k <= n){
        t[k] += x;
        k += lowbit(k);
    }
}
ll sum(ll* t, int k){
    ll ans = 0;
    while( k > 0){
        ans += t[k];
        k -= lowbit(k);
    }
    return ans;
}
void addL(int lef, int rig, int x){
    add(t1, lef, x);
    add(t2, lef, lef*x);
    add(t1, rig+1, -x);
    add(t2, rig+1, -(rig+1)*x);
}
int main(int argc, const char** argv) {
    int m;
    scanf("%d %d",&n,&m);
    for(int i = 1; i <=n ; ++i){
        scanf("%lld", &a[i]);
            a[i] += a[i-1];
    }
    for(int i = 0; i <m; ++i){
        char ch;
        int x,y,c;
        while( ch != 'Q' && ch !='C')
            scanf("%c",&ch);
        // printf("ch=%c**\n", ch);
        if(ch == 'Q'){
            scanf("%d %d", &x,&y);
            ll ans = (a[y]+(sum(t1,y)*(y+1) - sum(t2,y))) - (a[x-1]+(sum(t1,x)*x-sum(t2,x)));
            printf("%lld\n", ans);
        }else if( ch == 'C'){
            scanf("%d %d %d",&x,&y,&c);
            addL(x,y,c);
        }
    }
    return 0;
}

这里面的树状数组t1是维护 ∑ i = 1 n ( n + 1 ) ⋅ a [ i ] \sum_{i=1}^{n}(n+1)\cdot a[i] ∑i=1n(n+1)⋅a[i],t2数组是维护 ∑ i = 1 n i ⋅ a [ i ] \sum_{i=1}^{n}i\cdot a[i] ∑i=1ni⋅a[i].
区间更新操作是对这两个操作进行的,至于区间求和在原来前缀和的基础上加上这个区间修改后的差分求和得到的就是最终的结果.
(纯粹的板子,但是我说不清楚,┭┮﹏┭┮2333333).