A Simple Problem with Integers

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 2011 字
n个数，q次操作：1lrx区间[l,r]整体
一本通
例
正文

/*
原题：一本通 4.3 例 2 A Simple Problem with Integers (POJ 3468)
题意：n 个数，q 次操作：1 l r x 区间 [l,r] 整体加 x；2 l r 求区间 [l,r] 的和。
思路：带懒标记的线段树，维护区间和与区间加标记；下推时把标记按区间长度传给左右儿子。
复杂度：时间 O((n+q) log n)，空间 O(n)。
易错点：区间和与懒标记用 long long；add 为 0 表示无标记；下推后才能递归子区间。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000005;
ll a[N];
ll sum[N*4];
ll add[N*4];
void pushdown(int node,int l,int r){
    if(add[node]!=0){
        int mid=(l+r)/2;
        int ls=node*2,rs=node*2+1;
        sum[ls]+=add[node]*(mid-l+1);
        sum[rs]+=add[node]*(r-mid);
        add[ls]+=add[node];
        add[rs]+=add[node];
        add[node]=0;
    }
}
void build(int node,int l,int r){
    add[node]=0;
    if(l==r){
        sum[node]=a[l];
        return;
    }
    int mid=(l+r)/2;
    build(node*2,l,mid);
    build(node*2+1,mid+1,r);
    sum[node]=sum[node*2]+sum[node*2+1];
}
void update(int node,int l,int r,int ql,int qr,ll v){
    if(ql<=l&&r<=qr){
        sum[node]+=v*(r-l+1);
        add[node]+=v;
        return;
    }
    pushdown(node,l,r);
    int mid=(l+r)/2;
    if(ql<=mid){
        update(node*2,l,mid,ql,qr,v);
    }
    if(qr>mid){
        update(node*2+1,mid+1,r,ql,qr,v);
    }
    sum[node]=sum[node*2]+sum[node*2+1];
}
ll query(int node,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr){
        return sum[node];
    }
    pushdown(node,l,r);
    int mid=(l+r)/2;
    ll res=0;
    if(ql<=mid){
        res+=query(node*2,l,mid,ql,qr);
    }
    if(qr>mid){
        res+=query(node*2+1,mid+1,r,ql,qr);
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    for(int i=0;i<q;i++){
        int op;
        cin>>op;
        if(op==1){
            int l,r;
            ll x;
            cin>>l>>r>>x;
            update(1,1,n,l,r,x);
        }else{
            int l,r;
            cin>>l>>r;
            cout<<query(1,1,n,l,r)<<"\n";
        }
    }
    return 0;
}
A Simple Problem with Integers

正文

一本通·提高篇的其它内容
