36ος ΠΔΠ Α' Φάση: Το σπίτι στον ελαιώνα (olivetrees) - Λύση

Συγγραφέας: Μποκής Κωνσταντίνος

Επεξήγηση εκφώνησης

Δίνεται ένας πίνακας με \(M\) στήλες και \(N\) γραμμές. Κάθε στήλη \(i\) έχει \(Z_i\) κατειλημμένα κελιά στη βάση της και ακολουθούν τα \(N-Z_i\) κενά κελιά στην κορυφή της. Ζητείται να υπολογιστεί το εμβαδό του μεγαλύτερου ορθογωνίου παραλληλογράμμου που σχηματίζεται αποκλειστικά από κενά κελιά.

Στο πρόβλημα αυτό χρειάζεται να γνωρίζουμε μόνο το πλήθος των κενών κελιών σε κάθε στήλη \(i\), το οποίο το ονομάζουμε ύψος και το συμβολίζουμε με \(H_i\). Ξεκινάμε με την εξής βασική παρατήρηση:

Παρατήρηση 1 Στο μέγιστο ορθογώνιο παραλληλόγραμμο που ξεκινάει από την στήλη \(i\) και τελειώνει στην στήλη \(j\), η άνω του πλευρά (με πλάτος \(j-i+1\)) ταυτίζεται με την άνω πλευρά του πίνακα και το ύψος του είναι η ελάχιστη από τις τιμές \(H_i, H_{i+1}, \ldots, H_j\).

Στην συνέχεια θα παρουσιάσουμε μια λύση brute force, δηλαδή εξαντλητικής διερεύνησης με πολυπλοκότητα \(\mathcal{O}(M^3)\) και μια βελτιωμένη με πολυπλοκότητα \(\mathcal{O}(M^2)\). Θα ακολουθήσει η βέλτιστη λύση με πολυπλοκότητα \(\mathcal{O}(M)\). Τέλος θα παρουσιαστούν τρεις ακόμα υποβέλτιστες λύσεις που βασίζονται σε πιό σύνθετες τεχνικές, τεχνικές οι οποίες είναι γενικά χρήσιμες για την επίλυση προβλημάτων, δεν είναι όμως απαραίτητο να τις γνωρίζει κάποιος για την Α’ φάση του διαγωνισμού. Οι λύσεις αυτές είναι άμεσες βελτιώσεις της brute force λύσης. Η πρώτη έχει πολυπλοκότητα \(\mathcal{O}(M \cdot \sqrt{M})\), η δεύτερη \(\mathcal{O}(M\cdot \log^2{M})\) και η τελευταία \(\mathcal{O}(M\cdot \log{M})\).

Λύση με brute force - \(\mathcal{O}(M^3)\)

Δοκιμάζουμε όλα τα δυνατά άκρα \(i\) και \(j\) και υπολογίζουμε το εμβαδό του μέγιστου ορθογωνίου παραλληλογράμμου που σχηματίζεται. Χρησιμοποιούνται δυο for για να δώσουν όλους τους δυνατούς συνδυασμούς τιμών για τα \(i\) και \(j\).
Το ύψος του ορθογωνίου παραλληλογράμμου είναι το ελάχιστο ύψος όλων των στηλών από \(i\) έως και \(j\) και το εσωτερικό for φροντίζει να το βρει. Στο 1^o παράδειγμα της εκφώνησης για το συνδυασμό \(i=1\) και \(j=4\), το ύψος του ορθογωνίου παραλληλογράμμου καθορίζεται από την στήλη \(2\) (που έχει το χαμηλότερο ύψος) και το πλάτος από τα \(i,j\).

Υπάρχουν \(M \cdot (M-1)\) συνολικοί συνδυασμοί για τα \(i\) και \(j\) και η αναζήτηση του ελάχιστου ύψους χρειάζεται χρόνο \(\mathcal{O}(M)\). Άρα συνολικά η λύση χρειάζεται \(\mathcal{O}(M^3)\) χρόνο.

#include <cstdio>
#include <algorithm>
#include <vector>

long ans,N,M;
std::vector<long> H;

