线段树板子 30pts求条 玄关

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 2e5 + 5, INF = 0x7f7f7f7f;
int n, q, w[N];
ll tag[8*N];
struct node{
    ll l, r, s, m; // s = sum, m = min
}tree[8*N];

inline int ls(int u){return u<<1;}
inline int rs(int u){return u<<1|1;}
inline int mid(int l, int r){return l+(r-l >> 1);}

inline void pushup(int u){
    tree[u].s = tree[ls(u)].s + tree[rs(u)].s;
    tree[u].m = min(tree[ls(u)].m, tree[rs(u)].m);
}

void build(int u, int l, int r){
    if(l == r){
        tree[u] = {l, r, w[l], w[l]};
        return;
    }
    tree[u] = {l, r, -1, INF};
    int md = mid(l, r);
    build(ls(u), l, md);
    build(rs(u), md+1, r);
    pushup(u);
}

inline void mtag(int u, ll k){
    tag[u] += k;
    tree[u].s += (tree[u].r-tree[u].l+1)*k;
    tree[u].m += k;
}

inline void pushdown(int u){
    if(!tag[u]) return;
    mtag(ls(u), tag[u]);
    mtag(rs(u), tag[u]);
    tag[u] = 0;
}

void modify(int u, int l, int r, ll k){
    node self = tree[u];
    if(l <= self.l && self.r <= r){
        mtag(u, k);
        return;
    }
    pushdown(u);
    int md = mid(self.l, self.r);
    if(l <= md) modify(ls(u), l, r, k);
    if(r > md) modify(rs(u), l, r, k);
    pushup(u);
}

ll query(int u, int l, int r, bool qtype){ // qtype 1=sum 0=min
    node self = tree[u];
    if(l <= self.l && self.r <= r){
        return qtype ? self.s : self.m;
    }
    int md = mid(self.l, self.r), res = (qtype ? 0 : INF), tmpres;
    pushdown(u);
    if(l <= md) res = query(ls(u), l, r, qtype);
    if(r > md){
        tmpres = query(rs(u), l, r, qtype);
        res = qtype ? res + tmpres : min(res, tmpres);
    }
    // pushup(u);
    return res;
}

int main(){
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> w[i];
    build(1, 1, n);
    char op;
    ll x, y, z;
    for(int i=1; i<=q; i++){
        cin >> op >> x >> y;
        if(op == 'P'){
            cin >> z;
            modify(1, x, y, z);
        }else if(op == 'S'){
            cout << query(1, x, y, true) << "\n";
        }else{
            cout << query(1, x, y, false) << "\n";
        }
    }
    return 0;
}