mxqz线段树

喵仔牛奶 @ 2022-11-04 21:18:50

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n, q, opt, l, r, k, a[N], sum[N << 2], tag[N << 2], ass[N << 2], qwq[N << 1];
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) {
    sum[p] = max(sum[ls(p)], sum[rs(p)]);
}
void build(int p, int l, int r) {
    if (l == r) { sum[p] = a[l]; return; }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid), build(rs(p), mid + 1, r);
    push_up(p);
}
inline void push_tag(int p, int fa) {
    if (qwq[fa]) sum[p] = ass[fa];
    tag[p] += tag[fa], sum[p] += tag[fa];
}
inline void push_down(int p) {
    push_tag(ls(p), p), push_tag(rs(p), p), tag[p] = qwq[p] = 0;
}
inline void modify(int p, int nl, int nr, int l, int r, ll k) {
    push_down(p);
    if (nl <= l && r <= nr) {
        tag[p] += k, sum[p] += k; 
        return;
    }
    int mid = (l + r) >> 1;
    if (nl <= mid) modify(ls(p), nl, nr, l, mid, k);
    if (nr > mid) modify(rs(p), nl, nr, mid + 1, r, k);
    push_up(p);
}
inline void assign(int p, int nl, int nr, int l, int r, ll k) {
    push_down(p);
    if (nl <= l && r <= nr) {
        qwq[p] = 1, ass[p] = k, tag[p] = 0, sum[p] = k;
        return;
    }
    int mid = (l + r) >> 1;
    if (nl <= mid) assign(ls(p), nl, nr, l, mid, k);
    if (nr > mid) assign(rs(p), nl, nr, mid + 1, r, k);
    push_up(p);
}
ll query(int p, int nl, int nr, int l, int r) {
    ll res = -LLONG_MAX;
    push_down(p);
    if (nl <= l && r <= nr) return sum[p];
    int mid = (l + r) >> 1;
    if (nl <= mid) res = max(res, query(ls(p), nl, nr, l, mid));
    if (nr > mid) res = max(res, query(rs(p), nl, nr, mid + 1, r));
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= q; i ++) {
        cin >> opt >> l >> r;
        if (opt == 1) cin >> k, assign(1, l, r, 1, n, k);
        else if (opt == 2) cin >> k, modify(1, l, r, 1, n, k);
        else cout << query(1, l, r, 1, n) << '\n';
    }
    return 0;
}

by yyandy @ 2022-11-04 21:21:26

@喵仔牛奶 推平操作 qwq 标记也要下传吧。

by 喵仔牛奶 @ 2022-11-04 21:23:30

@yyandy qwq

https://www.luogu.com.cn/record/92803455

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n, q, opt, l, r, k, a[N], sum[N << 2], tag[N << 2], ass[N << 2], qwq[N << 1];
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) {
    sum[p] = max(sum[ls(p)], sum[rs(p)]);
}
void build(int p, int l, int r) {
    if (l == r) { sum[p] = a[l]; return; }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid), build(rs(p), mid + 1, r);
    push_up(p);
}
inline void push_tag(int p, int fa) {
    if (qwq[fa]) qwq[p] = 1, sum[p] = ass[fa];
    tag[p] += tag[fa], sum[p] += tag[fa];
}
inline void push_down(int p) {
    push_tag(ls(p), p), push_tag(rs(p), p), tag[p] = qwq[p] = 0;
}
inline void modify(int p, int nl, int nr, int l, int r, ll k) {
    push_down(p);
    if (nl <= l && r <= nr) {
        tag[p] += k, sum[p] += k; 
        return;
    }
    int mid = (l + r) >> 1;
    if (nl <= mid) modify(ls(p), nl, nr, l, mid, k);
    if (nr > mid) modify(rs(p), nl, nr, mid + 1, r, k);
    push_up(p);
}
inline void assign(int p, int nl, int nr, int l, int r, ll k) {
    push_down(p);
    if (nl <= l && r <= nr) {
        qwq[p] = 1, ass[p] = k, tag[p] = 0, sum[p] = k;
        return;
    }
    int mid = (l + r) >> 1;
    if (nl <= mid) assign(ls(p), nl, nr, l, mid, k);
    if (nr > mid) assign(rs(p), nl, nr, mid + 1, r, k);
    push_up(p);
}
ll query(int p, int nl, int nr, int l, int r) {
    ll res = -LLONG_MAX;
    push_down(p);
    if (nl <= l && r <= nr) return sum[p];
    int mid = (l + r) >> 1;
    if (nl <= mid) res = max(res, query(ls(p), nl, nr, l, mid));
    if (nr > mid) res = max(res, query(rs(p), nl, nr, mid + 1, r));
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= q; i ++) {
        cin >> opt >> l >> r;
        if (opt == 1) cin >> k, assign(1, l, r, 1, n, k);
        else if (opt == 2) cin >> k, modify(1, l, r, 1, n, k);
        else cout << query(1, l, r, 1, n) << '\n';
    }
    return 0;
}