int main(){
    FILE *in = fopen("olivetrees.in","r");
    fscanf(in,"%ld%ld",&N,&M);
    H.resize(M);
    for(long i=0;i<M;i++){
        fscanf(in,"%ld",&H[i]);
        H[i] = N - H[i];
    }
    fclose(in);

    for(long i=0;i<M;i++){
        for(long j=i;j<M;j++){
            long min_height=H[i];//βρες το ελάχιστο ύψος από i εως και j
            for(long k=i+1;k<=j;k++)
                min_height = std::min(min_height,H[k]);
            ans = std::max(ans, (j-i+1) * min_height);
        }
    }

    FILE *out = fopen("olivetrees.out","w");
    fprintf(out,"%ld\n",ans);
    fclose(out);
    return 0;
}

Λύση με brute force - \(\mathcal{O}(M^2)\)

Στον παραπάνω κώδικα το εξωτερικό for καθορίζει το \(i\) και το ενδιάμεσο το \(j\). Είναι προφανές ότι \(\min{\{H_i, \ldots, H_{j+1}\}} = \min\left( \min{ \{H_i, \ldots, H_j \} }, H_{j+1} \right)\) άρα όταν έχουμε το ελάχιστο ύψος στο διάστημα \([i,j]\) μπορούμε με μία και μόνο επιπλέον σύγκριση να βρούμε το ελάχιστο ύψος στο διάστημα \([i,j+1]\) καταργώντας το τρίτο for. Έτσι, ο χρόνος εκτέλεσης βελτιώνεται σε \(\mathcal{O}(M^2)\).

    for(long i=0;i<M;i++){
        long min_height=H[i];//ελάχιστο ύψος από i έως και j
        for(long j=i;j<M;j++){
            min_height = std::min(min_height,H[j]);
            ans = std::max(ans, (j-i+1) * min_height);
        }
    }

Οι παραπάνω λύσεις “δοκιμάζουν” τα δυνατά άκρα του ορθογωνίου παραλληλογράμμου και έπειτα υπολογίζουν το ύψος του. Εναλλακτικά, μπορούμε για κάθε στήλη \(i\), να αναζητήσουμε τα άκρα του ορθογωνίου παραλληλογράμμου με ύψος \(H_i\) που την περιέχει. Αυτό το κάνουμε ολισθαίνοντας δυο δείκτες \(\texttt{left}, \texttt{right}\) αριστερά και δεξιά του \(i\) όσο βρίσκουμε “συμβατές” στήλες με τη \(i\), δηλαδή στήλες που έχουν ύψος τουλάχιστον \(H_i\). Για κάθε μία από τις \(M\) στήλες θα ολισθήσουμε τους δύο δείκτες το πολύ \(M-1\) φορές. Άρα και η λύση αυτή χρειάζεται \(\mathcal{O}(M^2)\) χρόνο.

    for(long i=0;i<M;i++){
        long left = i, right = i;
        while(left-1>=0 && H[i]<=H[left-1]) left--;
        while(right+1<M && H[i]<=H[right+1]) right++;
        ans = std::max(ans, (right-left+1) * H[i]);
    }

Δείτε ολόκληρο τον κώδικα εδώ.

Βέλτιστη λύση με μονότονη στοίβα (monotonic stack) - \(\mathcal{O}(M)\)

Τώρα, θα επιταχύνουμε τον υπολογισμό των \(\texttt{left}\) και \(\texttt{right}\) για κάθε \(i\). Ξεκινάμε με τις εξής χρήσιμες παρατηρήσεις:

Παρατήρηση 2 Κάθε στήλη \(i\) με ύψος \(H_i\) είναι χρήσιμη και επεκτείνεται προς τα δεξιά, όσο την ακολουθούν στήλες με ύψος τουλάχιστον \(H_i\).

Η πρώτη στήλη \(j\) με \(j\gt i\) και \(H_j \lt H_i\) λέμε ότι καταργεί την \(i\). Δείτε στο παρακάτω παράδειγμα (σχήμα 1) τα ύψη \(1,4,5\) που ανήκουν στς στήλες \(1,2,3\) αντίστοιχα. Κάθε ένα από αυτά τα ύψη, επεκτείνεται προς τα δεξιά καθώς οι δεξιότερες στήλες το ξεπερνούν σε ύψος. Καθώς έρχεται η σειρά της στήλης \(4\) με ύψος \(2\) να εξεταστεί, το ύψος \(2\) είναι χαμηλότερο από τα ύψη \(4\) και \(5\). Το ύψος \(2\) θα καταργήσει το ύψος \(5\) (το οποίο επεκτάθηκε μόνο στη στήλη \(3\) δίνοντας εμβαδό \(5\cdot 1\)) (σχήμα 2). Το ύψος \(2\) στη συνέχεια καταργεί και το ύψος \(4\) (το οποίο επεκτάθηκε έως τη στήλη \(3\) δίνοντας εμβαδό \(4 \cdot 2\)) (σχήμα 3).

