分享线段树的另一种写法

不打标记

#include <bits/stdc++.h>

using namespace std;

int n, m;
const int N = 200010;

struct info{
    int minv, mincnt;
};

info operator + (const info &l, const info &r){
    info a;
    a.minv = min(l.minv, r.minv);
    if(l.minv == r.minv) a.mincnt = l.mincnt + r.mincnt;
    else if(l.minv < r.minv) a.mincnt = l.mincnt;
    else a.mincnt = r.mincnt;
    return a;
}

struct Node{
    info val;
}seg[N * 4];

int a[N];

void update(int id){
    seg[id].val = seg[id * 2].val + seg[id * 2 + 1].val;
}

void build(int id, int l, int r){
    if(l == r) seg[id] = {a[l], 1};
    else{
        int mid = l + r >> 1;
        build(id << 1, l, mid), build(id << 1 | 1, mid + 1, r);
        update(id);
    }
}

void change(int id, int l, int r, int pos, int val){
    if(l == r){
        seg[id].val = {val, 1};
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) change(id * 2, l, mid, pos, val);
    else if(pos > mid) change(id * 2 + 1, mid + 1, r, pos, val);
    update(id);
    return;
}

info query(int id, int l, int r, int ql, int qr){
    if(l == ql && r == qr) return seg[id].val;
    int mid = l + r >> 1;
    if(qr <= mid) return query(id << 1, l, mid, ql, qr);
    if(ql > mid) return query(id << 1 | 1, mid + 1, r, ql, qr);
    return query(id << 1, l, mid, ql, mid) + query(id << 1 | 1, mid + 1, r, mid + 1, qr);
}

int main(){
    scanf("%d %d",&n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d",&a[i]);
    }
    build(1, 1, n);
    while(m -- ){
        int op, x, d;
        scanf("%d %d %d",&op, &x, &d);
        if(op == 1) change(1, 1, n, x, d);
        else{
            printf("%d %d\n",query(1, 1, n, x, d).minv,query(1, 1, n, x, d).mincnt);
        }
    }
    return 0;
}

打标记

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;

int n, m;
int a[N];

struct info{
    LL maxv;
};

struct tag{
    LL add;
};

info operator + (const info & l, const info & r){
    return {max(l.maxv, r.maxv)};
} 

info operator + (const info & v, const tag & t){
    return {v.maxv + t.add};
}

tag operator + (const tag & t1, const tag & t2){
    return {t1.add + t2.add};
}

struct node{
    info val;
    tag t;
}seg[N * 4];

void settag(int id, tag t){
    seg[id].val = seg[id].val + t;
    seg[id].t = seg[id].t + t;
    // seg[id].t.add = 0;
}

void update(int id){
    seg[id].val = seg[id << 1].val + seg[id << 1 | 1].val;
}

void pushdown(int id){
    if(seg[id].t.add){
        settag(id << 1, seg[id].t), settag(id << 1 | 1, seg[id].t);
        seg[id].t.add = 0;
    }
}

void build(int id, int l, int r){
    if(l == r){
        seg[id] = {a[l]};
        return;
    }
    int mid = l + r >> 1;
    build(id << 1, l, mid), build(id << 1 | 1, mid + 1, r);
    update(id);
}

void modify(int id, int l, int r, int ql, int qr, tag t){
    if(l == ql && r == qr){
        settag(id, t);
        return;
    }
    int mid = l + r >> 1;
    pushdown(id);
    if(qr <= mid) modify(id << 1, l, mid, ql, qr, t);
    else if(ql > mid) modify(id << 1 | 1, mid + 1, r, ql, qr, t);
    else{
        modify(id << 1, l, mid, ql, mid, t);
        modify(id << 1 | 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}

info query(int id, int l, int r, int ql, int qr){
    if(l == ql && r == qr) return seg[id].val;
    int mid = l + r >> 1;
    pushdown(id);
    if(ql > mid) return query(id << 1 | 1, mid + 1, r, ql, qr);
    if(qr <= mid) return query(id << 1, l, mid, ql, qr);
    return query(id << 1 | 1, mid + 1, r, mid + 1, qr) + query(id << 1, l, mid, ql, mid);
}

int main(){
    scanf("%d %d",&n, &m);
    for(int i = 1; i <= n; i ++ ){
        scanf("%d",&a[i]);
    }
    build(1, 1, n);
    while(m -- ){
        // cout << endl;
        int op;
        scanf("%d",&op);
        if(op == 1){
            int l, r, d;
            scanf("%d %d %d",&l, &r, &d);
            modify(1, 1, n, l, r,(tag){d});
        }
        else{
            int l, r;
            scanf("%d %d",&l, &r);
            auto ans = query(1, 1, n, l, r);
            printf("%lld\n", ans.maxv);
        }
    }
}