자료 구조

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

int main() {
    set<int> s;
    s.insert(5); s.insert(3); s.insert(8); s.insert(3); // 3 중복 무시
    cout << s.count(3) << "\n";        // 1 (있으면 1, 없으면 0)
    s.erase(3);
    cout << s.count(3) << "\n";        // 0

    // 순서 질의: 5 이상인 가장 작은 원소
    auto it = s.lower_bound(5);        // >= 5
    if (it != s.end()) cout << *it << "\n";   // 5
    auto it2 = s.upper_bound(5);       // > 5
    if (it2 != s.end()) cout << *it2 << "\n"; // 8

    map<string,int> cnt;
    cnt["apple"]++;                    // 없으면 0에서 시작
    cnt["apple"]++;
    cout << cnt["apple"] << "\n";      // 2
    if (cnt.count("banana")) cout << "yes\n"; else cout << "no\n"; // no
}

unordered_map<int,int> cnt;
for (int x : {2,3,2,5,3,2}) cnt[x]++;
cout << cnt[2] << "\n";   // 3

s = set()
s.add(5); s.add(3); s.add(8); s.add(3)   # 3 중복 무시
print(3 in s)          # True
s.discard(3)           # 없어도 에러 안 남 (remove는 에러)
print(3 in s)          # False

# 빈도수: Counter가 편리
from collections import Counter
cnt = Counter([2, 3, 2, 5, 3, 2])
print(cnt[2])          # 3
print(cnt[99])         # 0  (없는 키는 0, 하지만 조회로 생성되진 않음)

# 기본값 딕셔너리
from collections import defaultdict
g = defaultdict(list)
g[1].append(2)         # 없으면 빈 리스트 자동 생성
print(g[1])            # [2]

import bisect
arr = [3, 5, 8]                 # 정렬 상태 유지 필요
i = bisect.bisect_left(arr, 5)  # >= 5 인 첫 위치 → 1
print(arr[i])                   # 5

vector<int> a = {100, 5, 100, 50000, 5};
vector<int> vals = a;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end()); // 정렬 + 중복 제거
for (int& x : a)
    x = lower_bound(vals.begin(), vals.end(), x) - vals.begin(); // 압축 인덱스
// a = {1, 0, 1, 2, 0}  (5→0, 100→1, 50000→2)

a = [100, 5, 100, 50000, 5]
vals = sorted(set(a))                  # [5, 100, 50000]
comp = {v: i for i, v in enumerate(vals)}
a = [comp[x] for x in a]               # [1, 0, 1, 2, 0]

multiset<int> ms;
ms.insert(5); ms.insert(5); ms.insert(3);
cout << *ms.begin() << "\n";        // 3 (최솟값)
cout << *ms.rbegin() << "\n";       // 5 (최댓값)

// 5를 '하나만' 지우기 — 아주 흔한 함정
ms.erase(ms.find(5));               // O(log N), 5 하나만 제거
// ms.erase(5);  ← 이렇게 하면 5를 '전부' 지운다! 주의
cout << ms.count(5) << "\n";        // 1

set<int> pts;
// 새 점 x의 가장 가까운 이웃 후보
auto it = pts.lower_bound(x);          // x 이상 첫 원소
int best = INT_MAX;
if (it != pts.end()) best = min(best, *it - x);
if (it != pts.begin()) { --it; best = min(best, x - *it); }

struct Hash {
    size_t operator()(long long x) const {
        x ^= 0x9e3779b97f4a7c15ULL;      // 랜덤 상수로 섞기
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
};
unordered_map<long long, int, Hash> safe;

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

int main() {
    stack<int> st;
    st.push(5);
    st.push(2);
    st.push(8);
    cout << st.top() << "\n";   // 8
    st.pop();                    // 8 제거
    cout << st.top() << "\n";   // 2
    cout << st.size() << "\n";  // 2
    while (!st.empty()) st.pop();
    cout << (st.empty() ? "empty" : "not") << "\n"; // empty
}

const int MAXN = 1000000;
int data[MAXN], top = 0;      // top = 원소 개수(= 다음 빈 칸)

void push(int x) { data[top++] = x; }
int  pop()       { return data[--top]; }   // 비었는지 호출자가 확인
int  peek()      { return data[top - 1]; }
bool empty()     { return top == 0; }

st = []
st.append(5)
st.append(2)
st.append(8)
print(st[-1])      # 8  (top)
print(st.pop())    # 8  (꺼내며 제거)
print(st[-1])      # 2
print(len(st))     # 2
print(not st)      # False (비었으면 True)

bool balanced(const string& s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(') st.push(c);
        else {                       // c == ')'
            if (st.empty()) return false;  // 짝 없는 닫는 괄호
            st.pop();
        }
    }
    return st.empty();               // 안 닫힌 여는 괄호가 없어야 함
}

def balanced(s):
    st = []
    for c in s:
        if c == '(':
            st.append(c)
        else:
            if not st:
                return False
            st.pop()
    return not st

vector<int> nextGreater(const vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);
    stack<int> st;                       // 인덱스 저장, 값은 감소 유지
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            ans[st.top()] = a[i];        // i가 st.top()의 다음 큰 값
            st.pop();
        }
        st.push(i);
    }
    return ans;
}