Παρατήρηση 3 Κάθε στήλη με ύψος \(H_j\) που κατάργησε κάποια αριστερότερη στήλη μεγαλύτερου ύψους \(H_i\), επεκτείνεται αριστερά μέχρι το σημείο που επεκτεινόταν το ύψος \(H_i\). Δείτε στο ακόλουθο σχήμα, πως το ύψος \(2\) κατάργησε δύο μεγαλύτερα ύψη και επεκτείνεται αριστερότερα καλύπτωντας τις στήλες που κατάργησε (σχήμα 4).

Η μεθοδολογία που ακολουθεί η λύση είναι η εξής:

Διατρέχουμε τις στήλες από αριστερά προς τα δεξιά κρατώντας σε μια στοίβα (stack) τα ενεργά ύψη. Ως ενεργά ονομάζουμε τα ύψη με προοπτική να επεκταθούν δεξιότερα. Μόλις εμφανιστεί ένα μικρότερο ύψος \(H_j\) από αυτό που υπάρχει στην κορυφή της στοίβας, καταργούμε όσα μεγαλύτερα ύψη βρίσκονται ήδη στην κορυφή της στίβας διότι δεν επεκτείνονται άλλο. Το ύψος \(H_j\) επεκτείνεται αριστερά καταλαμβάνοντας όλες τις στήλες που κατάργησε. Κάθε ύψος \(H_j\) εισάγεται στη στοίβα μια φορά και κατά την εισαγωγή του υπολογίζεται η αριστερή ακμή του ορθογώνιου παραλληλογράμμου. Κάθε ύψος \(H_i\) που καταργείται από κάποιο μικρότερο \(H_j\) (\(j\gt i\)) κατάφερε να επεκταθεί έως τη στήλη \(j-1\) οπότε υπολογίζουμε το εμβαδό του πριν το αφαιρέσουμε από τη στοίβα. Με τη μέθοδο αυτή καταλήγουμε να έχουμε μια μονότονη (αύξoυσα στην περίπτωση μας) διάταξη των υψών στη στοίβα, γι’αυτό και η ονομασία μονότονη στοίβα (monotonic stack).

Ας δούμε την εκτέλεση του αλγορίθμου για το 1^o παράδειγμα της εκφώνησης.

	olivetrees
Θέση στήλης Ύψος στήλης	1 2 3 4 5 6 7 2 1 4 5 1 3 3

Διαβάζουμε το ύψος \(2\) που ξεκινά από τη στήλη \(1\) και το βάζουμε στη στοίβα (σχήμα 1).
Διαβάζουμε το ύψος \(1\) και καθώς είναι μικρότερο από το ύψος \(2\) στην κορυφή της στοίβας, το \(2\) δεν μπορεί να επεκταθεί άλλο. Το εμβαδό που σχημάτισε το ύψος \(2\) είναι \(2\times 1\) καθώς επεκτάθηκε σε μια μόνο στήλη. Τώρα μπορούμε να προσθέσουμε το ύψος \(1\) στη στοίβα. Το ύψος \(1\) ξεκινά από τη στήλη \(1\) (παρόλο που το βρήκαμε στη στήλη \(2\) στο αρχείο εισόδου) καθότι είναι μικρότερο από το ύψος \(2\) που πετάξαμε και μπορεί να επεκταθεί μέχρι τη στήλη που ξεκινούσε το ύψος \(2\) (σχήμα 2).
Διαβάζουμε το ύψος \(4\) (ξεκινά από τη στήλη \(3\)) και το προσθέτουμε στη στοίβα (σχήμα 3).
Διαβάζουμε το ύψος \(5\) (ξεκινά από τη στήλη \(4\)) και το προσθέτουμε στη στοίβα (σχήμα 4).
Διαβάζουμε το ύψος \(1\) (της στήλης \(5\)) και καθώς είναι μικρότερο από το \(5\) που βρίσκεται στην κορυφή της στοίβας, θα το διαγράψει. Το \(5\) κατάφερε να καλύψει εμβαδό \(5\times 1\). Κατόπιν παρατηρούμε ότι στην κορυφή της στοίβας υπάρχει το \(4\) που και αυτό θα διαγραφεί. Το εμβαδό που πέτυχε είναι \(4 \times 2\) εφόσον επεκτάθηκε έως την \(4\) στήλη. Τώρα στη στοίβα υπάρχει το ύψος \(1\) που είναι ίσο με το τωρινό μας ύψος. Δεν χρειάζεται πλέον και θα αντικατασταθεί από το τωρινό \(1\) (σχήμα 5).
Διαβάζουμε το ύψος \(3\) (ξεκινά στη στήλη \(6\)) και το βάζουμε στη στοίβα (σχήμα 6).
Διαβάζουμε το ύψος \(3\) (ξεκινά στη στήλη \(7\)). Το προηγούμενο ύψος \(3\) δεν χρειάζεται πλέον καθώς θα αντικατασταθεί από το τωρινό ύψος \(3\) (σχήμα 7).

