TLE求调

cyj20080401 @ 2024-12-14 13:50:04

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
const ll INF = 1e18;
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
struct SegmentTree {
    vll maxx, setv, addv;
    int n;

    bool in(int l, int r, int x, int y) {
        return l >= x && r <= y;
    }

    bool out(int l, int r, int x, int y) {
        return l > y || r < x;
    }

    void pushup(int u) {
        maxx[u] = max(maxx[u << 1], maxx[(u << 1) | 1]);
    }

    void maketag(int u, int type, ll x) {
        if (type == 1) {
            maxx[u] = x;
            setv[u] = x;
            addv[u] = 0;
        }
        else {
            if (setv[u] == INF) {
                maxx[u] += x;
                addv[u] += x;
            }
            else {
                setv[u] += x;
                maxx[u] = setv[u];
            }
        }
    }

    void pushdown(int node) {
        if (setv[node]!= INF) {
            maketag(node << 1, 1, setv[node]);
            maketag((node << 1) | 1, 1, setv[node]);
            setv[node] = INF;
        }
        if (addv[node]) {
            maketag(node << 1, 2, addv[node]);
            maketag((node << 1) | 1, 2, addv[node]);
            addv[node] = 0;
        }
    }

    void update(int u, int l, int r, int x, int y, int type, ll val) {
        if (in(l, r, x, y)) {
            maketag(u, type, val);
            return;
        }
        pushdown(u);
        int mid = (l + r) >> 1;
        if (!out(l, mid, x, y)) update(u << 1, l, mid, x, y, type, val);
        if (!out(mid + 1, r, x, y)) update((u << 1) | 1, mid + 1, r, x, y, type, val);
        pushup(u);
    }

    ll query(int u, int l, int r, int x, int y) {
        if (in(l, r, x, y)) return maxx[u];
        if (out(l, r, x, y)) return -INF;
        pushdown(u);
        int mid = (l + r) >> 1;
        return max(query(u << 1, l, mid, x, y), query((u << 1) | 1, mid + 1, r, x, y));
    }

    void build(vll arr, int u, int l, int r) {
        if (l == r) {
            maxx[u] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(arr, u << 1, l, mid);
        build(arr, (u << 1) | 1, mid + 1, r);
        pushup(u);
    }

    SegmentTree(vll arr, int m) : n(m) {
        maxx.resize(4 * m);
        setv.resize(4 * m);
        addv.resize(4 * m);
        build(arr, 1, 1, n);
        fill(setv.begin(), setv.end(), INF);
    }
};

int main() {
    int n = read(), q = read();
    vll arr(n + 1);
    for (int i = 1; i <= n; ++i)
        arr[i] = read();
    SegmentTree tree(arr, n);
    int op, l, r;
    ll x;
    while (q--) {
        op = read();
        l = read();
        r = read();
        if (op == 3)
            printf("%lld\n", tree.query(1, 1, n, l, r));
        else {
            x = read();
            tree.update(1, 1, n, l, r, op, x);
        }
    }
    return 0;
}

by MinLand @ 2024-12-15 10:09:25

事实证明不要滥用vector,我把改了一下，运行的时候注意更改栈空间，不然无法运行。

#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
const ll INF = 1e18;
inline ll read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
const ll N=1e6+114;
struct SegmentTree {
    // vll maxx, setv, addv;
    ll maxx[N*4],setv[N*4],addv[N*4];
    ll n;

    bool in(int l, int r, int x, int y) {
        return l >= x && r <= y;
    }

    bool out(int l, int r, int x, int y) {
        return l > y || r < x;
    }

    void pushup(int u) {
        maxx[u] = max(maxx[u << 1], maxx[(u << 1) | 1]);
    }

    void maketag(int u, int type, ll x) {
        if (type == 1) {
            maxx[u] = x;
            setv[u] = x;
            addv[u] = 0;
        }
        else {
            if (setv[u] == INF) {
                maxx[u] += x;
                addv[u] += x;
            }
            else {
                setv[u] += x;
                maxx[u] = setv[u];
            }
        }
    }

    void pushdown(int node) {
        if (setv[node]!= INF) {
            maketag(node << 1, 1, setv[node]);
            maketag((node << 1) | 1, 1, setv[node]);
            setv[node] = INF;
        }
        if (addv[node]) {
            maketag(node << 1, 2, addv[node]);
            maketag((node << 1) | 1, 2, addv[node]);
            addv[node] = 0;
        }
    }

    void update(int u, int l, int r, int x, int y, int type, ll val) {
        if (in(l, r, x, y)) {
            maketag(u, type, val);
            return;
        }
        pushdown(u);
        int mid = (l + r) >> 1;
        if (!out(l, mid, x, y)) update(u << 1, l, mid, x, y, type, val);
        if (!out(mid + 1, r, x, y)) update((u << 1) | 1, mid + 1, r, x, y, type, val);
        pushup(u);
    }

    ll query(int u, int l, int r, int x, int y) {
        if (in(l, r, x, y)) return maxx[u];
        if (out(l, r, x, y)) return -INF;
        pushdown(u);
        int mid = (l + r) >> 1;
        return max(query(u << 1, l, mid, x, y), query((u << 1) | 1, mid + 1, r, x, y));
    }

    void build(ll *arr, int u, int l, int r) {
        if (l == r) {
            maxx[u] = arr[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(arr, u << 1, l, mid);
        build(arr, (u << 1) | 1, mid + 1, r);
        pushup(u);
    }

    SegmentTree(ll * arr, int m) : n(m) {
        // maxx.resize(4 * m);
        // setv.resize(4 * m);
        // addv.resize(4 * m);
        build(arr, 1, 1, n);
        for(int i=1;i<=4*n;i++) 
            setv[i]=INF;
        // fill(setv.begin(), setv.end(), INF);
    }
};

ll arr[N];
int n=0,q=0;
int main() {
    //  n = read(), q = read();
     cin>>n>>q;
    // vll arr(n + 1);
    // cin>>n>>q;
    for (int i = 1; i <= n; ++i)
        // arr[i] = read();
        cin>>arr[i];
    SegmentTree tree(arr, n);
    int op, l, r;
    ll x;
    while (q--) {
        op = read();
        l = read();
        r = read();
        if (op == 3)
            printf("%lld\n", tree.query(1, 1, n, l, r));
        else {
            x = read();
            tree.update(1, 1, n, l, r, op, x);
        }
    }
    return 0;
}

by MinLand @ 2024-12-15 10:09:58

看看，这个cin都过了，那改成快读，应该会更快