POJ-3468 A Simple Problem with Integers

传送门：POJ - 3468

题目描述

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.

输入描述

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.

输出描述

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

思路分析

线段树维护区间和，区间更新

样例输入

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

样例输出

4
55
9
15

线段树代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=1e6+10;

struct node {
    int left,right;
    ll sum;
    int len() {
        return right-left+1;
    }
    int mid() {
        return (right+left)/2;
    }
} tree[N*4];

ll a[N],lazy[N];

void pp(int x) {
    tree[x].sum=tree[x*2].sum+tree[x*2+1].sum;
}

void pd(int x) {
    if(lazy[x]) {
        int mid=(tree[x].left+tree[x].right)/2;
        lazy[x*2]+=lazy[x];
        lazy[x*2+1]+=lazy[x];
        tree[x*2].sum+=tree[x*2].len()*lazy[x];
        tree[x*2+1].sum+=tree[x*2+1].len()*lazy[x];
        lazy[x]=0;
    }
}

void build(int x,int l,int r) {
    tree[x].left=l;
    tree[x].right=r;
    if(l==r) {
        tree[x].sum=a[l];
    } else {
        int mid=tree[x].mid();
        build(x*2,l,mid);
        build(x*2+1,mid+1,r);
        pp(x);
    }

}

void update(int x,int l,int r,ll v) {
    if(l<=tree[x].left && tree[x].right<=r) {
        tree[x].sum+=tree[x].len()*v;
        lazy[x]+=v;
    } else {
        pd(x);
        int mid=tree[x].mid();
        if(l<=mid)
            update(x*2,l,r,v);
        if(r>mid)
            update(x*2+1,l,r,v);
        pp(x);
    }
}

ll query(int x,int l,int r) {
    ll ans=0;
    if(l<=tree[x].left && tree[x].right<=r) {
        return tree[x].sum;
    }
    pd(x);
    int mid=tree[x].mid();
    if(l<=mid)
        ans+=query(x*2,l,r);
    if(r>mid)
        ans+=query(x*2+1,l,r);
    return ans;
}

int main() {
#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--) {
        char o;
        int x,y;
        ll z;
        cin>>o;
        scanf("%d%d",&x,&y);
        if(o=='C') {
            scanf("%lld",&z);
            update(1,x,y,z);
        } else {
            printf("%lld\n",query(1,x,y));
        }
    }



    return 0;
}

分块代码

#include <iostream>
#include <string>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <iomanip>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define fi first
#define se second
#define ll long long
#define pb push_back
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define umap unordered_map
#define uset unordered_set
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
const int N=100010;

int n,m,blo,num;
ll bel[N],l[N],r[N],sum[N],tag[N],a[N];

void build() {
    blo=sqrt(n);
    num=n/blo;
    if(n%blo)
        num++;
    for(int i=1; i<=num; i++) {
        l[i]=(i-1)*blo+1;
        r[i]=i*blo;
    }
    r[num]=n;
    for(int i=1; i<=n; i++)
        bel[i]=(i-1)/blo+1;
    for(int i=1; i<=num; i++)
        for(int j=l[i]; j<=r[i]; j++)
            sum[i]+=a[j];

}

void add(int x,int y,ll v) {
    if(bel[x]==bel[y]) {
        for(int i=x; i<=y; i++) {
            a[i]+=v;
            sum[bel[x]]+=v;
        }
        return ;
    }
    for(int i=bel[x]+1; i<bel[y]; i++)
        tag[i]+=v;
    for(int i=x; i<=r[bel[x]]; i++) {
        a[i]+=v;
        sum[bel[x]]+=v;
    }
    for(int i=l[bel[y]]; i<=y; i++) {
        a[i]+=v;
        sum[bel[y]]+=v;
    }
}

ll query(int x,int y) {
    ll ans=0;
    if(bel[x]==bel[y]) {
        for(int i=x; i<=y; i++) {
            ans+=a[i];
            ans+=tag[bel[x]];
        }
        return ans;
    }

    for(int i=bel[x]+1; i<bel[y]; i++)
        ans+=tag[i]*(r[i]-l[i]+1)+sum[i];
    for(int i=x; i<=r[bel[x]]; i++) {
        ans+=a[i];
        ans+=tag[bel[x]];
    }
    for(int i=l[bel[y]]; i<=y; i++) {
        ans+=a[i];
        ans+=tag[bel[y]];
    }
    return ans;

}

int main() {

#ifdef xiaofan
    freopen("in.txt","r",stdin);
#endif

    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%lld",&a[i]);
    build();
    while(m--) {
        char o;
        int x,y;
        ll z;
        cin>>o;
        if(o=='C') {
            scanf("%d%d%lld",&x,&y,&z);
            add(x,y,z);
        } else {
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x,y));
        }
    }





    return 0;
}