def next_greater(a):
    n = len(a)
    ans = [-1] * n
    st = []                              # 인덱스
    for i in range(n):
        while st and a[st[-1]] < a[i]:
            ans[st.pop()] = a[i]
        st.append(i)
    return ans

long long largestRectangle(const vector<int>& h) {
    int n = h.size();
    stack<int> st;                       // 높이가 증가하도록 인덱스 저장
    long long best = 0;
    for (int i = 0; i <= n; i++) {
        int cur = (i == n) ? 0 : h[i];   // 끝에 높이 0 sentinel
        while (!st.empty() && h[st.top()] >= cur) {
            int height = h[st.top()]; st.pop();
            int left = st.empty() ? -1 : st.top();
            long long width = i - left - 1;
            best = max(best, (long long)height * width);
        }
        st.push(i);
    }
    return best;
}

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

int main() {
    queue<int> q;
    q.push(1); q.push(2); q.push(3);
    cout << q.front() << "\n";   // 1
    q.pop();                      // 1 제거
    cout << q.front() << "\n";   // 2
    cout << q.size() << "\n";    // 2

    deque<int> dq;
    dq.push_back(10);
    dq.push_front(5);            // [5, 10]
    dq.push_back(20);           // [5, 10, 20]
    cout << dq.front() << " " << dq.back() << "\n"; // 5 20
    dq.pop_front();             // [10, 20]
    dq.pop_back();              // [10]
    cout << dq.front() << "\n"; // 10
}

const int MAXN = 1000000;
int buf[MAXN], head = 0, tail = 0;   // [head, tail) 가 현재 원소

void push(int x) { buf[tail++] = x; }
int  pop()       { return buf[head++]; }   // 비었는지 호출자가 확인
bool empty()     { return head == tail; }
int  size()      { return tail - head; }

from collections import deque

q = deque()
q.append(1); q.append(2); q.append(3)  # 뒤에 push
print(q[0])          # 1  (front)
print(q.popleft())   # 1  (앞에서 pop)
print(q[0])          # 2

dq = deque()
dq.append(10)        # 뒤
dq.appendleft(5)     # 앞 → [5, 10]
dq.append(20)        # [5, 10, 20]
print(dq[0], dq[-1]) # 5 20
dq.popleft()         # [10, 20]
dq.pop()             # [10]  (뒤에서)

vector<int> adj[MAXN];
int dist[MAXN];

void bfs(int start, int n) {
    for (int i = 0; i < n; i++) dist[i] = -1;
    queue<int> q;
    dist[start] = 0; q.push(start);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            q.push(v);
        }
    }
}

vector<int> slidingMax(const vector<int>& a, int k) {
    deque<int> dq;                       // 인덱스, 값 감소 유지
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();
        dq.push_back(i);
        if (dq.front() <= i - k) dq.pop_front();  // 창 벗어난 앞 제거
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}

from collections import deque

def sliding_max(a, k):
    dq = deque()          # 인덱스
    res = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            res.append(a[dq[0]])
    return res

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

int main() {
    priority_queue<int> maxpq;          // 최대 힙(기본)
    maxpq.push(5); maxpq.push(1); maxpq.push(3);
    cout << maxpq.top() << "\n";        // 5
    maxpq.pop();
    cout << maxpq.top() << "\n";        // 3

    // 최소 힙: greater 비교자 사용
    priority_queue<int, vector<int>, greater<int>> minpq;
    minpq.push(5); minpq.push(1); minpq.push(3);
    cout << minpq.top() << "\n";        // 1
}

