정렬과 탐색

sort(a.begin(), a.end(), greater<int>());   // 큰 값부터

a.sort(reverse=True)
b = sorted(a, reverse=True)

// C++에는 key가 없으므로 비교 함수(람다)로 표현
sort(a.begin(), a.end(), [](int x, int y) {
    return abs(x) < abs(y);          // |x| 가 작은 것이 앞
});

a.sort(key=abs)                       # 절댓값 기준
words.sort(key=len)                   # 길이 기준

struct Person { int age; string name; };
vector<Person> v;
sort(v.begin(), v.end(), [](const Person& a, const Person& b) {
    if (a.age != b.age) return a.age < b.age;   // 1순위: 나이 오름차순
    return a.name < b.name;                      // 2순위: 이름 사전순
});

vector<pair<int,int>> p;
sort(p.begin(), p.end());             // first 오름차순, 같으면 second 오름차순

people = [(30, "kim"), (20, "lee"), (30, "ahn")]
people.sort()                         # 튜플 사전식: 나이→이름
# 나이는 오름, 이름은 내림 같은 혼합 기준:
people.sort(key=lambda x: (x[0], x[1]))          # 둘 다 오름
nums.sort(key=lambda x: (-x[0], x[1]))           # 첫째 내림, 둘째 오름

stable_sort(v.begin(), v.end(), cmp); // 같은 키는 입력 순서 유지

// 틀림 — 등호를 넣으면 엄격 약순서 위반
sort(a.begin(), a.end(), [](int x, int y){ return x <= y; }); // 위험!
// 맞음
sort(a.begin(), a.end(), [](int x, int y){ return x <  y; });

// 나쁨: 오버플로 + 타입 오류
// 좋음:
sort(a.begin(), a.end(), [](ll x, ll y){ return x > y; });

from functools import cmp_to_key
def cmp(a, b):
    return -1 if a < b else (1 if a > b else 0)
a.sort(key=cmp_to_key(cmp))

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

void merge_sort(vector<int>& a, int lo, int hi, vector<int>& tmp) {
    if (hi - lo <= 1) return;              // 원소 0~1개면 정렬됨
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid, tmp);
    merge_sort(a, mid, hi, tmp);
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi)              // 두 정렬된 절반을 병합
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];  // <= 로 안정성 유지
    while (i < mid) tmp[k++] = a[i++];
    while (j < hi)  tmp[k++] = a[j++];
    for (int t = lo; t < hi; t++) a[t] = tmp[t];
}
int main() {
    vector<int> a = {5,2,9,1,5,6};
    vector<int> tmp(a.size());
    merge_sort(a, 0, a.size(), tmp);       // 반열린 구간 [0, n)
}

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    res, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    res.extend(left[i:]); res.extend(right[j:])
    return res

void quick_sort(vector<int>& a, int lo, int hi) {   // 닫힌 구간 [lo, hi]
    if (lo >= hi) return;
    int p = a[lo + rand() % (hi - lo + 1)];          // 무작위 피벗
    int i = lo, j = hi;
    while (i <= j) {                                  // Hoare 스타일 분할
        while (a[i] < p) i++;
        while (a[j] > p) j--;
        if (i <= j) swap(a[i++], a[j--]);
    }
    quick_sort(a, lo, j);
    quick_sort(a, i, hi);
}

// 0..K 범위 정수 계수 정렬 (안정 버전)
vector<int> counting_sort(const vector<int>& a, int K) {
    vector<int> cnt(K + 1, 0), out(a.size());
    for (int x : a) cnt[x]++;
    for (int v = 1; v <= K; v++) cnt[v] += cnt[v - 1];   // 누적합 = 끝 위치
    for (int i = (int)a.size() - 1; i >= 0; i--)         // 뒤에서 순회 → 안정
        out[--cnt[a[i]]] = a[i];
    return out;
}

def counting_sort(a, K):
    cnt = [0] * (K + 1)
    for x in a:
        cnt[x] += 1
    out = []
    for v in range(K + 1):
        out.extend([v] * cnt[v])
    return out

# "점수 내림차순, 동점은 이름 오름차순"
people.sort(key=lambda p: p.name)          # 2순위 먼저
people.sort(key=lambda p: -p.score)        # 1순위 나중 (안정 정렬이라 이름순 유지)

int lower_bound_impl(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size();        // hi 는 "끝 다음" (반열림)
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] < target) lo = mid + 1; // mid 부족 → 버림
        else                 hi = mid;     // mid 후보 → 남김
    }
    return lo;                             // target 이상인 첫 인덱스
}

int upper_bound_impl(const vector<int>& a, int target) {
    int lo = 0, hi = (int)a.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] <= target) lo = mid + 1; // <= 로 바꾼 것이 전부
        else                  hi = mid;
    }
    return lo;
}

#include <algorithm>
sort(a.begin(), a.end());                        // 반드시 정렬!
auto lo = lower_bound(a.begin(), a.end(), x);    // x 이상 첫 위치
auto hi = upper_bound(a.begin(), a.end(), x);    // x 초과 첫 위치
int idx     = lo - a.begin();                    // 인덱스로 변환
int count_x = hi - lo;                           // x 의 개수
bool exists = (lo != a.end() && *lo == x);       // 존재 여부