Εξαντλήθηκαν οι στήλες μας αλλά έχουν μείνει στη στοίβα κάποια ύψη. Τα ύψη αυτά “επέζησαν” έως και τη στήλη \(M\) (\(7\) στο παράδειγμα μας) άρα υπολογίζουμε το εμβαδό καθενός από αυτά πριν το διαγράψουμε από τη στοίβα.

Κάθε μία από τις \(M\) στήλες, θα εισαχθεί μία φορά στη στοίβα και θα αφαιρεθεί μία φορά. Άρα η λύση με τη μονότονη στοίβα χρειάζεται χρόνο \(\mathcal{O}(M)\).

#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>

long ans,N,M;
struct rect {
    long height;//ύψος height
    long left;//αριστερή ακμή του ορθογωνίου 
    rect(long height,long left):height(height),left(left){}
};

int main(){
    FILE *in = fopen("olivetrees.in","r");
    fscanf(in,"%ld%ld",&N,&M);
    std::stack<rect> S;
    for(long h,i=0;i<M;i++){
        fscanf(in,"%ld",&h);
        h = N - h;
        rect p(h,i);//το ύψος h ξεκινά στη στήλη i
        //αφαίρεσε τα μεγαλύτερα ύψη της στοίβας (αν υπάρχουν)
        while(!S.empty() && S.top().height>=h){
            //υπολόγισε εμβαδό ορθογωνίου που καταργείται
            ans = std::max(ans, (i-S.top().left)*S.top().height);
            p.left = S.top().left;//το ύψος h ξεκινά από τη θέση του ύψους που κατήργησε
            S.pop();
        }
        S.push(p);
    }
    fclose(in);

    //αφαίρεσε από τη στοίβα όσα ορθογώνια φτάνουν μέχρι το δεξιό άκρο M-1
    while(!S.empty()){
        //υπολόγισε εμβαδό ορθογωνίου που καταργείται
        ans = std::max(ans,(M-S.top().left)*S.top().height);
        S.pop();
    }
    FILE *out = fopen("olivetrees.out","w");
    fprintf(out,"%ld\n",ans);
    fclose(out);
    return 0;
}

Λύση με sqrt decomposition - \(\mathcal{O}(M \cdot \sqrt{M})\)

Η ακόλουθη λύση βασίζεται στην τεχνική sqrt-decomposition και δεν έχει προαπαιτούμενες γνώσεις για να διαβαστεί. Αν θέλετε να μάθετε παραπάνω δείτε εδώ και εδώ.

Το μειονέκτημα της brute force λύσης είναι ότι εξετάζουμε πολλές φορές ένα ένα τα ύψη των γειτονικών στηλών καθώς ολισθαίνουμε τους δύο δείκτες μας για να βρούμε όλες τις στήλες \(j\) με \(H_j \ge H_i\). Αν μοιράσουμε τις \(M\) στήλες σε ομάδες (buckets) από \(\sqrt{M}\) γειτονικές στήλες και προϋπολογίσουμε το ελάχιστο ύψος σε κάθε ομάδα, μπορούμε να ολισθαίνουμε τους δείκτες μας κατά \(\sqrt{M}\) στήλες σε χρόνο \(\mathcal{O}(1)\) επιταχύνοντας την προηγούμενη λύση¹. Παρατηρήστε πως τα \(M\) ύψη χωρίζονται σε \(S\) ομάδες μεγέθους \(\sqrt{M}\) όπου σε κάθε ομάδα \(i\) έχει προϋπολογιστεί η ελάχιστη τιμή \(B_i\):

