POJ3468 A Simple Problem with Integers(zkw线段树lazy标记)-蒲公英云

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

傷城~ 2021-09-16 03:36 348阅读 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;
}