SPOJ - Największa różnica

Question

Cześć, problem dotyczy zadania Największa różnica: https://pl.spoj.com/problems/LIKEHELL/

Mianowicie wynik z jakiegoś powodu wychodzi zły, a ja nie mogę namierzyć błędu. Załączam kod i mam nadzieję, że ktoś mądrzejszy wytłumaczy o co chodzi.

#include <iostream>
#include <algorithm>

using namespace std;

const int M = 1 << 21;
const int leaf = 1 << 20;

int tree_min[M + 5];
int tree_max[M + 5];

void dodaj(int a, int x){
    a += leaf;
    
    while(a /= 2){
        if(tree_min[a] == 0) tree_min[a] = M;
        tree_min[a] = min(tree_min[a], x);
        tree_max[a] = max(tree_max[a], x);
    }
}

int roznica(int a){
    int ans = 0;
    a += leaf;
    
    while(a /= 2){
         ans = max(ans, tree_max[(a*2)+1]-tree_min[a]);
    }
    return ans;
}

void zmien(int p, int v){
    p += leaf;
    tree_min[p]=v;
    tree_max[p]=v;

    while(p){
        p/=2;
        if(tree_min[(p*2)+1] == 0) tree_min[(p*2)+1] = M;
        if(tree_min[(p*2)] == 0) tree_min[(p*2)] = M;
        tree_min[p] = min(tree_min[p*2], tree_min[(p*2)+1]);
        tree_max[p] = max(tree_max[p*2], tree_max[(p*2)+1]);
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    for(int i=1; i<=n; i++){
        int x;
        cin >> x;
        dodaj(i, x);
    }
    
    for(int i=0; i<q; i++){
        string z;
        cin >> z;
        if(z == "q")
            cout << roznica(1) <<"\n";
        else if(z == "u"){
            int p, v;
            cin >> p >> v;
            zmien(p, v);
        }
    }    
        
    return 0;
}

 

Answer 1

Pomysł masz w większości dobry, ale problem pojawia się w funkcji roznica. To co tam napisałeś nie będzie działać. Żeby rozwiązać to zadanie wystarczy dodać jeszcze jedną tablicę, powiedzy res, która trzyma największą różnicę między dwiema wartościami należącymi do danego poddrzewa. Gdy chcesz odpowiedzieć na zapytanie o największą różnicę dla wszystkich liczb wystarczy, że wypiszesz res[1], bo wierzchołek nr 1 obejmuje całą tablicę. I teraz tablicę res będziemy konstruować w funkcji zmien. Oczywiście res[liść] = 0. Zastanówmy się jak może wyglądać różnica której szukamy, jeżeli jesteśmy w wierzchołku nr v, który nie jest liściem, to oba elementy różnicy mogą należeć albo do lewego poddrzewa, albo do prawego, albo jeden element leży w lewym poddrzewie, a drugi w prawym. Jeżeli oba elementy należą do któregoś z poddrzew to zauważmy, że wyniki dla poddrzew mamy już obliczone, czyli bierzemy max(res[2*v], res[2*v+1]). Jeżeli mniejszy element jest w lewym poddrzewie, a większy w prawy, to bierzemy tree_max[2*v+1] - tree_max[2*v]. No i nie będzie sytuacji, w której mniejszy element jest w prawym poddrzwie, a większy w lewym, bo to by było bez sensu.

Przerobiony kod wygląda tak:

#include <iostream>
#include <algorithm>

using namespace std;

const int M = 1 << 21;
const int leaf = 1 << 20;
const int INF = 1e9 + 7;

int tree_min[M + 5];
int tree_max[M + 5];
int res[M + 5];

void zmien(int p, int v) {
    p += leaf;
    tree_min[p] = v;
    tree_max[p] = v;
    res[p] = 0;

    while (p) {
        p /= 2;
        if (tree_min[(p * 2) + 1] == 0) tree_min[(p * 2) + 1] = INF;
        if (tree_min[(p * 2)] == 0) tree_min[(p * 2)] = INF;
        tree_min[p] = min(tree_min[p * 2], tree_min[(p * 2) + 1]);
        tree_max[p] = max(tree_max[p * 2], tree_max[(p * 2) + 1]);

        res[p] = max({ res[2 * p], res[2 * p + 1], tree_max[2 * p + 1] - tree_min[2 * p] });
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        zmien(i, x);
    }

    for (int i = 0; i < q; i++) {
        string z;
        cin >> z;
        if (z == "q")
            cout << res[1] << "\n";
        else if (z == "u") {
            int p, v;
            cin >> p >> v;
            zmien(p, v);
        }
    }

    return 0;
}

Usunąłem funkcję dodaj, bo tak naprawdę można ją zastąpić funkcją zmien. Dodatkowo robiłeś taki błąd, że tablicę tree_min wypełniałeś na początku wartością M, czyli coś koło 2 milionów, a największy element w tablicy to mógł być miliard. I wtedy mogło wyjść tak, że masz tablicę wypełnioną tylko miliardami, a Twój program stwierdzi, że i tak najmniejsza wartość to 1<<21. To też poprawiłem.