vector<int> v;                    // Empty vector
vector<int> v(n);                 // n elements, default initialized (0)
vector<int> v(n, val);            // n elements, all = val
vector<int> v = {1, 2, 3};        // Initializer list
vector<vector<int>> v(n, vector<int>(m, 0));  // n x m 2D vector

// Adding elements
v.push_back(x);                   // Add to end: O(1) amortized
v.emplace_back(x);                // More efficient for objects
v.pop_back();                     // Remove last: O(1)

// Access
v[i];                             // Access by index: O(1) (no bounds check)
v.at(i);                          // Access with bounds check
v.front();                        // First element
v.back();                         // Last element

// Size
v.size();                         // Number of elements
v.empty();                        // Check if empty
v.clear();                        // Remove all elements

// Iteration
for (int x : v) { }               // Range-based for
for (int& x : v) { x++; }         // Modify elements
for (int i = 0; i < v.size(); i++) { }  // Index-based

// Read n integers
int n; cin >> n;
vector<int> a(n);
for (int& x : a) cin >> x;

// Reverse
reverse(a.begin(), a.end());
// or
reverse(all(a));  // Using macro

// Sort
sort(all(a));                     // Ascending
sort(all(a), greater<int>());     // Descending

// Remove duplicates from sorted vector
a.erase(unique(all(a)), a.end());

// Find element
auto it = find(all(a), x);
if (it != a.end()) {
    int idx = it - a.begin();
}

// Binary search (on sorted vector)
bool found = binary_search(all(a), x);
auto it = lower_bound(all(a), x);  // First >= x
auto it = upper_bound(all(a), x);  // First > x

set<int> s;

// Insert: O(log n)
s.insert(5);
s.insert(3);
s.insert(5);  // Ignored, already exists
// s = {3, 5}

// Check existence: O(log n)
if (s.count(5)) { }       // Returns 0 or 1
if (s.find(5) != s.end()) { }

// Erase: O(log n)
s.erase(5);               // By value
s.erase(s.begin());       // By iterator

// Bounds (powerful!)
auto it = s.lower_bound(4);  // First >= 4, returns iterator to 5
auto it = s.upper_bound(4);  // First > 4, returns iterator to 5

// Min/Max
*s.begin();               // Minimum
*s.rbegin();              // Maximum (or *prev(s.end()))

// Iterate (sorted order)
for (int x : s) { }

map<string, int> m;

// Insert/Update: O(log n)
m["apple"] = 5;
m["banana"]++;            // Inserts with value 0, then increments

// Access: O(log n)
cout << m["apple"];       // 5
cout << m["cherry"];      // Creates entry with value 0!

// Check existence first
if (m.count("apple")) { }
if (m.find("apple") != m.end()) { }

// Safe access
auto it = m.find("apple");
if (it != m.end()) {
    cout << it->second;  // Value
}

// Iterate (sorted by key)
for (auto& [key, value] : m) {
    cout << key << ": " << value << '\n';
}

// Erase
m.erase("apple");

multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(3);
// ms = {3, 5, 5}

ms.count(5);              // Returns 2
ms.erase(5);              // Erases ALL 5s!
ms.erase(ms.find(5));     // Erases ONE 5

// Max heap (default)
priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
pq.top();   // 4 (maximum)
pq.pop();   // Removes 4

// Min heap
priority_queue<int, vector<int>, greater<int>> minPq;
minPq.push(3);
minPq.push(1);
minPq.push(4);
minPq.top();  // 1 (minimum)

// With pairs (compares by first, then second)
priority_queue<pair<int, int>> pq;
pq.push({5, 1});
pq.push({3, 2});
pq.top();  // {5, 1}

// Min heap for shortest paths
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push({0, start});  // {distance, node}

