Featured image of post 洛谷P2357题解

洛谷P2357题解

封面来源

Pixiv tragic heroine-74016100

线段树模板题,区间修改,区间求和

第一个墓碑其实和后面几块处理方法相同,相当于对$[1,1]$操作

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define int long long
#define FOR(i,l,r) for(register int i=l;i<=r;i++)
#define mid ((l+r)>>1)
#define differ(a,b) (b-a+1)
#define lc p<<1
#define rc p<<1|1
using namespace std;
// #define FOR(i,l,r) for(register int i=l;i<=r;i++)
const int N = 2e5+7;
int n,f;
struct SGN{
    int sum,lz;
}nd[N<<2];
int fs[N];
int ma;//
void pushup(int p){
    nd[p].sum=nd[lc].sum+nd[rc].sum;
}
void build(int p,int l,int r){
    if(l==r){
        nd[p].sum=fs[l];
        return;
    }
    build(lc,l,mid);
    build(rc,mid+1,r);
    pushup(p);
}
void pushdown(int p,int l,int r){
    if(nd[p].lz){
        nd[lc].lz+=nd[p].lz;
        nd[rc].lz+=nd[p].lz;
        nd[lc].sum+=nd[p].lz*differ(l,mid);
        nd[rc].sum+=nd[p].lz*differ((mid+1),r);
        nd[p].lz=0;
    }
}
void update(int p,int l,int r,int x,int y,int k){
    if(x<=l&&y>=r){
        nd[p].sum+=differ(l,r)*k;
        nd[p].lz+=k;
    }
    else{
        pushdown(p,l,r);
        if(x<=mid){
            update(lc,l,mid,x,y,k);
        }
        if(y>mid){
            update(rc,mid+1,r,x,y,k);
        }
        pushup(p);
    }
}
int Qsum(int p,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return nd[p].sum;
    }
    pushdown(p,l,r);
    int ans = 0;
    if(x<=mid){
        ans+=Qsum(lc,l,mid,x,y);
    }
    if(y>mid){
        ans+=Qsum(rc,mid+1,r,x,y);
    }
    return ans;
    // return Qsum(lc,l,mid,x,y)+Qsum(rc,mid+1,r,x,y);
}
signed main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>f;
    FOR(i,1,n){
        cin>>fs[i];
    }
    build(1,1,n);
    int op;
    FOR(i,1,f){

        cin>>op;
        if(op==1){
            int l,r,k;
            cin>>l>>r>>k;
            update(1,1,n,l,r,k);
        }
        if(op==2){
            int k;
            cin>>k;
            update(1,1,n,1,1,k);
        }
        if(op==3){
            int k;
            cin>>k;
            update(1,1,n,1,1,-k);
        }
        if(op==4){
            int l,r;
            cin>>l>>r;
            cout<<Qsum(1,1,n,l,r)<<endl;
        }
        if(op==5){
            cout<<Qsum(1,1,n,1,1)<<endl;
        }
    }
}
所念皆星河
Built with Hugo
主题 StackJimmy 设计