SMT 50pts 求调

STA_Morlin @ 2022-08-01 17:23:43

by STA_Morlin @ 2022-08-01 17:26:43

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int man = 2e6+10;
const ll rec = 2e9+10;
struct SMT {
    int mod;
    ll a[man], d[man<<2], b[man<<2], e[man<<2];
    void build (int s, int t, int p) {
        e[p] = rec;
        if (s == t) d[p] = a[s];
        else {
            int mid = s+(t-s>>1);
            build(s, mid, p<<1);
            build(mid+1, t, (p<<1)|1);
            d[p] = max(d[p<<1], d[p<<1|1]);
        }
        return ;
    }
    void pushdown (int s, int t, int p) {
        int l = p<<1, r = p<<1|1;
        if (e[p] != rec) {
            d[l] = e[l] = e[p];
            d[r] = e[r] = e[p];
            b[l] = b[r] = 0;
            e[p] = rec;
        }
        b[l] += b[p];
        b[r] += b[p];
        d[l] += b[p];
        d[r] += b[p];
        b[p] = 0;
        return ;
    }
    void upd (int l, int r, int s, int t, int p, ll c) {
        if (l<=s && t<=r) {
            d[p] = e[p] = c;
            b[p] = 0;
        } else {
            int mid = s+(t-s>>1);
            pushdown(s, t, p);
            if (l <= mid) upd(l, r, s, mid, p<<1, c);
            if (mid+1 <= r) upd(l, r, mid+1, t, p<<1|1, c);
            d[p] = max(d[p<<1], d[p<<1|1]);
        }
        return ;
    }
    void add (int l, int r, int s, int t, int p, ll c) {
        if (l<=s && t<=r) {
            d[p] += c;
            b[p] += c;
        } else {
            int mid = s+(t-s>>1);
            pushdown(s, t, p);
            if (l <= mid) add(l, r, s, mid, p<<1, c);
            if (mid+1 <= r) add(l, r, mid+1, t, p<<1|1, c);
            d[p] = max(d[p<<1], d[p<<1|1]);
        }
        return ;
    }
    int ges (int l, int r, int s, int t, int p) {
        pushdown(s, t, p);
        if (l<=s && t<=r) return d[p];
        else {
            int mid = s+(t-s>>1), res = -rec;
            if (l <= mid) res = max(res, ges(l, r, s, mid, p<<1));
            if (mid+1 <= r) res = max(res, ges(l, r, mid+1, t, p<<1|1));
            return res;
        }
    }
} S;

int n, m;
int main () {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
        freopen("test.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%d", S.a+i);
    S.build(1, n, 1);
    for (int f, l, r, c, i = 1; i <= m; ++ i) {
        scanf("%d%d%d", &f, &l, &r);
        if (f == 1) {
            scanf("%d", &c);
            S.upd(l, r, 1, n, 1, c);
        } else if (f == 2) {
            scanf("%d", &c);
            S.add(l, r, 1, n, 1, c);
        } else printf("%d\n", S.ges(l, r, 1, n, 1));
    }
    return 0;
}

by GOD_hj @ 2022-08-01 18:26:34

orz

by jijidawang @ 2022-08-01 19:55:03

@SMTwy

by SMTwy @ 2022-08-01 19:56:05

@jijidawang 调不了

by wkh2008 @ 2022-08-01 20:37:47

orz

by STA_Morlin @ 2022-08-02 08:18:05

改：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll man = 1e6+10, rec = 2e9+10;
struct SMT {
    ll a[man], d[man<<2], b[man<<2], e[man<<2];
    void build (int s, int t, int p) {
        e[p] = rec;
        if (s == t) d[p] = a[s];
        else {
            int mid = s+(t-s>>1);
            build(s, mid, p<<1);
            build(mid+1, t, (p<<1)|1);
            d[p] = max(d[p<<1], d[p<<1|1]);
        }
        return ;
    }
    void pushdown (int p) {
        int l = p<<1, r = p<<1|1;
        if (e[p] != rec) {
            d[l] = e[l] = e[p];
            d[r] = e[r] = e[p];
            b[l] = b[r] = 0;
            e[p] = rec;
        }
        b[l] += b[p];
        b[r] += b[p];
        d[l] += b[p];
        d[r] += b[p];
        b[p] = 0;
        return ;
    }
    void upd (int l, int r, int s, int t, int p, ll c) {
        if (l<=s && t<=r) {
            d[p] = e[p] = c;
            b[p] = 0;
        } else {
            int mid = s+(t-s>>1);
            pushdown(p);
            if (l <= mid) upd(l, r, s, mid, p<<1, c);
            if (mid+1 <= r) upd(l, r, mid+1, t, p<<1|1, c);
            d[p] = max(d[p<<1], d[p<<1|1]);
        }
        return ;
    }
    void add (int l, int r, int s, int t, int p, ll c) {
        if (l<=s && t<=r) {
            d[p] += c;
            b[p] += c;
        } else {
            int mid = s+(t-s>>1);
            pushdown(p);
            if (l <= mid) add(l, r, s, mid, p<<1, c);
            if (mid+1 <= r) add(l, r, mid+1, t, p<<1|1, c);
            d[p] = max(d[p<<1], d[p<<1|1]);
        }
        return ;
    }
    ll ges (int l, int r, int s, int t, int p) {
        pushdown(p);
        if (l<=s && t<=r) return d[p];
        else {
            ll mid = s+(t-s>>1), res = -rec;
            if (l <= mid) res = max(res, ges(l, r, s, mid, p<<1));
            if (mid+1 <= r) res = max(res, ges(l, r, mid+1, t, p<<1|1));
            return res;
        }
    }
} S;

int n, m;
int main () {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
        freopen("test.out", "w", stdout);
    #endif
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++ i) scanf("%lld", S.a+i);
    S.build(1, n, 1);
    for (int f, l, r, i = 1; i <= m; ++ i) {
        scanf("%d%d%d", &f, &l, &r);
        if (f == 1) {
            ll c;
            scanf("%lld", &c);
            S.upd(l, r, 1, n, 1, c);
        } else if (f == 2) {
            ll c;
            scanf("%lld", &c);
            S.add(l, r, 1, n, 1, c);
        } else printf("%lld\n", S.ges(l, r, 1, n, 1));
    }
    return 0;
}

by Broken_Eclipse @ 2022-08-02 09:59:32

你的rec(inf)应该调得更大一些。 @STA_Morlin

by STA_Morlin @ 2022-08-02 10:15:46

@Broken_Eclipse 谢谢谢（话说为什么4倍n不可以啊

by Broken_Eclipse @ 2022-08-02 10:25:08

@STA_Morlin 不太清楚，但你这份代码开5倍n就能过了

by STA_Morlin @ 2022-08-02 10:30:05

@Broken_Eclipse OK，谢谢谢