首页 > 代码库 > poj 3468(简单线段树区间更新)

poj 3468(简单线段树区间更新)

2024-07-18 04:29:25   225人阅读

A Simple Problem with Integers
Time Limit: 5000MS Memory Limit: 131072K
Total Submissions: 61936 Accepted: 18934
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.

Source

POJ Monthly--2007.11.25, Yang Yi

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n,q;
#define ll long long
struct Node{
    int left,right;
    ll sum,p;        //p表示left 到 right 的增量
}a[400010];
void built(int cur,int x,int y){
    a[cur].left=x;
    a[cur].right=y;
    a[cur].p=0;
    if(x==y){
        scanf("%I64d",&a[cur].sum);
        return ;
    }
    int mid=(x+y)>>1;
    built(cur<<1,x,mid);
    built(cur<<1|1,mid+1,y);
    a[cur].sum=a[cur<<1].sum+a[cur<<1|1].sum;
}
void update(int cur,int x,int y,ll val){
    if(a[cur].left==x && a[cur].right==y){
        a[cur].sum+=val*(y-x+1);
        a[cur].p+=val;
        return ;
    }
    if(a[cur].p){
        a[cur<<1].p+=a[cur].p;
        a[cur<<1|1].p+=a[cur].p;
        a[cur<<1].sum+=a[cur].p*(a[cur<<1].right-a[cur<<1].left+1);
        a[cur<<1|1].sum+=a[cur].p*(a[cur<<1|1].right-a[cur<<1|1].left+1);
        a[cur].p=0;
    }
    int mid=(a[cur].left+a[cur].right)>>1;
    if(y<=mid)
        update(cur<<1,x,y,val);
    else if(x>mid)
        update(cur<<1|1,x,y,val);
    else{
        update(cur<<1,x,mid,val);
        update(cur<<1|1,mid+1,y,val);
    }
    a[cur].sum=a[cur<<1].sum+a[cur<<1|1].sum;
}

ll query(int cur,int x,int y){
    if(a[cur].left==x && a[cur].right==y){
        return a[cur].sum;
    }
    if(a[cur].p){
        a[cur<<1].p+=a[cur].p;
        a[cur<<1|1].p+=a[cur].p;
        a[cur<<1].sum+=a[cur].p*(a[cur<<1].right-a[cur<<1].left+1);
        a[cur<<1|1].sum+=a[cur].p*(a[cur<<1|1].right-a[cur<<1|1].left+1);
        a[cur].p=0;
    }
    int mid=(a[cur].left+a[cur].right)>>1;
    if(y<=mid)
        return query(cur<<1,x,y);
    else if(x>mid)
        return query(cur<<1|1,x,y);
    else{
        return query(cur<<1,x,mid)+query(cur<<1|1,mid+1,y);
    }
}
int main(){
    while(scanf("%d%d",&n,&q)!=EOF){
        built(1,1,n);
        while(q--){
            char s[2]; scanf("%s",s);

            if(s[0]=='C'){
                int x,y;
                ll val;
                scanf("%d%d%I64d",&x,&y,&val);
                update(1,x,y,val);
            }
            else{
                int x,y;
                scanf("%d%d",&x,&y);
                printf("%I64d\n",query(1,x,y));
            }
        }
    }
    return 0;
}



联系
我们