线段树

给n个数 $a_{1},a_{2},a_{3}…a_{n}$ 。
支持q个操作：
1 x d，修改 $a_{x}=d$ 。
2 l r，查询 $min_{i=l}^{r}a_{i}$ ，并且求出最小值出现了多少次。

const int N = 200010;
int n, q;
int a[N];

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];

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].val = { a[l],1 };
    }
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r); 
        update(id);
    }
}

//节点为id,对应的区间为[l,r]，修改a[pos]为val
void change(int id, int l, int r, int pos, int val) {
    if (l == r) seg[id].val = { val,1 };
    else {
        int mid = (l + r) / 2;
        if (pos <= mid) change(id * 2, l, mid, pos, val);
        else change(id * 2 + 1, mid + 1, r, pos, val);
        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) / 2;
    //[l,mid]   [mid+1,r]
    if (qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if (ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
}

void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int x, d;
            scanf("%d%d", &x, &d);
            change(1, 1, n, x, d);
        }
        else {
            int l, r; scanf("%d%d", &l, &r);
            info ans = query(1, 1, n, l, r);
            printf("%d %d\n", ans.minv, ans.mincnt);
        }
    }
}

signed main()
{
    int T;
    //T = read();
    T = 1;
    while (T--) {
        solve();
    }
    return 0;
}

给n个数 $a_{1},a_{2},a_{3}…a_{n}$ 。
支持q个操作：
1 x d，修改 $a_{x}=d$ 。
2 l r，查询[l,r]中的最大子段和，也就是找到l≤l′≤r′≤r，使得 $\sum_{i=l'}^{r'}a_{i}$ 最大。

const int N = 200010;
int n, q;
int a[N];

struct info {
    ll mss, mpre, msuf, s;
    info() {}
    info(int a):mss(a),mpre(a),msuf(a),s(a){}
};

info operator+(const info& l, const info& r) {
    info a;
    a.mss = max(l.mss, max(r.mss, l.msuf + r.mpre));
    a.mpre = max(l.mpre, l.s + r.mpre);
    a.msuf = max(r.msuf, l.msuf + r.s);
    a.s = l.s + r.s;
    return a;
}

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

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].val = info(a[l]);
    }
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 1, mid + 1, r); 
        update(id);
    }
}

//节点为id,对应的区间为[l,r]，修改a[pos]为val
void change(int id, int l, int r, int pos, int val) {
    if (l == r) seg[id].val = info(val);
    else {
        int mid = (l + r) / 2;
        if (pos <= mid) change(id * 2, l, mid, pos, val);
        else change(id * 2 + 1, mid + 1, r, pos, val);
        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) / 2;
    //[l,mid]   [mid+1,r]
    if (qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if (ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
}

void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int x, d;
            scanf("%d%d", &x, &d);
            change(1, 1, n, x, d);
        }
        else {
            int l, r; scanf("%d%d", &l, &r);
            info ans = query(1, 1, n, l, r);
            printf("%lld\n", ans.mss);
        }
    }
}

给n个数 $a_{1},a_{2},a_{3}…a_{n}$ 。
支持q个操作：
1 l r d，令所有的 $a_{i}$ (l≤i≤r)加上d。
2 l r，查询 $max_{i=l}^{r}a_{i}$ 。

const int N = 200010;
int n, q;
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& l, const tag& r) {
    return { l.maxv + r.add };
}
tag operator+(const tag& t1, const tag& t2) {
    return { t1.add + t2.add };
}

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


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

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

void pushdown(int id) {
    if (seg[id].t.add != 0) {
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        seg[id].t.add = 0;
    }
}

void build(int id, int l, int r) {
    if (l == r) {
        seg[id].val = { a[l]};
    }
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 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) / 2;
    //[l,mid]   [mid+1,r]
    pushdown(id);
    if (qr <= mid) modify(id * 2, l, mid, ql, qr, t);
    else if (ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else {
        modify(id * 2, l, mid, ql, mid,t);
        modify(id * 2 + 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) / 2;
    //[l,mid]   [mid+1,r]
    pushdown(id);
    if (qr <= mid) return query(id * 2, l, mid, ql, qr);
    else if (ql > mid) return query(id * 2 + 1, mid + 1, r, ql, qr);
    else {
        return query(id * 2, l, mid, ql, mid) + query(id * 2 + 1, mid + 1, r, mid + 1, qr);
    }
}

void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    while (q--) {
        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);
            info ans = query(1, 1, n, l, r);
            printf("%lld\n", ans.maxv);
        }
    }
}

给n个数 $a_{1},a_{2},a_{3}…a_{n}$ 。
支持q个操作：
1 l r d，令所有的 $a_{i}$ (l≤i≤r)加上d。
2 l r d，令所有的 $a_{i}$ (l≤i≤r)乘上d。
3 l r d，令所有的 $a_{i}$ (l≤i≤r)等于d。
4 l r，查询 $\sum_{i=l}^{r}a_{i}mod(10^{9}+7)$ 。

const int N = 200010;
const ll mod = 1e9 + 7;
int n, q;
ll a[N];

struct tag {
    ll mul, add;
};

tag operator+(const tag& t1, const tag& t2) {
    //(x*t1.mul+t1.add)*t2.mul+t2.add
    return { t1.mul * t2.mul % mod,(t1.add * t2.mul + t2.add) % mod };
}

struct node {
    tag t;
    ll val;
    int sz;
}seg[N * 4];


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

void settag(int id, tag t) {
    seg[id].t = seg[id].t + t;
    seg[id].val = (seg[id].val * t.mul + seg[id].sz * t.add) % mod;
}

void pushdown(int id) {
    if (seg[id].t.add != 0 || seg[id].t.mul != 1) {
        settag(id * 2, seg[id].t);
        settag(id * 2 + 1, seg[id].t);
        seg[id].t.add = 0;
        seg[id].t.mul = 1;
    }
}

void build(int id, int l, int r) {
    seg[id].t = { 1,0 };
    seg[id].sz = r - l + 1;
    if (l == r) {
        seg[id].val = { a[l] };
    }
    else {
        int mid = (l + r) / 2;
        build(id * 2, l, mid);
        build(id * 2 + 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) / 2;
    //[l,mid]   [mid+1,r]
    pushdown(id);
    if (qr <= mid) modify(id * 2, l, mid, ql, qr, t);
    else if (ql > mid) modify(id * 2 + 1, mid + 1, r, ql, qr, t);
    else {
        modify(id * 2, l, mid, ql, mid, t);
        modify(id * 2 + 1, mid + 1, r, mid + 1, qr, t);
    }
    update(id);
}

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

void solve() {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    build(1, 1, n);
    while (q--) {
        int op; scanf("%d", &op);
        if (op <= 3) {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            if (op == 1) modify(1, 1, n, l, r, tag{ 1,d });
            else if (op == 2) modify(1, 1, n, l, r, tag{ d ,0 });
            else if (op == 3) modify(1, 1, n, l, r, tag{ 0,d });
        }
        else {
            int l, r; scanf("%d%d", &l, &r);
            ll ans = query(1, 1, n, l, r);
            printf("%lld\n", ans);
        }
    }
}

Last updated 10 months ago