POJ3468 A Simple Problem with Integers(zkw线段树lazy标记)

傷城~ 2021-09-16 03:36 209阅读 0赞

A Simple Problem with Integers  
Time Limit: 5000MS Memory Limit: 131072K  
Total Submissions: 140421 Accepted: 43534  
Case Time Limit: 2000MS  
Description

You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.  
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.  
Each of the next Q lines represents an operation.  
“C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.  
“Q a b” means querying the sum of Aa, Aa+1, … , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5  
1 2 3 4 5 6 7 8 9 10  
Q 4 4  
Q 1 10  
Q 2 4  
C 3 6 3  
Q 2 4  
Sample Output

4  
55  
9  
15  
Hint

The sums may exceed the range of 32-bit integers.

一道过了几万人的经典题，作为zkw的训练题很好。  
值得注意的是，这题其实不需要打lazy标记，直接维护维护前缀前缀和即可。  
事实上，因为满足区间减法，你也可以用树状数组写。并且还有二维进阶题目等着你。

#include <iostream>
    #include <cstring>
    #include <cstdlib>
    #include <string>
    #include <cstdio>
    #include <cmath>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <bitset>
    #include <assert.h>
    #include<algorithm>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){
       if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
    const int maxn = 270000;
    //head
    
    ll T[maxn],b[maxn];//b是lazy标记
    int n,q,M,h,p;
    void init()
    {
        scanf("%d%d",&n,&q);
        for(M = 1,h = 0;M < 2 + n;M <<= 1,h++);//h为树的高度，根的高度为0
            rep(i,M+1,M+n+1)
            scanf("%lld",&T[i]);
            per(i,1,M)
                T[i] = T[i<<1] + T[i<<1|1];//没有用差分版本
    }
    void down(int t)
    {
        per(i,1,h+1)//向下传递
            if(b[p=t>>i])
            {
                b[p] >>= 1;//子节点只增加一半
                T[p<<1] += b[p]; T[p<<1|1] += b[p];
                b[p<<1] += b[p]; b[p<<1|1] += b[p];
                b[p] = 0;
            }
    }
    
    void change(int l,int r,int k)
    {
        int ll,rr;
        l = l + M - 1;
        r = r + M + 1;
        ll = l>>1; rr = r>>1;
        down(l);down(r);
        for(;l^r^1;l >>= 1,r>>=1,k<<=1)
        {
            if(~l&1) T[l^1] += k,b[l^1] += k;
            if(r&1)  T[r^1] += k,b[r^1] += k;
        }
        for(int i = ll;i;i>>=1) T[i] = T[i<<1] + T[i<<1|1];//向上更新
        for(int i = rr;i;i>>=1) T[i] = T[i<<1] + T[i<<1|1]; 
    }
    
    void query(int l ,int r)
    {
        ll ans = 0;
        l = l + M - 1;
        r = r + M + 1;
        down(l);down(r);
        for(;l^r^1;l>>=1,r>>=1)
        {
            if(~l&1) ans += T[l^1];
            if(r&1)  ans += T[r^1];
        }
        printf("%lld\n",ans);
    }
    char c;
    int l,r,k;
    void work()
    {
        while(q--)
        {
            getchar();
            scanf("%c%d%d",&c,&l,&r);
            if(c == 'Q')
                query(l,r);
            else
                scanf("%d",&k),change(l,r,k);
        }
    }
    int main()
    {
        init();
        work();
        return 0;
    }