uniolympiads English

Μέγιστη αύξουσα υπακολουθία

Το μήκος της σε O(nlog⁡n)O(n \log n), κρατώντας για κάθε μήκος το μικρότερο δυνατό τελευταίο στοιχείο.

Πότε

Η άμεση εφαρμογή είναι σπάνια. Πολύ συχνότερα το πρόβλημα ανάγεται σε LIS: ταξινομείς ζευγάρια κατά τη μία συντεταγμένη και ψάχνεις αύξουσα ακολουθία στην άλλη (φάκελοι μέσα σε φακέλους, πύργοι από κουτιά).

Η ιδέα

Το DP fi=1+max⁡j<i, aj<aifjf_i = 1 + \max_{j < i,\ a_j < a_i} f_j είναι O(n2)O(n^2). Για n=2⋅105n = 2 \cdot 10^5 χρειάζεται κάτι καλύτερο.

Κρατάμε tailk\mathrm{tail}_k: το μικρότερο τελευταίο στοιχείο ανάμεσα σε όλες τις αύξουσες υπακολουθίες μήκους k+1k+1 που έχουμε δει. Ο πίνακας tail\mathrm{tail} είναι γνησίως αύξων. Για κάθε νέο xx, το πρώτο tailk≥x\mathrm{tail}_k \ge x αντικαθίσταται από το xx: μια υπακολουθία μήκους kk που τελειώνει σε κάτι <x< x επεκτείνεται με το xx. Αν δεν υπάρχει τέτοιο kk, το xx μεγαλώνει τον πίνακα κατά ένα. Η απάντηση είναι το μήκος του πίνακα.

Παγίδες

  • Ο tail\mathrm{tail} δεν είναι η ίδια η υπακολουθία. Για να την ανακατασκευάσεις, κράτα για κάθε στοιχείο τον δείκτη του προηγούμενού του.
  • Γνησίως αύξουσα: lower_bound. Μη φθίνουσα: upper_bound. Το test σε αυτή τη σελίδα έχει πολλές ίσες τιμές για να πιάνει ακριβώς αυτό.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/lis.cpp
// Length of the longest strictly increasing subsequence. O(n log n).
// tail[k] = the smallest possible last element of an increasing subsequence of length k + 1.
// tail stays sorted, so each element replaces the first tail >= it (lower_bound).
// For non-decreasing subsequences use upper_bound instead.

int lisLength(const vector<ll>& a) {
    vector<ll> tail;
    for (ll x : a) {
        auto it = lower_bound(tail.begin(), tail.end(), x);
        if (it == tail.end()) {
            tail.push_back(x);
        } else {
            *it = x;
        }
    }
    return tail.size();
}

Ελέγχθηκε σε 3.000 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.