// (거리, 정점) 최소 힙
priority_queue<pair<long long,int>,
               vector<pair<long long,int>>,
               greater<>> pq;
pq.push({0, start});

import heapq

h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 3)
print(h[0])              # 1  (최솟값 = top)
print(heapq.heappop(h))  # 1
print(heapq.heappop(h))  # 3

# 이미 있는 리스트를 O(N)에 힙으로
data = [5, 1, 3, 8, 2]
heapq.heapify(data)      # O(N)
print(heapq.heappop(data))  # 1

h = []
for x in [5, 1, 3]:
    heapq.heappush(h, -x)     # 부호 반전
print(-heapq.heappop(h))      # 5  (다시 반전해서 읽기)

struct MinHeap {
    vector<long long> h{0};          // h[0]은 사용 안 함(자리표시)
    int size() { return h.size() - 1; }
    bool empty() { return size() == 0; }
    void push(long long x) {
        h.push_back(x);
        int i = size();
        while (i > 1 && h[i] < h[i/2]) {   // sift-up
            swap(h[i], h[i/2]); i /= 2;
        }
    }
    long long top() { return h[1]; }
    void pop() {
        h[1] = h.back(); h.pop_back();
        int i = 1, n = size();
        while (true) {                     // sift-down
            int l = 2*i, r = 2*i+1, m = i;
            if (l <= n && h[l] < h[m]) m = l;
            if (r <= n && h[r] < h[m]) m = r;
            if (m == i) break;
            swap(h[i], h[m]); i = m;
        }
    }
};

vector<pair<int,int>> adj[MAXN];         // (이웃, 가중치)
long long dist[MAXN];

void dijkstra(int src, int n) {
    for (int i = 0; i < n; i++) dist[i] = LLONG_MAX;
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>, greater<>> pq;
    dist[src] = 0; pq.push({0, src});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d > dist[u]) continue;       // 낡은 항목 → 버림
        for (auto [v, w] : adj[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v], v});
            }
        }
    }
}

import heapq

def dijkstra(adj, src, n):
    dist = [float('inf')] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

import heapq

class MedianStream:
    def __init__(self):
        self.lower = []   # 최대 힙(부호 반전)
        self.upper = []   # 최소 힙
    def add(self, x):
        heapq.heappush(self.lower, -x)
        # lower의 최대가 upper의 최소보다 크면 넘김
        heapq.heappush(self.upper, -heapq.heappop(self.lower))
        # 크기 균형: lower가 항상 >= upper
        if len(self.upper) > len(self.lower):
            heapq.heappush(self.lower, -heapq.heappop(self.upper))
    def median(self):
        if len(self.lower) > len(self.upper):
            return -self.lower[0]
        return (-self.lower[0] + self.upper[0]) / 2

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

const ll P = 131, M = 1000000007LL;

int main() {
    string s; cin >> s;
    int n = s.size();
    vector<ll> h(n + 1, 0), pw(n + 1, 1);
    for (int i = 0; i < n; i++) {
        h[i + 1] = (h[i] * P + (s[i] - 'a' + 1)) % M;   // 접두사 해시
        pw[i + 1] = pw[i] * P % M;                       // P^(i+1)
    }
    // s[l..r] (0-index, 닫힌 구간)의 해시
    auto sub = [&](int l, int r) -> ll {
        return ((h[r + 1] - h[l] * pw[r - l + 1]) % M + M) % M;
    };
    // 예: 두 부분 문자열이 같은가?  sub(a,b) == sub(c,d)
}

def build_hash(s, P=131, M=(1 << 61) - 1):
    n = len(s)
    h = [0] * (n + 1)
    pw = [1] * (n + 1)
    for i in range(n):
        h[i + 1] = (h[i] * P + (ord(s[i]) - ord('a') + 1)) % M
        pw[i + 1] = pw[i] * P % M
    def sub(l, r):                 # s[l..r] 닫힌 구간
        return (h[r + 1] - h[l] * pw[r - l + 1]) % M
    return sub

