POJ3468

红太狼 2023-03-06 05:39 10阅读 0赞

# POJ3468 #

![博客图片][format_png]

## 题目链接 ##

[POJ3468][]

## 题目概述 ##

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

1.  `Q x y`( x ≤ y ) x \\leq y) x≤y)计算 ∑ i = x y a \[ i \] \\sum\_\{i = x\}^y a\[i\] ∑i=xya\[i\]
2.  `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][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).

## 其它 ##

[format_png]: /images/20230208/0b6998147bfe44aba88081dc6439fd95.png
[POJ3468]: http://poj.org/problem?id=3468
[OIwiki]: https://oi-wiki.org/basic/prefix-sum/#_8