萌新昧子刚学OI，线段树求调QAQ

kaceqwq @ 2022-08-17 08:05:13

by kaceqwq @ 2022-08-17 08:05:27

#include <bits/stdc++.h>
#define int long long 
using namespace std;
int n, m, a[10000005];
struct Node {
    int l, r, sum, tag1, tag2;
    bool flag;
} tree[10000005];
void Push_up (int p) {
    tree[p].sum = max (tree[p * 2].sum, tree[p * 2 + 1].sum);
}
void Build (int p, int l, int r) {
    tree[p].l = l;
    tree[p].r = r;
    tree[p].sum = -214748364700;
    if (l == r) {
        tree[p].sum = a[l];
        return ;
    }
    int mid = (l + r) / 2;
    Build (p * 2, l, mid);
    Build (p * 2 + 1, mid + 1, r);
    Push_up(p);
}
void Push_down (int p) {
    if (tree[p].flag) {
        tree[p * 2].tag1 = tree[p].tag1;
        tree[p * 2 + 1].tag1 = tree[p].tag1;
        tree[p * 2].tag2 = tree[p].tag2;
        tree[p * 2 + 1].tag2 = tree[p].tag2;
        tree[p * 2].sum = tree[p].tag1 + tree[p].tag2;
        tree[p * 2 + 1].sum = tree[p].tag1 + tree[p].tag2;
        tree[p * 2].flag = tree[p * 2 + 1].flag = 1;
    } else {
        tree[p * 2].tag2 += tree[p].tag2;
        tree[p * 2 + 1].tag2 += tree[p].tag2;
        tree[p * 2].sum += tree[p].tag2;
        tree[p * 2 + 1].sum += tree[p].tag2;
    }
    tree[p].flag = tree[p].tag1 = tree[p].tag2 = 0;
}
void Update1 (int p, int L, int R, int x) {
    if (L <= tree[p].l && tree[p].r <= R) {
        tree[p].tag1 = x;
        tree[p].tag2 = 0;
        tree[p].sum = x;
        tree[p].flag = 1;
        return ;    
    }
    Push_down(p);
    int mid = (tree[p].l + tree[p].r) / 2;
    if (L <= mid) Update1 (p * 2, L, R, x);
    if (R > mid) Update1 (p * 2 + 1, L, R, x);
    Push_up(p);
}
void Update2 (int p, int L, int R, int x) {
    if(L <= tree[p].l && tree[p].r <= R) {
        tree[p].tag2 += x;
        tree[p].sum += x;
        return ;    
    }
    Push_down(p);
    int mid = (tree[p].l + tree[p].r) / 2;
    if (L <= mid) Update1 (p * 2, L, R, x);
    if (R > mid) Update1 (p * 2 + 1, L, R, x);
    Push_up(p);
}
int Query (int p, int L, int R) {
    if (L <= tree[p].l && tree[p].r <= R) return tree[p].sum;
    Push_down (p);
    int mid = (tree[p].l + tree[p].r) / 2;
    int res = -2147483647000;
    if (L <= mid) res = max (res, Query (p * 2, L, R));
    if (R > mid) res = max (res, Query (p * 2 + 1, L, R));
    return res;
}
signed main () {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    Build (1, 1, n);
    while (m--) {
        int op, l, r, k;
        cin >> op >> l >> r;
        if (op == 1) {
            cin >> k;
            Update1 (1, l, r, k);
        }
        if (op == 2) {
            cin >> k;
            Update2 (1, l, r, k);
        }
        else cout << Query (1, l, r) << '\n';
    } 
    return 0;
} 

by JackMerryYoung @ 2022-08-17 08:10:38

@kaceqwq sum 和最大值不能放一起啊？

您这代码我直接蒙了。

by Micnation_AFO @ 2022-08-17 08:10:57

数组开小了，四倍空间。while 循环里面把第二个 if 改为 else if

by Micnation_AFO @ 2022-08-17 08:11:37

@JackMerryYoung 他这个估计是把 sum 当成 dat 直接用了

by kaceqwq @ 2022-08-17 08:12:21

@Leap_hash_jperm 可我是 1e7 唉

by JackMerryYoung @ 2022-08-17 08:14:07

@Leap_hash_jperm 所以错了呀，求和是 sum, 最大值怎么也是 sum???

by Micnation_AFO @ 2022-08-17 08:14:51

@kaceqwq 抱歉，没看清楚

另外，push_down 下传 tag2 的时候，由于是区间推平，t[p * 2] 和 t[p * 2 + 1] 的 tag1 应该赋值为 0，表示加 0。

by Micnation_AFO @ 2022-08-17 08:15:46

@JackMerryYoung 你看他的push_up，就是最大值

by Micnation_AFO @ 2022-08-17 08:18:09

而且 push_down 里面也没有必要 else 吧

by JackMerryYoung @ 2022-08-17 08:20:05

@Leap_hash_jperm 又不是求和的最大值。