【模板】线段树

已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100010;

int n, m;
ll a[N];
struct node{
    ll val, lazy;
}seg[N<<2];

void pushdown(int o, int l, int r){
    if(seg[o].lazy){
        seg[o<<1].lazy += seg[o].lazy;
        seg[o<<1|1].lazy += seg[o].lazy;
        int mid = (l + r) >> 1;
        seg[o<<1].val += seg[o].lazy*(mid-l+1);
        seg[o<<1|1].val += seg[o].lazy*(r-mid);
        seg[o].lazy = 0;
    }
}

void build(int o, int l, int r){
    seg[o].lazy = 0ll;
    if(l == r){
        seg[o].val = a[l];
        return;
    }
    int mid = (l+r)>>1;
    build(o<<1, l, mid);
    build(o<<1|1, mid+1, r);
    seg[o].val = seg[o<<1].val + seg[o<<1|1].val;
}

void modify(int o, int be, int en, int l, int r, ll add){
    if(be >= l && r >= en){
        seg[o].val += add*(en-be+1);
        seg[o].lazy += add;
        return;
    }    

    pushdown(o, be, en);
    int mid = (be+en)>>1;
    if(l <= mid) modify(o<<1, be, mid, l, r, add);
    if(r > mid) modify(o<<1|1, mid+1, en, l, r, add);
    seg[o].val = seg[o<<1].val + seg[o<<1|1].val;
}

ll query(int o, int be, int en, int l, int r){
    if(l <= be && en <= r){
        return seg[o].val;
    }

    pushdown(o, be, en);
    int mid = (be+en)>>1;
    ll s = 0;
    if(l <= mid) s += query(o<<1, be, mid, l, r);
    if(r > mid) s += query(o<<1|1, mid+1, en, l, r);
    return s;
}

int main(){
    int cs, x, y;
    ll k;

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);

    build(1, 1, n);


    for(int i = 1; i <= m; i++){
        scanf("%d", &cs);
        if(cs == 1){
            scanf("%d%d%lld", &x, &y, &k);
            modify(1, 1, n, x, y, k);
        }
        else{
            scanf("%d%d", &x, &y);
            printf("%lld\n", query(1, 1, n, x, y));
        }
    }

    return 0;
}

已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数乘上x
2.将某区间每一个数加上x
3.求出某区间每一个数的和

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 100010;

int n, m;
ll p;
ll a[N];
struct node{
    ll val;
    ll lazy1, lazy2;
}seg[N<<2];

template <typename T>
T read(){
    T N(0), F(1);
    char C = getchar();
    for(; !isdigit(C); C = getchar()) if(C == '-') F = -1;
    for(; isdigit(C); C = getchar()) N = N*10 + C-48;
    return N*F;
}

void pushdown1(int o, int l, int r){
    if(seg[o].lazy2 != 1){//这里传lazy的顺序不能变，我不知道为什么
        seg[o<<1].lazy1 = seg[o<<1].lazy1 * seg[o].lazy2%p;
        seg[o<<1|1].lazy1 = seg[o<<1|1].lazy1 * seg[o].lazy2%p;
        seg[o<<1].lazy2 = seg[o<<1].lazy2 * seg[o].lazy2%p;
        seg[o<<1|1].lazy2 = seg[o<<1|1].lazy2 * seg[o].lazy2%p;
        seg[o<<1].val = seg[o<<1].val * seg[o].lazy2%p;
        seg[o<<1|1].val = seg[o<<1|1].val * seg[o].lazy2%p;
        seg[o].lazy2 = 1;
    }
    if(seg[o].lazy1){
        seg[o<<1].lazy1 = (seg[o<<1].lazy1 + seg[o].lazy1)%p;
        seg[o<<1|1].lazy1 =(seg[o<<1|1].lazy1 + seg[o].lazy1)%p;
        int mid = (l + r) >> 1;
        seg[o<<1].val = (seg[o<<1].val + seg[o].lazy1*(mid-l+1)%p)%p;
        seg[o<<1|1].val = (seg[o<<1|1].val + seg[o].lazy1*(r-mid)%p)%p;
        seg[o].lazy1 = 0;
    }
}

void build(int o, int l, int r){
    seg[o].lazy1 = 0ll; seg[o].lazy2 = 1ll;
    if(l == r){
        seg[o].val = a[l]%p;
        return;
    }
    int mid = (l+r)>>1;
    build(o<<1, l, mid);
    build(o<<1|1, mid+1, r);
    seg[o].val = (seg[o<<1].val + seg[o<<1|1].val)%p;
}

void update(int o, int be, int en, int l, int r, ll add){
    if(en < l || r < be) return;
    if(be >= l && r >= en){
        seg[o].val = seg[o].val * add%p;
        seg[o].lazy1 = seg[o].lazy1 * add%p;
        seg[o].lazy2 = seg[o].lazy2 * add%p;
        return;
    }
    pushdown1(o, be, en);
    int mid = (be + en)>>1;

    if(l <= mid) update(o<<1, be, mid, l, r, add);
    if(r > mid) update(o<<1|1, mid+1, en, l, r, add);
    seg[o].val = (seg[o<<1].val + seg[o<<1|1].val)%p;
}

void modify(int o, int be, int en, int l, int r, ll add){
    if(en < l || r < be) return;
    if(be >= l && r >= en){
        seg[o].val = (seg[o].val + add*(en-be+1))%p;
        seg[o].lazy1 = (seg[o].lazy1 + add)%p;
        return;
    }    

    pushdown1(o, be, en);
    int mid = (be+en)>>1;
    modify(o<<1, be, mid, l, r, add);
    modify(o<<1|1, mid+1, en, l, r, add);
    seg[o].val = (seg[o<<1].val + seg[o<<1|1].val)%p;
}

ll query(int o, int be, int en, int l, int r){
    if(en < l || r < be) return 0;
    if(l <= be && en <= r){
        return seg[o].val%p;
    }

    pushdown1(o, be, en);
    int mid = (be+en)>>1;
    ll s = 0;
    s = (s + query(o<<1, be, mid, l, r))%p;
    s = (s + query(o<<1|1, mid+1, en, l, r))%p;
    seg[o].val = (seg[o<<1].val + seg[o<<1|1].val)%p;
    return s%p;
}

int main(){
    int cs, x, y;
    ll k;

    n = read<int>(); m = read<int>(); p = read<ll>();
    for(int i = 1; i <= n; i++) a[i] = read<ll>();

    build(1, 1, n);

    for(int i = 1; i <= m; i++){
        cs = read<int>();
        if(cs == 1){
            x = read<int>(); y = read<int>(); k = read<ll>();
            update(1, 1, n, x, y, k);
        }
        else if(cs == 2){
            x = read<int>(); y = read<int>(); k = read<ll>();
            modify(1, 1, n, x, y, k);
        }
        else if(cs == 3){
            x = read<int>(); y = read<int>();
            printf("%lld\n", query(1, 1, n, x, y)%p);
        }
    }

    return 0;
}