\[\underbrace{H_0, H_1, \dots, H_{\sqrt{M}-1}}_{B_0}, \underbrace{H_{\sqrt{M}}, \dots, H_{2\cdot\sqrt{M}-1}}_{B_1}, \dots, \underbrace{H_{S \cdot \sqrt{M}}, \dots, H_{M-1}}_{B_{S-1}}\]

Αν η αρχή ή/και το τέλους του μεγαλύτερου ορθογωνίου παραλληλογράμμου που περιέχει τη στήλη \(i\) και έχει ύψος \(H_i\) δεν βρίσκονται ακριβώς πάνω στα όρια της ομάδας του, θα χρειαστεί να εξετάσουμε τις στήλες της ομάδας μία μία σειριακά. Αυτό όμως δεν αλλάζει την πολυπλοκότητα καθώς σε κάθε αναζήτηση, το πολύ δυο ομάδες των \(\sqrt{M}\) στηλών μπορούν να αναζητηθούν σειριακά ενώ για τις ενδιάμεσες το πολύ \(\sqrt{M}\) ομάδες, οι ελάχιστες τιμές είναι προϋπολογισμένες.
Συνολικός χρόνος επίλυσης \(\mathcal{O}(M \cdot \sqrt{M})\).

inline long bucket_id(long x) { return x/SQRTN; }//id του bucket που περιέχει τη στήλη x
inline long bucket_first(long bid) { return bid*SQRTN; }//πρώτη στήλη στο bucket bid
inline long bucket_last(long bid) { return std::min(bid*SQRTN+SQRTN-1,M-1); }//τελευταία στήλη

long expand_left(long left){
    //αναζήτησε τις συμβατές στήλες αριστερά
    long bid = bucket_id(left), height=H[left], bf = bucket_first(bid);
    if(left<bucket_last(bid)){//δεν ξεκινάμε με ολόκληρο bucket
        while(left-1>=bf && H[left-1]>=height)left--;
        bid--;
        if(left>bf)//δεν φτάσαμε μέχρι το τέλος του bucket
            return left;
    }
    //προσπέρασε ολόκληρα buckets αριστερά
    while(bid>=0 && bucket[bid]>=height)
        left = bucket_first(bid--);
    if(bid>=0){//ας ψάξουμε το επόμενο bucket σειριακά
        bf = bucket_first(bid);
        while(left-1>=bf && H[left-1]>=height)left--;
    }
    return left;
}

    for(long j=0,bid=0,i=0;i<M;i++,j++){
        if(j==SQRTN){//ξεκινά το επόμενο  bucket
            j=0;
            bid++;
        }
        fscanf(in,"%ld",&H[i]);
        H[i] = N-H[i];
        bucket[bid] = std::min(bucket[bid],H[i]);
    }
    fclose(in);
    for(long i=0;i<M;i++){
        long left = expand_left(i);
        long right= expand_right(i);
        ans = std::max(ans,(right-left+1)*H[i]);
    }

Δείτε ολόκληρο τον κώδικα εδώ.

Λύση με δυαδική αναζήτηση και RMQ - \(\mathcal{O}(M \cdot \log^2{M})\)

Η αναζήτηση της μικρότερης τιμής σε ένα συνεχόμενο τμήμα (segment) γνωστών άκρων ενός πίνακα, ονομάζεται RMQ (Range Minimum Query). Ερωτήματα RMQ μπορούν να απαντηθούν με τη SQRT decomposition (που ομοιάζει με τον παραπάνω κώδικα), με δέντρα διαστημάτων (segment trees) αλλά και με άλλους τρόπους όπως ο αραιός πίνακας (sparse table) που θα δούμε στην επόμενη λύση. Η χρήση ενός segment tree μας επιτρέπει να προϋπολογίσουμε με την τεχνική διαίρει και βασίλευε τον πίνακα των υψών και να αποθηκεύσουμε τις ελάχιστες τιμές των διαστημάτων που προκύπτουν, στους κόμβους του segment tree. Κάθε αναζήτηση για την ελάχιστη τιμή σε οποιοδήποτε διάστημα \([\texttt{left}, \texttt{right}]\) γίνεται σε χρόνο \(\mathcal{O}(\log{M})\).