by 喵仔牛奶 @ 2022-11-04 21:24:33

https://www.luogu.com.cn/record/92803732

已改成

ll n, q, opt, l, r, k, a[N], sum[N << 2], tag[N << 2], ass[N << 2], qwq[N << 2];

by yyandy @ 2022-11-05 06:47:52

@喵仔牛奶

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
ll n, q, opt, l, r, k, a[N], sum[N << 2], tag[N << 2], ass[N << 2], qwq[N << 2];
inline int ls(int p) { return p << 1; }
inline int rs(int p) { return p << 1 | 1; }
inline void push_up(int p) {
    sum[p] = max(sum[ls(p)], sum[rs(p)]);
}
void build(int p, int l, int r) {
    if (l == r) { sum[p] = a[l]; return; }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid), build(rs(p), mid + 1, r);
    push_up(p);
}
inline void push_tag(int p, int fa) {
    if (qwq[fa]) qwq[p] = 1, tag[p]=0 , ass[p] = ass[fa], sum[p] = ass[fa];
    tag[p] += tag[fa], sum[p] += tag[fa];
}
inline void push_down(int p) {
    push_tag(ls(p), p), push_tag(rs(p), p), tag[p] = qwq[p] = 0;
}
inline void modify(int p, int nl, int nr, int l, int r, ll k) {
    if (nl <= l && r <= nr) {
        tag[p] += k, sum[p] += k; 
        return;
    }push_down(p);
    int mid = (l + r) >> 1;
    if (nl <= mid) modify(ls(p), nl, nr, l, mid, k);
    if (nr > mid) modify(rs(p), nl, nr, mid + 1, r, k);
    push_up(p);
}
inline void assign(int p, int nl, int nr, int l, int r, ll k) {
    if (nl <= l && r <= nr) {
        qwq[p] = 1, ass[p] = k, tag[p] = 0, sum[p] = k;
        return;
    }push_down(p);
    int mid = (l + r) >> 1;
    if (nl <= mid) assign(ls(p), nl, nr, l, mid, k);
    if (nr > mid) assign(rs(p), nl, nr, mid + 1, r, k);
    push_up(p);
}
ll query(int p, int nl, int nr, int l, int r) {
    ll res = -LLONG_MAX;
    if (nl <= l && r <= nr) return sum[p];
    int mid = (l + r) >> 1;push_down(p);
    if (nl <= mid) res = max(res, query(ls(p), nl, nr, l, mid));
    if (nr > mid) res = max(res, query(rs(p), nl, nr, mid + 1, r));
    return res;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i ++)
        cin >> a[i];
    build(1, 1, n);
    for (int i = 1; i <= q; i ++) {
        cin >> opt >> l >> r;
        if (opt == 1) cin >> k, assign(1, l, r, 1, n, k);
        else if (opt == 2) cin >> k, modify(1, l, r, 1, n, k);
        else cout << query(1, l, r, 1, n) << '\n';
    }
    return 0;
}

稍微再改了一点，对了。

你这个写法和我习惯的有点不同。