star_problem_final.cpp

/*
 * ★ Problem  —  Sequence with Three Operations
 * ============================================================
 * Given S = <x0, …, xn-1>, maintain a compact data structure:
 *
 *   report_min(i, j)          – min of S[i..j]
 *   multi_increment(i, j, Δ)  – add Δ to every S[k], i ≤ k ≤ j
 *   rotate(i, j)              – reverse subarray S[i..j]
 *                               (xi↔xj, xi+1↔xj-1, …)
 *
 * Solution: Implicit Treap with two lazy tags
 * ─────────────────────────────────────────────────────────────
 * An Implicit Treap is a randomised BST whose "key" is each
 * node's rank in the sequence (implicit — never stored).
 * Random priorities keep expected height at O(log n).
 *
 * Every range op on S[i..j] uses the same pattern:
 *   split → apply O(1) lazy tag → merge back
 *
 * Lazy tags per node (both commute freely):
 *   lazy  – pending add-delta for the whole subtree
 *   rev   – pending reversal flag for the whole subtree
 *
 * Complexity   report_min / multi_increment / rotate → O(log n)
 *              Space                                 → O(n)
 */

#include <bits/stdc++.h>
using namespace std;

// ── Seeded RNG ────────────────────────────────────────────────
// BUG IN ORIGINAL: rng() was called but mt19937 rng was never declared.
// Fix: declare and seed it properly here.
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

// ══════════════════════════════════════════════════════════════
//  Node
// ══════════════════════════════════════════════════════════════
struct Node {
    int  val, minVal;   // element value + subtree minimum (after lazy)
    int  lazy;          // pending add-delta for subtree
    bool rev;           // pending reversal for subtree
    int  size, prio;
    Node *left, *right;

    explicit Node(int v)
        : val(v), minVal(v), lazy(0), rev(false),
          size(1), prio((int)rng()),
          left(nullptr), right(nullptr) {}
};

// ── Aggregate helpers ─────────────────────────────────────────
int sz(Node* t) { return t ? t->size   : 0; }
int mn(Node* t) { return t ? t->minVal : INT_MAX; }

void pull(Node* t) {          // recompute size + minVal from children
    if (!t) return;
    t->size   = 1 + sz(t->left) + sz(t->right);
    t->minVal = min({t->val, mn(t->left), mn(t->right)});
}

// ── Lazy-tag application (O(1) each) ─────────────────────────
void applyAdd(Node* t, int d) {   // "add d to every element in subtree"
    if (!t) return;
    t->val    += d;
    t->minVal += d;
    t->lazy   += d;
}

void applyRev(Node* t) {          // "reverse order of subtree"
    if (!t) return;
    swap(t->left, t->right);      // swap children immediately …
    t->rev ^= true;               // … propagate flag lazily later
}

// ── Push before descending into a node ───────────────────────
// The two tags commute (add doesn't affect order; rev doesn't
// affect values), so push order is free.
void push(Node* t) {
    if (!t) return;
    if (t->lazy) {
        applyAdd(t->left,  t->lazy);
        applyAdd(t->right, t->lazy);
        t->lazy = 0;
    }
    if (t->rev) {
        applyRev(t->left);
        applyRev(t->right);
        t->rev = false;
    }
}

// ══════════════════════════════════════════════════════════════
//  Core primitives: split / merge  (both O(log n) expected)
// ══════════════════════════════════════════════════════════════
// split(t, k) → (L, R) where L has exactly k nodes
pair<Node*, Node*> split(Node* t, int k) {
    if (!t) return {nullptr, nullptr};
    push(t);                               // always push before descending
    int lsz = sz(t->left);
    if (lsz >= k) {
        auto [L, R] = split(t->left, k);
        t->left = R;
        pull(t);
        return {L, t};
    } else {
        auto [L, R] = split(t->right, k - lsz - 1);
        t->right = L;
        pull(t);
        return {t, R};
    }
}

Node* merge(Node* l, Node* r) {
    if (!l) return r;
    if (!r) return l;
    push(l); push(r);
    if (l->prio > r->prio) {
        l->right = merge(l->right, r);
        pull(l);
        return l;
    } else {
        r->left = merge(l, r->left);
        pull(r);
        return r;
    }
}

// ══════════════════════════════════════════════════════════════
//  Public API  (0-indexed, both endpoints inclusive)
// ══════════════════════════════════════════════════════════════

// Isolate S[i..j] into three parts, operate on middle, reassemble.
// This helper (from my Python version) eliminates repetition.
#define ISOLATE(root, i, j)                         \
    auto [L__, MR__] = split(root, i);              \
    auto [M__, R__]  = split(MR__, (j)-(i)+1);     \
    Node *&L = L__, *&M = M__, *&R = R__;
#define REASSEMBLE(root) root = merge(L, merge(M, R))

int reportMin(Node*& root, int i, int j) {
    ISOLATE(root, i, j)
    int res = mn(M);
    REASSEMBLE(root);
    return res;
}

void multiIncrement(Node*& root, int i, int j, int delta) {
    ISOLATE(root, i, j)
    applyAdd(M, delta);
    REASSEMBLE(root);
}

void rotateSeq(Node*& root, int i, int j) {
    // Avoids shadowing std::rotate from <algorithm>
    ISOLATE(root, i, j)
    applyRev(M);
    REASSEMBLE(root);
}

// ── Utility ───────────────────────────────────────────────────
Node* build(const vector<int>& a) {
    Node* root = nullptr;
    for (int x : a) root = merge(root, new Node(x));
    return root;
}