Έστω ότι η στήλη \(i\) μπορεί να επεκταθεί έως και τη \(j\) σχηματίζοντας το μεγαλύτερο ορθογώνιο παραλληλόγραμμο. Όλες οι αναζητήσεις από τη στήλη \(i\) έως και τη θέση \(j\) θα δίνουν αποτέλεσμα RMQ τουλάχιστο \(H_i\) ενώ όλες οι αναζητήσεις πέρα του \(j\) θα δίνουν RMQ μικρότερο από \(H_i\). Αυτό πολύ απλά σημαίνει ότι έχουμε μονοτονία και μπορεί να εφαρμοστεί δυαδική αναζήτηση για να βρεθεί η στήλη \(j\). Κάνοντας δυαδική αναζήτηση από τη στήλη \(i\) προς τα δυο άκρα του πίνακα, βρίσκουμε πόσο επεκτείνεται το ορθογώνιο παραλληλόγραμμο αριστερά και δεξιά της. Για κάθε στήλη κάνουμε δυαδική αναζήτηση η οποία θα κάνει αναζήτηση στο segment tree, άρα για κάθε στήλη θέλουμε \(\mathcal{O}(\log^2{M})\) χρόνο. Συνολική πολυπλοκότητα \(\mathcal{O}(M \cdot \log^2{M})\).

        while(lo<hi){
            long mid=(lo+hi)/2;
            if(query(0,0,M-1,mid,i)>=H[i])
                hi = mid;
            else
                lo = mid+1;
        }
        left = hi;
        //επέκταση δεξιά
        lo=i, hi = M-1;
        while(lo<hi){
            long mid=(lo+hi+1)/2;
            if(query(0,0,M-1,i,mid)>=H[i])
                lo = mid;
            else
                hi = mid-1;
        }
        right = lo;
        ans = max(ans,(right-left+1)*H[i]);

Δείτε ολόκληρο τον κώδικα εδώ

Λύση με αραιό πίνακα (sparse table) - \(\mathcal{O}(M \cdot \log{M})\)

Αναζήτηση RMQ μπορεί να γίνει και με αραιό πίνακα (sparse table), δηλαδή για όλες τις \(M\) θέσεις του πίνακα, να προϋυπολογίσουμε τα ελάχιστα ύψη για διαστήματα πλάτους \(2^0, 2^1, 2^2, 2^3, \dots , 2^{\lfloor\log_2{M}\rfloor}\) συνεχόμενων στηλών που ξεκινούν από κάθε θέση \(i\). Ο προϋπολογισμός απαιτεί μνήμη και χρόνο της τάξης \(\mathcal{O}(M \cdot \log{M})\).

Έχοντας προϋπολογίσει τις RMQ τιμές των παραπάνω διαστημάτων, μπορούμε να απαντάμε σε χρόνο \(\mathcal{O}(1)\) ερωτήματα RMQ για οποιοδήποτε διάστημα \([\texttt{left}, \texttt{right}]\) όταν γνωρίζουμε τα άκρα του². Για να υπολογίσουμε το μέγιστο ορθογώνιο παραλληλόγραμμο που περιέχει τη στήλη \(i\) και έχει ύψος \(H_i\) θα αναζητήσουμε την αριστερότερη στήλη \(\texttt{left}\) και τη δεξιότερη \(\texttt{right}\) ώστε τα διαστήματα \([\texttt{left},i]\) και \([i,\texttt{right}]\) να έχουν RMQ τουλάχιστον \(H_i\).

