# CSES Sort & Search
[Link contest](https://lqdoj.edu.vn/contest/csessortandsearch). Cần join group CSES trước.
## Checkpoint 1: Sort, Binary Search, Two Pointer
---
## Distinct
sort lại hoặc dùng map, hoặc set: `cout << s.size()`

## Apartments:
Sắp xếp $a,b$ tăng dần rồi ghép (chính là 2-pointer).

## Ferris
Sắp tăng dần và ghép đứa nhẹ nhất với đứa nặng nhất.

## Sum of Two Values
TKNP hoặc hai con trỏ. (Binary search or two-pointer).

## Sum of Three
Xem bài BOSOTG
Chạy `for` để cố định một số thì quy về bài trên.

## Stick Lengths
Cho dãy $a$. Tìm số $x$ để biến đổi toàn dãy về giá trị này, để chi phí $\sum (a_i-x)$ đạt $\min$.
Đáp án: Lấy $x$ là trung vị của dãy. Tức phần tử đứng giữa (vị trí $n/2$) trong dãy $a$ đã sắp xếp. Trường hợp $n$ chẵn thì lấy nằm giữa hai giá trị này là được. VD $a = \{1,2,3,7,8,11\}$ thì $x \in [3,7]$

## Missing Coin Sum
Giả sử đã tạo được mọi tổng từ $1$ tới $X$.
Nếu cho thêm một xu $x_i$, chắc chắn tạo thêm được đoạn $1 + x_i$ tới $X + x_i$
- TH 1: $X + 1 \ge 1+x_i$. Kết hợp đoạn cũ $[1,X]$ với đoạn mới thì sẽ bao phủ được $[1, X + x_i]$
- TH 2: Sẽ bị "lủng" ở giữa, ít nhất là tổng $X+1$ không tạo được.

Lúc mới đầu, ta có $X = 0$. Có thể sort dãy $x$ tăng dần và xét như trên.

## Đếm phân phối
`bool mark[N]`. Gán` mark[v] = true` nếu giá trị $v$ đã xuất hiện, ngược lại `false`
`int cnt[N]`. Ý nghĩa `cnt[v]` là số lần `v` đã xuất hiện. Gán `cnt[v]++` với mỗi giá trị $v$ ta gặp.
Bất kì thông tin gì liên quan, được lưu theo giá trị.

## Collecting Numbers
Đề bài: Lần lượt lấy các số $1,2,3,\dots,n$. Mỗi lượt chỉ được đi từ trái sang phải. Cần bao nhiêu lượt?
pos[v]: vt xuất hiện. pos[v] < pos[v+1]
## Collecting Numbers 2
Xét sự thay đổi của đáp án.
https://cses.fi/paste/cb8b308657ebd68617d3f6/

## Playlist
Hai con trỏ, giải bài toán: "Tìm đoạn dài nhất/ ngắn nhất thỏa mãn tính chất $\alpha$ bất kì".
Bài này kết hợp thêm đếm phân phối.

## Học Two pointer, Binary Search ở đâu?
Vào codeforces.com, mục Edu và đăng ký "ITMO Academy: pilot course".
Sau đó đọc theory và làm practice ở hai phần này.

## Checkpoint 2: C++ STL (set, multiset, map) & Greedy
---
## Concert ticket
### Cách dùng `multiset`

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

void print(multiset<int> s) {
    for (auto val : s) cout << val << ' ';
    cout << '\n';
}

int main()
{
    multiset<int> s({2,2,2,3,3,5,1,4,6,0});
    print(s);
    s.erase(3);
    print(s);
    //iterator
    s.erase(s.find(2));
    print(s);
    //s.erase(s.find(-1)); //RTE
    if (s.count(-1))
        s.erase(s.find(-1));

    //get min
    cout << "Min: " << (*s.begin()) << '\n';
    //get max
    cout << "Max: " << (*s.rbegin()) << '\n';
}

Kết quả:

### TKNP trên set/multiset

auto it = s.upper_bound(x); //phần tử nhỏ nhất > x
if (it != s.end()) cout << (*it); //lấy ra giá trị
lower_bound() thì khác là tìm >= thôi.

### Sol
Bài này dùng TKNP trên multiset và erase dần đi những vé đã được mua.

## Towers
Bài này dùng chiến thuật "Tham lam" (Greedy).
Dùng một multiset lưu kích thước của khối trên cùng mỗi tháp.
Đầu tiên là sort giảm dần. Xét từng khối từ lớn tới bé. TKNP trên multiset, xem thử có tháp nào chứa được nó (lower_bound). Nếu không có thì tạo tháp mới.

## Restaurant
### Cách dùng `map`

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

int main()
{
    map<int,int> mp;
    mp[1] = 5;
    mp[2] = 9;
    mp[5] = 6;
    for (auto info : mp)
        cout << info.first << ' ' << info.second << '\n';
}

Kết quả:
Một cách để hình dung `map` là có thể dùng nó để đếm phân phối với `v` rất lớn ($10^9$)

### Sol
Nén số: Không quan tâm chính xác là ai đã đến hoặc đi vào thời điểm nào, chỉ cần giữ đúng thứ tự trước sau thôi.
Thêm nữa, cần dùng prefix-sum để tính số khách tại một thời điểm bất kì (Mẹo tăng đoạn $[L,R]$ nhanh: `s[L]++, s[R]--`. Sau cùng chạy for và `s[sau] += s[trước]`)

## Maximum Subarray Sum
### Kĩ thuật Prefix Sum
Đặt $s_i$ là tổng $i$ số đầu tiên. Tính bằng công thức $s_i = s_{i-1} + a_i$.
Công thức tính tổng đoạn liên tiếp $[l,r]: s[r] - s[l-1]$
Giải thích: Tổng $r$ số đầu tiên, loại đi $l-1$ số ở đầu.
Xem thêm: https://vnoi.info/wiki/algo/data-structures/prefix-sum-and-difference-array.md
### Sol
Giả sử đang xét đoạn kết thúc tại $i$. Cần tìm $j: 0\le j < i$ để $s_i - s_j$ (tổng của đoạn $[j+1,j+2,\dots,i]$) đạt $\max \rightarrow$ quy về tìm $s_j \min$.

## Movie Festival
###### tags: `QHĐ`
Sort các bộ phim theo $b$ tăng dần. Đặt `f[i]` là số phim nhiều nhất xem được nếu phim cuối cùng ta xem là phim thứ $i$ (trong mảng đã sort).
TKNP để có được $j$ lớn nhất mà $b_j \le a_i$ với mỗi $i$. Có `f[i] = max(f[1..j]) + 1`.
Có thể áp dụng prefix-max?
Solution rất giống bài 2 KC, OLP MTTN 2023: https://lqdoj.edu.vn/problem/olp4ck1b2a/editorial

## Các bài khó hơn
## Josephus 2
Cần mô phỏng lại trò chơi.
Tại mỗi thời điểm, cần:
- tính xem người bị loại tiếp theo đứng thứ mấy trong mảng còn lại?
- xóa một người ra khỏi hàng.

Dùng Segment Tree lưu `cnt` và TKNP trên segment tree (walk)

## Sliding Median và Cost
Tìm trung vị của đoạn "trượt".
Nhận thấy mọi thời điểm ta chỉ "xóa một, thêm một".
Hướng 1: Nén số, sau đó dùng segment tree trên tập các giá trị.
- Cần TKNP
- Với bài cost, cần tính tổng --> lưu thêm thông tin vào mỗi nút

Hướng 2: Dùng hai cái `multiset` đại diện cho tập lớn và tập bé.
- Luôn đảm bảo $\max small \le \min big$
- Kích thước hai tập ngang nhau.