import bisect
a.sort()                                   # 반드시 정렬!
lo = bisect.bisect_left(a, x)              # x 이상 첫 위치 (lower_bound)
hi = bisect.bisect_right(a, x)             # x 초과 첫 위치 (upper_bound)
count_x = hi - lo
exists  = lo < len(a) and a[lo] == x
idx     = bisect.insort(a, x)              # 정렬 유지하며 삽입 (필요 시)

i = bisect.bisect_left(a, x)
prev = a[i - 1] if i > 0 else None         # x 미만 최대값
succ = a[i]     if i < len(a) else None    # x 이상 최소값

int lo = 0, hi = 1'000'000'000, ans = lo;
while (lo <= hi) {
    int mid = lo + (hi - lo) / 2;
    if (ok(mid)) { ans = mid; lo = mid + 1; } // 되면 더 키워 본다
    else         hi = mid - 1;                // 안 되면 줄인다
}
// ans = 가능한 최대 x

int lo = 0, hi = 1'000'000'000;
while (lo < hi) {
    int mid = lo + (hi - lo) / 2;      // 내림
    if (ok(mid)) hi = mid;             // 되면 더 작게
    else         lo = mid + 1;         // 안 되면 키운다
}
// lo == hi 가 답

double lo = 0, hi = 1e9;
for (int it = 0; it < 100; it++) {        // eps 비교보다 안전
    double mid = (lo + hi) / 2;
    if (ok(mid)) lo = mid; else hi = mid;
}
// lo (또는 hi) 가 답

lo, hi = 0.0, 1e9
for _ in range(100):
    mid = (lo + hi) / 2
    if ok(mid):
        lo = mid
    else:
        hi = mid

// 1-based, P[i][j] = (1..i, 1..j) 영역 합
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        P[i][j] = a[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1];

// 직사각형 (r1,c1)-(r2,c2) 합
ll area = P[r2][c2] - P[r1-1][c2] - P[r2][c1-1] + P[r1-1][c1-1];

vector<ll> D(n + 2, 0);
// 각 갱신: 구간 [l, r] 에 +v (1-based)
D[l] += v;  D[r + 1] -= v;
// 모든 갱신 후 한 번에 복원
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = a[i - 1] + D[i];

D = [0] * (n + 2)
for l, r, v in updates:              # 1-based
    D[l] += v
    D[r + 1] -= v
a = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = a[i - 1] + D[i]

// 직사각형 (r1,c1)-(r2,c2) 에 +v
D[r1][c1]     += v;  D[r1][c2+1]   -= v;
D[r2+1][c1]   -= v;  D[r2+1][c2+1] += v;
// 이후 2차원 누적 합으로 실제 값 복원
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++)
        D[i][j] += D[i-1][j] + D[i][j-1] - D[i-1][j-1];

// 합이 정확히 S인 연속 구간의 개수 (음수 포함 가능)
long long count_sum_equal(const vector<int>& a, long long S) {
    unordered_map<long long,long long> freq;
    freq[0] = 1;                       // 빈 접두사
    long long pre = 0, ans = 0;
    for (int x : a) {
        pre += x;
        ans += freq[pre - S];          // pre - prev = S 인 prev 개수
        freq[pre]++;
    }
    return ans;
}

from collections import defaultdict
def count_sum_equal(a, S):
    freq = defaultdict(int); freq[0] = 1
    pre = ans = 0
    for x in a:
        pre += x
        ans += freq[pre - S]
        freq[pre] += 1
    return ans

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

int main() {
    int n = 6;
    vector<ll> d(n + 1, 0);              // d[r+1]까지 접근하므로 여유 한 칸

    auto range_add = [&](int l, int r, ll v) {
        d[l] += v;
        if (r + 1 <= n) d[r + 1] -= v;   // r == n-1이면 넘어가지 않게
    };

    range_add(1, 3, 5);
    range_add(2, 4, 2);
    range_add(0, 5, 1);

    vector<ll> a(n);
    ll cur = 0;
    for (int i = 0; i < n; i++) {         // 누적 합으로 복원
        cur += d[i];
        a[i] = cur;
    }
    for (ll x : a) cout << x << " ";       // 1 6 8 8 3 1
    cout << "\n";
}

def solve(n, updates):                    # updates: (l, r, v) 리스트
    d = [0] * (n + 1)
    for l, r, v in updates:
        d[l] += v
        if r + 1 <= n:
            d[r + 1] -= v
    a, cur = [0] * n, 0
    for i in range(n):
        cur += d[i]
        a[i] = cur
    return a

print(solve(6, [(1, 3, 5), (2, 4, 2), (0, 5, 1)]))  # [1, 6, 8, 8, 3, 1]

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

int n = 4, m = 4;
vector<vector<ll>> d(6, vector<ll>(6, 0));   // (n+2) x (m+2)

void rect_add(int r1, int c1, int r2, int c2, ll v) {
    d[r1][c1]     += v;
    d[r2+1][c1]   -= v;
    d[r1][c2+1]   -= v;
    d[r2+1][c2+1] += v;                       // 겹친 부분 보정
}