vector<int> toVec(Node* t) {
    vector<int> out;
    function<void(Node*)> inorder = [&](Node* t) {
        if (!t) return;
        push(t);
        inorder(t->left);
        out.push_back(t->val);
        inorder(t->right);
    };
    inorder(t);
    return out;
}

void printSeq(Node* root, const string& label = "") {
    if (!label.empty())
        cout << left << setw(34) << (label + " ") << ": ";
    cout << "[ ";
    for (int x : toVec(root)) cout << x << " ";
    cout << "]\n";
}

// ══════════════════════════════════════════════════════════════
//  Stress test vs brute force  (from my Python version)
// ══════════════════════════════════════════════════════════════
void stressTest(int n = 200, int ops = 600) {
    cout << "\n── Stress test (n=" << n << ", ops=" << ops << ") ──\n";

    vector<int> ref(n);
    for (int& x : ref) x = (int)(rng() % 1001) - 500;
    Node* root = build(ref);
    int errors = 0;

    for (int t = 0; t < ops; ++t) {
        int i  = rng() % n;
        int j  = i + rng() % (n - i);
        int op = rng() % 3;

        if (op == 0) {                              // ReportMin
            int got  = reportMin(root, i, j);
            int want = *min_element(ref.begin() + i, ref.begin() + j + 1);
            if (got != want) ++errors;
        } else if (op == 1) {                       // MultiIncrement
            int d = (int)(rng() % 101) - 50;
            multiIncrement(root, i, j, d);
            for (int k = i; k <= j; ++k) ref[k] += d;
        } else {                                    // Rotate
            rotateSeq(root, i, j);
            reverse(ref.begin() + i, ref.begin() + j + 1);
        }
        if (toVec(root) != ref) ++errors;
    }

    if (errors == 0)
        cout << "  ✓ PASSED — all " << ops << " operations match brute force\n";
    else
        cout << "  ✗ FAILED — " << errors << " mismatches\n";
}

// ══════════════════════════════════════════════════════════════
//  main
// ══════════════════════════════════════════════════════════════
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // ── Slide 23 example: Rotate ──────────────────────────────
    cout << "══ Slide Example ═══════════════════════════════════\n";
    Node* root = build({14, 12, 23, 19, 111, 51, 321, -40});
    printSeq(root,  "Initial");
    rotateSeq(root, 1, 6);
    printSeq(root,  "After Rotate(1,6)");
    // Expected: [ 14 321 51 111 19 23 12 -40 ]

    // ── Chained operations demo (from original code) ──────────
    cout << "\n══ Combined Operations Demo ════════════════════════\n";
    root = build({5, 3, 8, 1, 9, 2, 7, 4, 6});
    printSeq(root, "Initial");

    cout << "ReportMin(2,6)              = "
         << reportMin(root, 2, 6) << "\n";      // min(8,1,9,2,7) = 1

    multiIncrement(root, 1, 4, 10);
    printSeq(root, "After MultiIncrement(1,4,10)");
    // indices 1..4: {3,8,1,9} → {13,18,11,19}

    cout << "ReportMin(0,8) after inc    = "
         << reportMin(root, 0, 8) << "\n";

    rotateSeq(root, 0, 4);
    printSeq(root, "After Rotate(0,4)");

    rotateSeq(root, 3, 7);
    printSeq(root, "After Rotate(3,7)");

    multiIncrement(root, 0, 8, -5);
    printSeq(root, "After MultiIncrement(0,8,-5)");

    cout << "Final ReportMin(0,8)        = "
         << reportMin(root, 0, 8) << "\n";

    // ── Stress test (from my Python version) ──────────────────
    stressTest(200, 600);

    // ── Interactive mode (from original code) ─────────────────
    cout << "\n══ Interactive Mode ════════════════════════════════\n";
    int n; cout << "Enter n: "; cin >> n;
    vector<int> b(n);
    cout << "Enter " << n << " integers: ";
    for (int& x : b) cin >> x;
    root = build(b);
    printSeq(root, "Sequence");

    int q; cout << "Enter number of queries: "; cin >> q;
    while (q--) {
        cout << "\n  Type (1=ReportMin  2=MultiIncrement  3=Rotate): ";
        int type; cin >> type;
        if (type == 1) {
            int i, j; cin >> i >> j;
            cout << "  Min[" << i << ".." << j << "] = "
                 << reportMin(root, i, j) << "\n";
        } else if (type == 2) {
            int i, j, d; cin >> i >> j >> d;
            multiIncrement(root, i, j, d);
            printSeq(root, "  Sequence");
        } else if (type == 3) {
            int i, j; cin >> i >> j;
            rotateSeq(root, i, j);
            printSeq(root, "  Sequence");
        } else {
            cout << "  Unknown query type.\n";
        }
    }

    // ── Complexity summary ────────────────────────────────────
    cout << R"(
══ Complexity Summary ══════════════════════════════
  Data structure   Implicit Treap + lazy propagation

  Lazy tags        lazy_add  (range add)     ┐ commute freely:
                   lazy_rev  (range reverse)  ┘ push order is free

  Operation                Time          Notes
  ────────────────────────────────────────────────────────
  report_min(i,j)          O(log n) exp  2×split + read minVal + 2×merge
  multi_increment(i,j,Δ)   O(log n) exp  2×split + O(1) applyAdd + 2×merge
  rotate(i,j)              O(log n) exp  2×split + O(1) applyRev + 2×merge
  Space                    O(n)          one Node per element
)";

    return 0;
}