vector<int> rabinKarp(const string& text, const string& pat) {
    int n = text.size(), m = pat.size();
    vector<int> res;
    if (m > n) return res;
    ll pph = 0, pw = 1;                 // 패턴 해시, P^(m-1)
    for (int i = 0; i < m; i++) {
        pph = (pph * P + (pat[i] - 'a' + 1)) % M;
        if (i) pw = pw * P % M;
    }
    ll cur = 0;
    for (int i = 0; i < n; i++) {
        cur = (cur * P + (text[i] - 'a' + 1)) % M;          // 앞에서 한 글자 추가
        if (i >= m) cur = (cur - (text[i-m]-'a'+1) * pw % M * P % M + M*M) % M; // 뒤 한 글자 제거
        if (i >= m - 1 && cur == pph) res.push_back(i - m + 1);
    }
    return res;
}

def rabin_karp(text, pat, P=131, M=(1 << 61) - 1):
    n, m = len(text), len(pat)
    if m > n:
        return []
    pph = 0
    for c in pat:
        pph = (pph * P + (ord(c) - ord('a') + 1)) % M
    powm = pow(P, m - 1, M)
    cur, res = 0, []
    for i, c in enumerate(text):
        cur = (cur * P + (ord(c) - ord('a') + 1)) % M
        if i >= m:
            cur = (cur - (ord(text[i-m]) - ord('a') + 1) * powm * P) % M
        if i >= m - 1 and cur == pph:
            res.append(i - m + 1)
    return res

// 값을 pair<ll,ll>로 다루거나, (h1 << 32 | h2) 형태로 합쳐 비교
pair<ll,ll> sub2(int l, int r) { return { sub1(l,r), sub2b(l,r) }; }
// 비교: sub2(a,b) == sub2(c,d)

import random
P = random.randint(256, 10**6)   # 실행마다 다른 밑 → anti-hash 방어

def is_palindrome_checker(s, P=131, M=(1 << 61) - 1):
    fwd = build_hash(s, P, M)               # 앞 강의의 build_hash
    bwd = build_hash(s[::-1], P, M)
    n = len(s)
    def check(l, r):                        # s[l..r]이 회문인가
        length = r - l + 1
        # 뒤집은 문자열에서 s[l..r]에 대응하는 구간
        rl, rr = n - 1 - r, n - 1 - l
        return fwd(l, r) == bwd(rl, rr)
    return check

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

struct DSU {
    vector<int> parent, sz;
    DSU(int n) : parent(n), sz(n, 1) {
        iota(parent.begin(), parent.end(), 0);   // parent[i] = i
    }
    int find(int x) {                             // 경로 압축
        while (parent[x] != x)
            x = parent[x] = parent[parent[x]];    // 반경로 압축
        return x;
    }
    bool unite(int a, int b) {                    // union by size
        a = find(a); b = find(b);
        if (a == b) return false;                 // 이미 같은 그룹
        if (sz[a] < sz[b]) swap(a, b);            // 큰 쪽(a) 밑에 붙임
        parent[b] = a;
        sz[a] += sz[b];
        return true;
    }
    bool same(int a, int b) { return find(a) == find(b); }
    int size(int x) { return sz[find(x)]; }
};

int main() {
    DSU d(5);
    d.unite(0, 1); d.unite(2, 3); d.unite(0, 2);
    cout << d.same(1, 3) << "\n";   // 1 (true)
    cout << d.same(1, 4) << "\n";   // 0 (false)
    cout << d.size(0) << "\n";      // 4
}

vector<int> parent, rnk;   // rnk 초기값 0
int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); } // 재귀 압축
bool unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return false;
    if (rnk[a] < rnk[b]) swap(a, b);
    parent[b] = a;
    if (rnk[a] == rnk[b]) rnk[a]++;   // 높이가 같을 때만 1 증가
    return true;
}

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:      # 경로 압축(2-패스)
            self.parent[x], x = root, self.parent[x]
        return root
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True
    def same(self, a, b):
        return self.find(a) == self.find(b)

d = DSU(5)
d.union(0, 1); d.union(2, 3); d.union(0, 2)
print(d.same(1, 3))   # True
print(d.same(1, 4))   # False
print(d.size[d.find(0)])  # 4

long long kruskal(int n, vector<array<int,3>>& edges) { // {w, u, v}
    sort(edges.begin(), edges.end());
    DSU d(n);
    long long total = 0; int used = 0;
    for (auto& [w, u, v] : edges) {
        if (d.unite(u, v)) {          // 합쳐졌다 = 사이클 아님
            total += w;
            if (++used == n - 1) break;
        }
    }
    return total;                     // used < n-1 이면 그래프가 비연결
}