Consigli su ottimizzazione per panama sum

Olimpiadi
1

Con questo codice si riesce a fare 100/100 senza problemi arrivando ad un massimo di 400ms, ma noto persone con codici molto piu’ efficenti ed essendo questo uno dei miei primi problemi con un segment tree volevo chiedervi, ci sono modi piu’ efficenti di farlo? O implementare piu’ efficentemente questo tipo di query?

#include <iostream>
#include <vector>
using namespace std;

struct max_item {
    long long seg, pref, suf, sum;
};

struct segtree {
    int size;
    vector<max_item> max_seg_even;
    vector<max_item> max_seg_odd;
    max_item MAX_NEUTRAL = {0, 0, 0, 0};

    void init(int n) {
        size = 1;
        while(size < n) size *= 2;
        max_seg_even.resize(2 * size);
        max_seg_odd.resize(2 * size);
    }

    void build(vector<int> &V, vector<max_item> &max_seg, int nodo, int lx, int rx) {
        if(rx - lx == 1) {
            if(lx < V.size()) {
                max_seg[nodo] = max_single(V[lx]);
            }
            return;
        }

        int middle = (lx + rx) / 2;
        build(V, max_seg, 2 * nodo + 1, lx, middle);
        build(V, max_seg, 2 * nodo + 2, middle, rx);
        max_seg[nodo] = max_merge(max_seg[2 * nodo + 1], max_seg[2 * nodo + 2]);
    }

    void build(vector<int> &V, vector<max_item> &max_seg) {
        build(V, max_seg, 0, 0, size);
    }

    max_item max_merge(max_item a, max_item b) {
        return {
            max(a.seg, max(b.seg, a.suf + b.pref)),
            max(a.pref, a.sum + b.pref),
            max(b.suf, b.sum + a.suf),
            a.sum + b.sum
        };
    }

    max_item max_single(int v) {
        if(v > 0)
            return {v, v, v, v};
        return {0, 0, 0, v};
    }

    void set_even(int i, int v, int nodo, int lx, int rx) {
        if(rx - lx == 1) {
            max_seg_even[nodo] = max_single(v);
            return;
        }

        int middle = (lx + rx) / 2;
        if(i < middle) {
            set_even(i, v, 2 * nodo + 1, lx, middle);
        } else {
            set_even(i, v, 2 * nodo + 2, middle, rx);
        }

        max_seg_even[nodo] = max_merge(max_seg_even[2 * nodo + 1], max_seg_even[2 * nodo + 2]);
    }

    void set_even(int i, int v) {
        set_even(i, v, 0, 0, size);
    }

    void set_odd(int i, int v, int nodo, int lx, int rx) {
        if(rx - lx == 1) {
            max_seg_odd[nodo] = max_single(v);
            return;
        }

        int middle = (lx + rx) / 2;
        if(i < middle) {
            set_odd(i, v, 2 * nodo + 1, lx, middle);
        } else {
            set_odd(i, v, 2 * nodo + 2, middle, rx);
        }

        max_seg_odd[nodo] = max_merge(max_seg_odd[2 * nodo + 1], max_seg_odd[2 * nodo + 2]);
    }

    void set_odd(int i, int v) {
        set_odd(i, v, 0, 0, size);
    }

    max_item max_segment_even(int l, int r, int nodo, int lx, int rx) {
        if(lx >= r || l >= rx) return MAX_NEUTRAL;
        if(lx >= l && rx <= r) return max_seg_even[nodo];
        int middle = (lx + rx) / 2;

        max_item sinistra = max_segment_even(l, r, 2 * nodo + 1, lx, middle);
        max_item destra = max_segment_even(l, r, 2 * nodo + 2, middle, rx);
        return max_merge(sinistra, destra);
    }

    max_item max_segment_even(int l, int r) {
        return max_segment_even(l, r, 0, 0, size);
    }

    max_item max_segment_odd(int l, int r, int nodo, int lx, int rx) {
        if(lx >= r || l >= rx) return MAX_NEUTRAL;
        if(lx >= l && rx <= r) return max_seg_odd[nodo];
        int middle = (lx + rx) / 2;

        max_item sinistra = max_segment_odd(l, r, 2 * nodo + 1, lx, middle);
        max_item destra = max_segment_odd(l, r, 2 * nodo + 2, middle, rx);
        return max_merge(sinistra, destra);
    }

    max_item max_segment_odd(int l, int r) {
        return max_segment_odd(l, r, 0, 0, size);
    }
};

int main() {
    int N, q;
    cin>>N>>q;

    segtree st;
    st.init(N);

    vector<int> V(N);
    vector<int> V1(N);
    for(int i = 0; i < N; ++i) {
        int x;
        cin >> x;
        if(i % 2 == 1) {V[i] = -x; V1[i] = x;}
        else {V[i] = x; V1[i] = -x;}
    }

    st.build(V, st.max_seg_even);
    st.build(V1, st.max_seg_odd);

    // 5 9 1 2 8 4 6 4 2 8

    while(q--) {
        int op;
        cin>>op;
        if(op == 1) {
            int i, v;
            cin>>i>>v;
            --i;
            if(i % 2 == 1) v = -v;
            st.set_even(i, v);
            st.set_odd(i, -v);
        } else {
            int l, r;
            cin>>l>>r;
            --l;
            cout << max(st.max_segment_odd(l, r).seg, st.max_segment_even(l, r).seg) << '\n';
        }
    }
    return 0;
}
2

Quando si parla di alberi segmentati l’implementazione può fare molta differenza. In particolare un’implementazione iterativa (e non ricorsiva) è notevolmente più veloce (anche se meno potente).
Ci sono dei problemi in cui il time limit è molto stretto e l’implementazione ricorsiva non passa, ma sono casi abbastanza rari.
Io personalmente preferisco ove possibile scriverli ricorsivi (e con i puntatori) anche se sono più lenti perché di solito non dà problemi ed è più facile adattarli a varianti più potenti (lazy, persistenti, sparsi etc.)

1 Mi Piace
3

te hai consigli o problemi carini da fare sui segment tree? ne ho fatti alcuni su codeforces ma molto precisi che spiegavano esattamente che operazioni fare, non problemi generali su cui dici, ok qui forse si potrebbe fare con un segment tree

4

Qui su training sono carini e abbastanza facili ois_scmax e preegoi_parkour. Un segment semplice ma con idee carine dietro è di sicuro tai_sfere. Con applicazioni un po’ più particolari ci sono ois_forum e ois_fossils. Con segment più avanzati ci sono tai_hasta, figurines e iiot_ktree. Infine ois_police7 è abbastanza difficile ma molto bello.

5

grazie :heart:

6

Sono bloccato su scmax, puoi hint?

7
Hint 1

Il problema è molto chiaramente una dp.

Hint 2

Risolvi il problema per tutti i suffissi.

Hint 3

Con un segment puoi ottimizzare le transizioni da O(N) a O(log max P) = O(log N)

2 Mi Piace
8

sfere e’ molto carino, anche se l’idea l’avevo gia’ vista.