while (!pq.empty()) {
    auto [d, u] = pq.top();
    pq.pop();
    
    if (d > dist[u]) continue;  // Already processed
    
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

#include <algorithm>

vector<int> a = {3, 1, 4, 1, 5};

// Sort ascending
sort(all(a));  // {1, 1, 3, 4, 5}

// Sort descending
sort(all(a), greater<int>());  // {5, 4, 3, 1, 1}

// Custom comparator
sort(all(a), [](int x, int y) {
    return x > y;  // Descending
});

// Sort pairs by second element
vector<pair<int, int>> v = {{1, 3}, {2, 1}, {3, 2}};
sort(all(v), [](auto& a, auto& b) {
    return a.second < b.second;
});
// v = {{2, 1}, {3, 2}, {1, 3}}

// Partial sort (first k elements)
partial_sort(a.begin(), a.begin() + k, a.end());

// Nth element (find kth smallest, O(n) average)
nth_element(a.begin(), a.begin() + k, a.end());
// a[k] is now the (k+1)th smallest

vector<int> a = {1, 2, 3, 4, 5};  // Must be sorted!

// Check if exists
binary_search(all(a), 3);  // true

// Lower bound: first >= target
auto it = lower_bound(all(a), 3);  // Points to 3
int idx = it - a.begin();  // Index 2

// Upper bound: first > target
auto it = upper_bound(all(a), 3);  // Points to 4
int idx = it - a.begin();  // Index 3

// Count occurrences
int count = upper_bound(all(a), x) - lower_bound(all(a), x);

// Find range of equal elements
auto [lo, hi] = equal_range(all(a), 3);

// Min/Max
*min_element(all(a));           // Minimum value
*max_element(all(a));           // Maximum value
auto [mn, mx] = minmax_element(all(a));

// Sum
accumulate(all(a), 0);          // Sum (start from 0)
accumulate(all(a), 0LL);        // Use long long for large sums

// Count
count(all(a), x);               // Count occurrences of x
count_if(all(a), [](int x) { return x > 0; });

// Reverse
reverse(all(a));

// Rotate
rotate(a.begin(), a.begin() + k, a.end());  // Left rotate by k

// Unique (remove consecutive duplicates)
a.erase(unique(all(a)), a.end());  // Works on sorted array

// Next/Prev permutation
do {
    // Process current permutation
} while (next_permutation(all(a)));

// Fill
fill(all(a), 0);
fill(arr, arr + n, 0);  // For C-style arrays

// GCD/LCM (C++17)
__gcd(a, b);           // GCD
gcd(a, b);             // C++17
lcm(a, b);             // C++17

string s = "hello";

// Basics
s.size();                // or s.length()
s.empty();
s[0];                    // 'h'
s.front();               // 'h'
s.back();                // 'o'

// Modification
s.push_back('!');        // "hello!"
s.pop_back();            // "hello"
s += " world";           // "hello world"

// Substring
s.substr(0, 5);          // "hello" (pos, len)
s.substr(6);             // "world" (pos to end)

// Find
s.find("world");         // 6 (position, or string::npos if not found)
s.find('o');             // 4

// Compare
s < "hi";                // true (lexicographic)
s == "hello world";      // true

// Convert
to_string(123);          // "123"
stoi("123");             // 123
stoll("123456789012");   // 123456789012LL

// Reverse
reverse(all(s));

// WRONG: Erasing while iterating
for (auto it = s.begin(); it != s.end(); it++) {
    if (*it == target) {
        s.erase(it);  // Iterator invalidated!
    }
}

// CORRECT
for (auto it = s.begin(); it != s.end(); ) {
    if (*it == target) {
        it = s.erase(it);  // erase returns next valid iterator
    } else {
        it++;
    }
}

// WRONG
for (auto& [k, v] : m) {
    if (v == 0) m.erase(k);  // Undefined behavior
}

// CORRECT: Collect keys first
vector<int> toRemove;
for (auto& [k, v] : m) {
    if (v == 0) toRemove.push_back(k);
}
for (int k : toRemove) m.erase(k);

map<int, int> m;
if (m[5] > 0) { }  // Creates m[5] = 0!

// CORRECT
if (m.count(5) && m[5] > 0) { }