桐柏S7-T4题解

· · 个人记录

一、25pts 部分分：
依题意模拟即可，时间复杂度 O(nQ)
代码如下： 

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,q,fr[100005],op,a,b,c,sum;
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&fr[i]);
    }
    for(int i=1;i<=q;i++){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&a,&b,&c);
            for(int j=a;j<=b;j++){
                fr[j]+=c;
            }
        }
        else{
            scanf("%lld%lld",&a,&b);
            sum=0;
            for(int j=a;j<=b;j++){
                sum+=fr[j];
            }
            printf("%lld\n",sum);
        }
    }
    return 0;
}

二、70pts 部分分：
设添加操作有 Q_1 次，查询操作有 Q_2 次。
我们可以使用前缀和进行优化，先预处理一个前缀和数组 sum 出来，即可直接 O(1) 访问，然后在每次更改时更改 l 之后的所有 sum_i 即可，时间复杂度 O(nQ_1+Q_2)，在 Q_1\leq 500 的情况下可过 代码如下： 

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,q,fr[100005],op,a,b,c,sum[100005];
int main(){
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&fr[i]);
        sum[i]=sum[i-1]+fr[i];
    }
    for(int i=1;i<=q;i++){
        scanf("%lld",&op);
        if(op==1){
            scanf("%lld%lld%lld",&a,&b,&c);
            for(int j=a;j<=b;j++){
                sum[j]+=(j-a+1)*c;
            }
            for(int j=b+1;j<=n;j++){
                sum[j]+=(b-a+1)*c;
            }
        }
        else{
            scanf("%lld%lld",&a,&b);
            printf("%lld\n",sum[b]-sum[a-1]);
        }
    }
    return 0;
}

三、正解：
线段树将每个长度不为 1 的区间划分成左右两个区间递归求解，把整个线段划分为一个树形结构，通过合并左右两区间信息来求得该区间的信息。这种数据结构可以方便的进行大部分的区间操作。——摘自OI-Wiki《线段树》
代码如下： 

#include<bits/stdc++.h>
#define N 100005
using namespace std;
typedef long long ll;
int a[N];
struct node{
    int l,r;
    ll sum;
    ll lazy;
}t[N*4];
void pushup(int p){
    t[p].sum=t[p<<1].sum+t[p<<1|1].sum;
}
void build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    pushup(p);
}
int len(int p){
    return t[p].r-t[p].l+1; 
}
void brush(int p,ll k){
    t[p].lazy+=k;
    t[p].sum+=len(p)*k;
}
void push_down(int p){
    brush(p<<1,t[p].lazy);
    brush(p<<1|1,t[p].lazy);
    t[p].lazy=0;
}
void update(int p,int l,int r,ll k){
    if(l<=t[p].l&&t[p].r<=r){
        brush(p,k);
        return;
    }
    push_down(p);
    int mid=(t[p].l+t[p].r)>>1;
    if(l<=mid){
        update(p<<1,l,r,k);
    }
    if(r>=mid+1){
        update(p<<1|1,l,r,k);
    }
    pushup(p);
}
ll query(int p,int l,int r){
    if(l<=t[p].l&&t[p].r<=r){
        return t[p].sum;
    }
    int mid=(t[p].l+t[p].r)>>1;
    push_down(p);
    ll res=0;
    if(l<=mid){
        res+=query(p<<1,l,r);
    }
    if(r>=mid+1){
        res+=query(p<<1|1,l,r);
    }
    return res;
}
int main(){
    int n,m;
    int opt,x,y,k;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){scanf("%d",&a[i]);}
    build(1,1,n);
    while(m--){
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&x,&y,&k);
            update(1,x,y,k);
        }
        else if(opt==2){
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(1,x,y));
        }
    }
    return 0;
}