[一本通学习笔记] 线段树

题目很模板

10127. 「一本通 4.3 练习 1」最大数

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

const int N = 1000005;

int val[N], a[N], m, p, n;

void pushup(int p) { val[p] = max(val[p * 2], val[p * 2 + 1]); }

void modify(int p, int l, int r, int pos, int v) {
    if (l == r) {
        val[p] = v;
    } else {
        int mid = (l + r) >> 1;
        if (pos <= mid)
            modify(p * 2, l, mid, pos, v);
        else
            modify(p * 2 + 1, mid + 1, r, pos, v);
        pushup(p);
    }
}

int query(int p, int l, int r, int ql, int qr) {
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return val[p];
    int mid = (l + r) / 2;
    return max(query(p * 2, l, mid, ql, qr), query(p * 2 + 1, mid + 1, r, ql, qr));
}

int main() {
    cin >> m >> p;
    n = m;
    int len = 0;
    int lastans = 0;
    for (int i = 1; i <= m; i++) {
        char op;
        int x;
        cin >> op >> x;
        if (op == 'A') {
            x += lastans;
            x %= p;
            modify(1, 1, n, ++len, x);
        } else {
            cout << (lastans = query(1, 1, n, len - x + 1, len)) << endl;
        }
    }
}

10128. 「一本通 4.3 练习 2」花神游历各国

维护区间最大值及位置，修改的时候如果当前区间最大值大于1就继续，否则剪枝。这样等价于做了不超过O(nlogn)次单点修改，实现上和普通线段树略有出入。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll N = 400005;

ll n, m, val[N], mv[N], mx[N], a[N];

void pushup(ll p) {
    mv[p] = max(mv[p * 2], mv[p * 2 + 1]);
    if (mx[p] == mx[p * 2])
        mx[p] = mx[p * 2];
    else
        mx[p] = mx[p * 2 + 1];
    val[p] = val[p * 2] + val[p * 2 + 1];
}

void build(ll p, ll l, ll r) {
    if (l == r) {
        val[p] = mv[p] = a[l];
        mx[p] = l;
    } else {
        build(p * 2, l, (l + r) / 2);
        build(p * 2 + 1, (l + r) / 2 + 1, r);
        pushup(p);
    }
}

void modify(ll p, ll l, ll r, ll ql, ll qr) {
    if (l > qr || r < ql || mv[p] <= 1)
        return;
    if (l == r) {
        val[p] = mv[p] = sqrt(val[p]);
        return;
    }
    modify(p * 2, l, (l + r) / 2, ql, qr);
    modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
    pushup(p);
}

ll query(ll p, ll l, ll r, ll ql, ll qr) {
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return val[p];
    return query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr);
}

int main() {
    cin >> n;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        ll t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        if (t1 == 1) {
            cout << query(1, 1, n, t2, t3) << endl;
        } else {
            modify(1, 1, n, t2, t3);
        }
    }
}

10129. 「一本通 4.3 练习 3」维护序列

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

const ll N = 1000005;
ll val[N], ta[N], tb[N], n, P, m, a[N], t1, t2, t3, t4;

void pushup(ll p) { val[p] = (val[p * 2] + val[p * 2 + 1]) % P; }
void pushdown(ll p, ll l, ll r) {
    if (tb[p] != 1) {
        tb[p * 2] *= tb[p];
        tb[p * 2 + 1] *= tb[p];
        ta[p * 2] *= tb[p];
        ta[p * 2 + 1] *= tb[p];
        val[p * 2] *= tb[p];
        val[p * 2 + 1] *= tb[p];
        tb[p] = 1;
    }
    if (ta[p]) {
        ta[p * 2] += ta[p];
        ta[p * 2 + 1] += ta[p];
        val[p * 2] += ta[p] * ((l + r) / 2 - l + 1);
        val[p * 2 + 1] += ta[p] * (r - (l + r) / 2);
        ta[p] = 0;
    }
    val[p * 2] %= P;
    val[p * 2 + 1] %= P;
    ta[p * 2] %= P;
    ta[p * 2 + 1] %= P;
    tb[p * 2] %= P;
    tb[p * 2 + 1] %= P;
}
void build(ll p, ll l, ll r) {
    ta[p] = 0;
    tb[p] = 1;
    if (l == r) {
        val[p] = a[l];
        return;
    }
    build(p * 2, l, (l + r) / 2);
    build(p * 2 + 1, (l + r) / 2 + 1, r);
    pushup(p);
}
void modify(ll p, ll l, ll r, ll ql, ll qr, ll add, ll mul) {
    if (l > qr || r < ql)
        return;
    if (l >= ql && r <= qr) {
        ta[p] += add;
        tb[p] *= mul;
        ta[p] *= mul;
        val[p] *= mul;
        val[p] += add * (r - l + 1);
        ta[p] %= P;
        tb[p] %= P;
        val[p] %= P;
    } else {
        pushdown(p, l, r);
        modify(p * 2, l, (l + r) / 2, ql, qr, add, mul);
        modify(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr, add, mul);
        pushup(p);
    }
}
ll query(ll p, ll l, ll r, ll ql, ll qr) {
    if (l > qr || r < ql)
        return 0;
    if (l >= ql && r <= qr)
        return val[p];
    pushdown(p, l, r);
    return (query(p * 2, l, (l + r) / 2, ql, qr) + query(p * 2 + 1, (l + r) / 2 + 1, r, ql, qr)) % P;
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> P;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    cin >> m;
    for (ll i = 1; i <= m; i++) {
        cin >> t1 >> t2 >> t3;
        if (t1 <= 2)
            cin >> t4;
        if (t1 == 1) {
            modify(1, 1, n, t2, t3, 0, t4);
        }
        if (t1 == 2) {
            modify(1, 1, n, t2, t3, t4, 1);
        }
        if (t1 == 3) {
            cout << query(1, 1, n, t2, t3) << endl;
        }
    }
}