Είναι δυνατό να βρεθεί η στήλη \(\texttt{right}\) (αντίστοιχα και η \(\texttt{left}\)) κάνοντας δυαδική αναζήτηση και καταλήγοντας σε πολυπλοκότητα ίδια με της προηγούμενης λύσης, όμως υπάρχει καλύτερη μέθοδος. Έστω \(x\) το πλάτος του διαστήματος \([i,\texttt{right}]\). Ο αριθμός \(x\) είναι άγνωστος, όμως έχει την ιδιότητα ότι όλα τα ερωτήματα RMQ που ξεκινούν στη θέση \(i\) με πλάτος έως και \(x\) δίνουν RMQ τουλάχιστον \(H_i\), ενώ για μεγαλύτερο πλάτος έχουν RMQ μικρότερο από \(H_i\) (ή ξεπεράσαμε τη θέση \(M\)). Κάθε ακέραιος αριθμός \(x\) αναπαρίσταται ως άθρoισμα δυνάμεων του δυο (το γνωστό μας δυαδικό σύστημα). Αρκεί λοιπόν να ερευνήσουμε ένα ένα όλα τα διαστήματα με πλάτος τις προϋπολογισμένες δυνάμεις του \(2\) από τον αραιό πίνακα (ξεκινώντας από τη μεγαλύτερη δύναμη) και να την χρησιμοποιήσουμε για να συνθέσουμε τον άγνωστο αριθμό \(x\) αν δεν μας δίνει RMQ μικρότερο από \(H_i\). Προσθέτοντας όλες τις δυνάμεις του \(2\) που έδωσαν RMQ τουλάχιστον \(H_i\) έχουμε τον αριθμό \(x\) και τελικά το ορθογώνιο παραλληλόγραμμο μας.

Με τον τρόπο αυτό ενσωματώνουμε τη δυαδική αναζήτηση με τα RMQ ερωτήματα και για κάθε στήλη \(i\) χρειαζόμαστε χρόνο \(\mathcal{O}(\log{M})\) για να βρούμε το μεγαλύτερo ορθογώνιο παραλληλόγραμμο. Συνολική πολυπλοκότητα \(\mathcal{O}(M \cdot \log{M})\).

Ο προϋπολογισμός των διαστημάτων:

    logm = (long)ceil(log2(M));
    rmq.resize(M,std::vector<long>(logm+1));
    //precompute sparse array O(M*logM)
    for(long i=0;i<M;i++)rmq[i][0] = H[i];
    for(long j=1;j<=logm;j++){
        for(long i=0;i<M;i++){
            long step = 1L << (j-1);
            if(i + step<M)
                rmq[i][j] = std::min(rmq[i][j-1],rmq[i+step][j-1]);
            else
                rmq[i][j] = rmq[i][j-1];
        }
    }

Η αναζήτηση των ορθογώνιων παραλληλογράμμων:

    for(long i=0;i<M;i++){
        long left = i, right = i;
        for(int j=logm;j>=0;j--){
            long step = 1L << j;
            //επέκταση δεξιά
            if(right+1<M && rmq[right+1][j]>=H[i])
                right=std::min(M-1,right+step);
            //επέκταση αριστερά
            if(left-step>=0 && rmq[left-step][j]>=H[i])
                left -= step;
        }
        ans = std::max(ans,(right-left+1)*H[i]);
    }

Δείτε ολόκληρο τον κώδικα εδώ.

Έστω ότι χωρίσουμε τα \(M\) στοιχεία σε ομάδες μεγέθους \(K\), τότε η διάσχιση όλων των ομάδων χρειάζεται χρόνο \(\mathcal{O}(\frac{M}{K})\) ενώ η σειριακή διάσχιση μίας ομάδας χρειάζεται χρόνο \(\mathcal{O}(K)\). Είναι επιθυμητό η σειριακή διάσχιση μίας ομάδας \(K\) στοιχείων να έχει ίδια πολυπλοκότητα με τη διάσχιση όλων των \(\frac{M}{K}\) ομάδων, άρα \(\frac{M}{K}=K\Rightarrow M=K^2 \Rightarrow K=\sqrt{M}\) (αφού \(K \gt 0,M \gt 0\)). ↩
Έστω \(k\) η μέγιστη δύναμη του \(2\) που δεν υπερβαίνει το πλάτος \(x\) του διαστήματος \([\texttt{left}, \texttt{right}]\). Άρα \(2^{k+1}\gt x \Rightarrow 2^k + 2^k \gt x\) οπότε για να βρεθεί το ελάχιστο ύψος του διαστήματος με πλάτος \(x\), αρκεί να βρούμε το μικρότερο ύψος από τα δύο προϋπολογισμένα διαστήματα πλάτους \(2^k\), το ένα που ξεκινά από τη θέση \(\texttt{left}\) και το δεύτερο που καταλήγει στη θέση \(\texttt{right}\). Κανένα από τα δύο διαστήματα πλάτους \(2^k\) δεν υπερβαίνει το πλάτος \(x\) εφόσον \(2^k\leq x\) και ταυτόχρονα η ένωση τους καλύπτει όλο το ζητούμενο διάστημα \(x\). ↩