线段树求助
  • 板块学术版
  • 楼主Jefferyz
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/4/6 02:52
  • 上次更新2024/4/6 10:24:45
查看原帖
线段树求助
1022282
Jefferyz楼主2024/4/6 02:52

想问问为什么把ls和rs换成宏定义我本地编译器输出到一半会RE,洛谷就不会。还有max宏定义为什么会比std慢这么多。

#include <bits/stdc++.h>

#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;
const int N = 2e6 + 10;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

int tree[N << 2], tagAdd[N << 2], tagChange[N << 2], a[N];
inline int ls(int p){return p<<1;}
inline int rs(int p){return p<<1|1;}
void pushup(int p) {
    tree[p] = max(tree[ls(p)], tree[rs(p)]);
}

void build(int p, int l, int r) {
    if (l == r) {
        tree[p] = a[l];
        return;
    }
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
    pushup(p);
}

void pushdown(int p) {
    if (tagChange[p] != inf) {
        tagAdd[ls(p)] = tagAdd[rs(p)] = 0;
        tagChange[ls(p)] = tagChange[rs(p)] = tagChange[p];
        tree[ls(p)] = tagChange[p];
        tree[rs(p)] = tagChange[p];
        tagChange[p] = inf;
    }
    if (tagAdd[p]) {
        tagAdd[ls(p)] += tagAdd[p];
        tagAdd[rs(p)] += tagAdd[p];
        tree[ls(p)] += tagAdd[p];
        tree[rs(p)] += tagAdd[p];
        tagAdd[p] = 0;
    }
}

void update(int p, int lp, int rp, int l, int r, int k, int type) {
    if (lp >= l && rp <= r) {
        if (type == 2) tagAdd[p] += k, tree[p] += k;
        if (type == 1) tagChange[p] = k, tagAdd[p] = 0, tree[p] = k;
        return;
    }
    pushdown(p);
    int mid = (lp + rp) >> 1;
    if (l <= mid) update(ls(p), lp, mid, l, r, k, type);
    if (r > mid) update(rs(p), mid + 1, rp, l, r, k, type);
    pushup(p);
}

int query(int p, int lp, int rp, int l, int r) {
    int ans = -inf;
    if (lp >= l && rp <= r) return tree[p];
    pushdown(p);
    int mid = (lp + rp) >> 1;
    if (l <= mid) ans = max(ans, query(ls(p), lp, mid, l, r));
    if (r > mid) ans = max(ans, query(rs(p), mid + 1, rp, l, r));
    return ans;
}

signed main() {
    //freopen("P1253_5.in", "r", stdin);
    int n = read(), q = read();
    for (int i = 1; i <= n; ++i) a[i] = read();
    memset(tagChange, 0x3f, sizeof tagChange);
    build(1, 1, n);
    while (q--) {
        int opt = read();
        if (opt == 3) {
            int l = read(), r = read();
            printf("%lld\n", query(1, 1, n, l, r));
        } else {
            int l = read(), r = read(), x = read();
            update(1, 1, n, l, r, x, opt);
        }
    }
    return 0;
}
2024/4/6 02:52
加载中...