int main() {
    rect_add(0, 0, 1, 1, 1);
    rect_add(1, 1, 3, 3, 2);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) {         // 2D prefix sum으로 복원
            if (i) d[i][j] += d[i-1][j];
            if (j) d[i][j] += d[i][j-1];
            if (i && j) d[i][j] -= d[i-1][j-1];
        }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cout << d[i][j] << " ";
        cout << "\n";
    }
    // 1 1 0 0 / 1 3 2 2 / 0 2 2 2 / 0 2 2 2
}

// 펜윅 위의 차분: 구간 더하기 + 점 질의
ll bit[100005]; int N;
void add(int i, ll v){ for(i++; i<=N; i+=i&-i) bit[i]+=v; }
ll sum(int i){ ll s=0; for(i++; i>0; i-=i&-i) s+=bit[i]; return s; }

void range_add(int l, int r, ll v){ add(l, v); add(r+1, -v); }
ll point_query(int i){ return sum(i); }        // 점 i의 현재 값

int longest_le(const vector<int>& a, long long S) {
    int n = a.size(), l = 0, best = 0;
    long long sum = 0;
    for (int r = 0; r < n; r++) {
        sum += a[r];                  // 오른쪽 확장
        while (sum > S) {             // 조건 위반 → 왼쪽 축소
            sum -= a[l];
            l++;
        }
        best = max(best, r - l + 1);  // [l, r] 이 유효
    }
    return best;
}

def longest_le(a, S):
    l, best, sum_ = 0, 0, 0
    for r, x in enumerate(a):
        sum_ += x
        while sum_ > S:
            sum_ -= a[l]
            l += 1
        best = max(best, r - l + 1)
    return best

vector<int> intersect(const vector<int>& a, const vector<int>& b) {
    vector<int> res; int i = 0, j = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] < b[j]) i++;
        else if (a[i] > b[j]) j++;
        else { res.push_back(a[i]); i++; j++; }   // 같으면 채택
    }
    return res;
}

sort(a.begin(), a.end());
for (int i = 0; i < n; i++) {
    int lo = i + 1, hi = n - 1;
    while (lo < hi) {
        int s = a[i] + a[lo] + a[hi];
        if (s == 0) { /* 채택 */ lo++; hi--; }
        else if (s < 0) lo++;
        else hi--;
    }
}

int longest_at_most_k_distinct(const vector<int>& a, int K) {
    unordered_map<int,int> cnt;        // 값 -> 창 내 개수
    int l = 0, best = 0;
    for (int r = 0; r < (int)a.size(); r++) {
        cnt[a[r]]++;                   // 편입
        while ((int)cnt.size() > K) {  // 종류가 K 초과 → 축소
            if (--cnt[a[l]] == 0) cnt.erase(a[l]);
            l++;
        }
        best = max(best, r - l + 1);
    }
    return best;
}

from collections import defaultdict
def longest_at_most_k_distinct(a, K):
    cnt = defaultdict(int)
    l = best = 0
    for r, x in enumerate(a):
        cnt[x] += 1
        while len(cnt) > K:
            cnt[a[l]] -= 1
            if cnt[a[l]] == 0:
                del cnt[a[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

vector<int> max_of_windows(const vector<int>& a, int K) {
    deque<int> dq;                     // 값이 감소하도록 인덱스 유지
    vector<int> res;
    for (int i = 0; i < (int)a.size(); i++) {
        if (!dq.empty() && dq.front() <= i - K) dq.pop_front();  // 창 이탈
        while (!dq.empty() && a[dq.back()] <= a[i]) dq.pop_back();// 열등 제거
        dq.push_back(i);
        if (i >= K - 1) res.push_back(a[dq.front()]);            // 최댓값
    }
    return res;
}

from collections import deque
def max_of_windows(a, K):
    dq, res = deque(), []
    for i, x in enumerate(a):
        if dq and dq[0] <= i - K:
            dq.popleft()
        while dq and a[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= K - 1:
            res.append(a[dq[0]])
    return res

// 최단: 조건(sum >= S)을 만족하는 즉시 길이 갱신하고 왼쪽을 최대한 당김
int shortest_ge(const vector<int>& a, long long S) {
    int l = 0, best = INT_MAX; long long sum = 0;
    for (int r = 0; r < (int)a.size(); r++) {
        sum += a[r];
        while (sum >= S) {                 // 만족하는 동안 계속 줄여 본다
            best = min(best, r - l + 1);
            sum -= a[l]; l++;
        }
    }
    return best == INT_MAX ? 0 : best;
}

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (auto& x : a) cin >> x;

    vector<int> vals(a);                        // 값 복사
    sort(vals.begin(), vals.end());             // 1) 정렬
    vals.erase(unique(vals.begin(), vals.end()), vals.end());  // 2) 중복 제거

    // 3) 각 값을 등수(0-based)로 변환
    for (int i = 0; i < n; i++) {
        int rank = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin();
        cout << rank << ' ';                    // 0..M-1
    }
}