# OAI




[TOC]

## I. Implementation Fundamentals (Whats given by the C++ Language)

### I.1 - Statements

#### I.1-a: Single Statement `...;`

#### I.1-b: Compound Statement `{...}`

#### I.1-c: `if else`

#### I.1-d: `switch case` `case` `default` `[[fallthrough]];`

#### I.1-e: `ternary operator`

#### I.1-f: `while`

#### I.1-g: `do while`

#### I.1-h: `for`

#### I.1-i: `range-for`

vector<int> a;
for (int x : a)
{
    
}

#### I.1-j: `continue`

#### I.1-k: `break`

#### I.1-l: `goto`

#### I.1-m: `return ;` `return <expressions>;`

#### I.1-n: `while(true)` `for (;;)`

#### I.1-o: `for (auto [u, v] : edges)` (C++17)

#### I.1-p: `;` (null statement)

### I.2 - Int Types

#### I.2-a: `int` (>=2 byte)

#### I.2-b: `unsigned int`

#### I.2-c: `long long`

#### I.2-d: `unsigned long long`

#### I.2-e: `short`

#### I.2-f: `unsigned short`

#### I.2-g: `int8_t`

#### I.2-h: `int16_t`

#### I.2-i: `int32_t`

#### I.2-j: `int64_t`

#### I.2-k: `uint8_t`

#### I.2-l: `uint16_t`

#### I.2-m: `uint32_t`

#### I.2-n: `uint64_t`

#### I.2-o: `size_t`

#### I.2-p: `ssize_t` (C++20)

### I.3 - Float Types

#### I.3-a: `float`

#### I.3-b: `double`

#### I.3-c: `long double`

### I.4 - Char & String Types

#### I.4-a: `char`

#### I.4-b: `signed char`

#### I.4-c: `unsigned char`

#### I.4-d: `string`

#### I.4-e: `string_view`

#### I.4-f: `fstream`

#### I.4-g: `ifstream`

#### I.4-h: `ofstream`

#### I.4-i: `stringstream`

#### I.4-j: `istringstream`

#### I.4-k: `ostringstream`

#### I.4-l: `char8_t` (C++20)

#### I.4-m: `char16_t`

#### I.4-n: `char32_t`

#### I.4-o: `istream`

#### I.4-p: `ostream`

#### I.4-q: `cin`

#### I.4-r: `cout`

#### I.4-s: `cerr`

#### I.4-t: `clog`

#### I.4-u: `Escape Character ('\n', '\\', '\'', '\"', ...)`

#### I.4-v: `Escape Sequence ('\nnn', '\o{nnn}', '\xnnn', '\x{nnn}', ...)`

#### I.4-w: `wchar_t`

#### I.4-x: `wcin`

#### I.4-y: `wcout`

### I.5 - Bool & Bit

#### I.5-a: `bool`

#### I.5-b: `byte` (C++17)

#### I.5-c: `vector<bool>`

#### I.5-d: `bitset<SIZE>`

### I.6 - Literals

#### I.6-a: `Long Literal (1L)`

#### I.6-b: `Unsigned Long Literal (1U)`

#### I.6-c: `Long Long Literal (1LL)`

#### I.6-d: `Unsigned Long Long Literal (1ULL)`

#### I.6-f: `Size Literal (1UZ)` (C++23)

#### I.6-g: `Signed Size Literal (1Z)` (C++23)

#### I.6-h: `Octal Literal (0123)`

#### I.6-i: `Hex Literal (0x123)`

#### I.6-j: `Binary Literal (0b101)`

#### I.6-k: `Float Literal (.1f)`

#### I.6-l: `Double Literal (.1)`

#### I.6-m: `Long Double Literal (.1L)`

#### I.6-n: `Char Literal ('\n')`

#### I.6-o: `String Literal ("abc")`

#### I.6-p: `Raw String Literal (R"(raw\nstring)")`

#### I.6-q: `Boolean Literal (true/false)`

#### I.6-r: `Digit Separator (123'456'789)`

### I.7 - Cast

#### I.7-a: C Cast `(Type)(Data)`

#### I.7-b: Static Cast `static_cast<Type>(Data)`

#### I.7-c: Const Cast `const_cast<Type>(Data)`

#### I.7-d: Reinterpret Cast: `reinterpret_cast<Type>(Data)`

#### I.7-e: Dynamic Cast: `dynamic_cast<Type>(Data)`

#### I.7-f: Bit Cast: `std::bit_cast`

### I.8 - Scoping

#### I.8-a: Global Scope `::x`

#### I.8-b: Variable Shadowing

#### I.8-c: Namespace `namespace`

#### I.8-d: Nameless Namespace `namespace`

#### I.8-e: Static Storage Duration `static` (deprecated `register`)

#### I.8-f: Static Constant Expressive `constexpr` `constinit` (C++20)

#### I.8-g: Thread Storage Duration `thread_local`

#### I.8-h: Dynamic Storage Duration (`new`, `new[]`, `delete`, `delete[]`)

#### I.8-i: Automatic Storage Duration (no `static`, no `thread_local`, no `new`, no `new[]`)

#### I.8-j: External Linkage (`inline`, `extern`)

#### I.8-k: Internal Linkage

#### I.8-l: No Linkage

#### I.8-m: Block Scope `{...}`

#### I.8-n: Class Struct Scope (Access Specifier: `public:`, `private:`, `protected:`)

#### I.8-o: Lifetime

### I.9 - Initialization

#### I.9-a: Default Initialization `int x;`

#### I.9-b: Value Initialization `int x{};`

#### I.9-c: Zero Initialization `static int x;`

#### I.9-d: Copy Initialization `int x = 0;`

#### I.9-e: Direct Initialization `int x(0);`

#### I.9-f: Scalar List Initialization `int x = {0};` (Narrowing Safe)

#### I.9-g: Copy List Initialization `vector<int> x = vector<int>{0, 0};`

#### I.9-h: Direct List Initialization `vector<int> x{0, 0};`

#### I.9-i: Initializer List Initialization `std::initializer_list<T> var = {..};`

#### I.9-j: Reference Initialization `int &x = dp[const_cat][const_card][const_cart];`

#### I.9-k: Constant Initialization `const int x = 0;`

#### I.9-l: Array Initialization `int x[2]{};`

#### I.9-m: Dynamic Initialization `int *x = new int(0);` (`new`)

#### I.9-n: Zero-Fill Array Initialization `int *x = new int[2]();` `(new[])`

#### I.9-o: Dynamic Array Initialization `int *x = new int[2]{0,0};` `(new[])`

#### I.9-p: Member Initialization `struct Int { int member; Int(int param) : member(param) {} }`

#### I.9-q: Default Member Initialization `struct Int{ int member = 0; }` (NSDMI)

#### I.9-r: String Literal Initialization `const char name[] = "SPy";` (utf8, unicode, wchar, signed char, unsigned chah, char)

#### I.9-s: Structured Binding Initialization `for (auto [u, v] : edges) {}`

#### I.9-t: Control Flow Initialization `if (int x = 0; x > 0) {}`

#### I.9-u: Partial Aggregate Initialization `int x[5]{1, 2};`

#### I.9-v: Direct Aggregate Initialization `Pair p(1, 2);`

#### I.9-w: Designated Initialization `Pair x = { .first = 1, .second = 2 };` (C++20)

#### I.9-x: Designated Aggregate Initialization `T object = { .var1 = arg1, .var2 { arg2 } }`

#### I.9-y: Lambda Capture Initialization `auto test = [&bind=target](){};`

#### I.9-z: Pointer Null Initialization `int *ptr{};`

### I.10 - Unary Operators

#### I.10-a: `+X` `Unary Plus`

#### I.10-b: `-X` `Unary Minus`

#### I.10-c: `!X` `Negation`

#### I.10-d: `~X` `Bitwise NOT`

#### I.10-e: `++X` `Pre Increment`

#### I.10-f: `--X` `Pre Decrement`

#### I.10-g: `X++` `Post Increment`

#### I.10-h: `X--` `Post Decrement`

### I.11 - Arithmetic Operators

#### I.11-a: `A+B` `Addition` `Plus`

#### I.11-b: `A-B` `Subtraction` `Minus`

#### I.11-c: `A*B` `Multiplication` `Multiply`

#### I.11-d: `A/B` `Division` `Div`

#### I.11-e: `A%B` `Remainder` `Mod`

#### I.11-f: `A+=B` `Assignment Addition`

#### I.11-g: `A-=B` `Assignment Subtraction`

#### I.11-h: `A*=B` `Assignment Multiplication`

#### I.11-i: `A/=B` `Assignment Division`

#### I.11-j: `A%=B` `Assignment Remainder`

### I.12 - Comparison Operators

#### I.12-a: `A<B` `Less` `LE`

#### I.12-b: `A<=B` `Less Or Equal` `LEQ`

#### I.12-c: `A>B` `Greater` `GE`

#### I.12-d: `A>=B` `Greater Or Equal` `GEQ`

#### I.12-e: `A==B` `Equal` `EQ`

#### I.12-f: `A!=B` `Not Equal` `NEQ`

#### I.12-g: `A<=>B` `Three-way` `Spaceship Operator`

### I.13 - Logic Operators

#### I.13-a: `A&&B` `Logic And`

#### I.13-b: `A||B` `Logic Or`

#### I.13-c: `There is no Logic Xor Operator`

#### I.13-d: `Short Circuit`

### I.14 - Bitwise Operators

#### I.14-a: `A<<B` `Shift Left`

#### I.14-b: `A>>B` `Shift Right`

#### I.14-c: `A^B` `XOR`

#### I.14-d: `A&B` `AND`

#### I.14-e: `A|B` `OR`

#### I.14-f: `A<<=B` `Assignment Shift Left`

#### I.14-g: `A>>=B` `Assignment Shift Right`

#### I.14-h: `A^=B` `Assignment XOR`

#### I.14-i: `A&=B` `Assignment AND`

#### I.14-j: `A|=B` `Assignment OR`

#### I.14-k: `~A` `UNARY NOT`

### I.15 - Operator Overloadding

#### I.15-a: Unoverloadable Operators `::`, `.`, `.*`, `?:`

#### I.15-b: Custom Assignment Operator `=`

#### I.15-c: Custom Function Call Operator `()`

#### I.15-d: Custom Subscript Operator `[]`

#### I.15-e: Custom Multidimensional Subscript Operator (comma operator, `C++23 []`)

#### I.15-f: Custom Logic And Operator `&&`

#### I.15-g: Custom Logic And Operator `||`

#### I.15-h: Custom Comma Operator `,`

#### I.15-i: Custom Member Access Operator `->`

#### I.15-j: Custom Pointer Member Access Operator `->*`

#### I.15-k: Custom New Operator `new` `new[]`

#### I.15-l: Custom Delete Operator `delete` `delete[]`

#### I.15-m: User-defined Literals Operator `""_s()`

#### I.15-n: Explicit Conversion Operator `explicit operator T()`

#### I.15-o: Boolean Explicit (Supressing Implicit Conversion) Operator `explicit operator bool()`

#### I.15-z: Comparison Suite: `strong ordering`, `partial ordering`, `poset`

### I.16 - Order

#### I.16-a: Operator Prescedence

#### I.16-b: Evaluation Order

#### I.16-c: Sequence Cases

#### I.16-d: Assignment Sequence Points

#### I.16-e: Function Call Arguments Order

#### I.16-f: Order of Evaluation

auto ReadInt() -> int {
    int x;
    cin >> x;
    return x;
}

int x = ReadInt();
int l = ReadInt(), r = ReadInt();
pair<int, int> q = pair<int, int>(l, r);
pair<int, int> p = pair<int, int>(ReadInt(), ReadInt());
cout << x << "\n" << p.first << " " << p.second << "\n";

txt.input
1
2 3
2 3
    
txt.output
1
3 2

#### I.16-g: Lexicographical Order

### I.17 - Enum

#### I.17-a: Enum

#### I.17-b: Enum Class

#### I.17-c: Enum Size

### I.18 - Template

#### I.18-a: Generic

#### I.18-y: TMP

#### I.18-z: SFINAE

### I.19 - Preprocessor

#### I.19-a: `#include`

#### I.19-b: `#define`

#### I.19-c: `#ifdef` `#ifndef` `#endif` `#else` `#if` `#elif`

#### I.19-d: `#pragma`

#### I.19-e: `#line`

#### I.19-f: `#warning`

#### I.19-g: `#error`

#### I.19-h: Build Flags (`-O2`, `-pipe`, `-static`, `-Wall`, `-Wextra`)

### I.20 - IO

#### I.20-a: `ios::sync_with_stdio(false);`

#### I.20-b: `cin.tie(nullptr);`

#### I.20-c: `cout.tie(nullptr);`

#### I.20-d: FastIO (`getchar`, `putchar`)

#### I.20-e: Unsafe FastIO (`getchar_unlocked`, `putchar_unlocked`)

### I.21 - Math

#### I.21-a: `abs()`

#### I.21-b: `gcd()`

#### I.21-c: `lcm()`

#### I.21-d: `min()`

#### I.21-e: `max()`

#### I.21-f: `sqrt()`

#### I.21-g: `pow()`

### I.22 - Debug

#### I.22-a: Runtime Assert

#### I.22-b: Static Assert

### I.23 - Include

#### I.23-a: `<bits/stdc++.h>`

#### I.23-b: Free Standing Library

### I.24 - STL

#### I.24-a: `std::array`

#### I.24-b: `std::vector`

### I.25 - Alias

#### I.25-a: `using`

using ll = long long;

template<typename T>
using Vec = std::vector<T>;

Vec<int> a; // std::vector<int> a;
Vec<char> b; // std::vector<char> b;

using namespace std;
using std::cout;

#### I.25-b: `typedef`

typedef long long ll;

#### I.25-c: `lvalue&`

const int LIM = 2e5 + 25;
long long dp[LIM];
auto f(int i, int j, int k, 
       int upperR, int lowerR, bool ilzr, bool itzr, 
       int upperL, int lowerL, bool ilzl, bool itzl
) -> long long
{
    if (i <= 0) {
        return 1;
    }
    
    auto &res = dp[i][j][k][upperR][lowerR][ilzr][itzr][upperL][lowerL][ilzl][itzl];
    if (res != -1) {
        return res;
    }
    
    res = f(i - 1) * i;
    return res;
}

memset(dp, -1, sizeof(dp));

### I.26 - Constants & Enums

#### I.26-a: Constants

####

### I.27 - Time

#### I.27-a: `<chrono>`

#### I.27-b: `system_clock`

- Timestamps, logging, current time

[[03:37]] NPDang: steady ?
[[03:38]] NPDang: ờ ;-;
...
[[05:00]] NPDang: gg jg gap

#### I.27-c: `steady_clock`

- Duration, benchmark, elapsed time

#### I.27-d: `high_resolution_clock`

-> Cook

### I.28 - Random

### I.29 - Filesystem

### I.30 - Templates

#### I.30-a: Generic

#### I.30-b: TMP

#### I.30-c: SFINAE

## II. Implementation (Đề hỏi gì làm nấy)

### II.1 - Bitmask

#### II.1-a: `IsZero(X)`

> Có thể dùng cùng một phương pháp cho các kiểu khác nhau như `bool`, `int`, `float` không ?

> IsZero("0") co tinh la true khong ? Neu phai cai so lon (BigNum) thi em se kiem tra nhu nao ?

> IsZero("") = True hay False ? Vì sao ? Giải thích và phân biệt giữa 0 và NULL ?

#### II.1-b: `IsOdd(X)` `IsEven(X)`

> Tìm một ví dụ mà ở đó cả `IsOdd(X)` lẫn `IsEven(X)` đều trả về false (nếu tồn tại) ?

> Hai hàm trên có thể dùng để test các kiểu khác nhau như `bool` `int` `float` không ?

> Với `int X=2` -> `bool(X)==true` thì lúc này `IsOdd(bool(X))` nên trả về gì ? True hay False ?

#### II.1-c: `IsPowerOfTwo(X)`

#### II.1-d: `IsPowerOfFour(X)` `IsPowerOfPowerOfTwo(X, K)`

#### II.1-e: `CheckBit(X, B)` `SetBit(X, B)` `UnsetBit(X, B)` `ToggleBit(X, B)`

#### II.1-f: `AssignBit(X, B, V)`

#### II.1-g: `ToBinary(X)` `ToOctet(X)` `ToHex(X)`

#### II.1-h: `FullMask(X)`

> `FullMask(X) = ((X == 64) ? (~ULL) : ((1ULL << X)-1))`

#### II.1-i: `XorSwap(X, Y)`

#### II.1-j: `BitLength(X)` `Log2(X)`

#### II.1-k: `CountSetBit(X)` `CountUnsetBit(X)`

#### II.1-l: `CountTrailingZero(X)` `CountTrailingOne(X)`

#### II.1-m: `CountLeadingZero(X)` `CountLeadingOne(X)`

#### II.1-n: `LeastSignificantBit(X)` `MostSignificantBit(X)`

#### II.1-o: `BitLeftRotation(X, N)` `BitRightRotation(X, N)`

#### II.1-p: `SubmaskEnumeration(X)`

#### II.1-q: `SignOf(X)` `IsPositive(X)` `IsNegative(X)` `HasOppositeSign(X, Y)`

#### II.1-r: `IsolateLowestSetBit(X)` `ClearLowestSetBit(X)`

> `IsolateLowestSetBit(X) = (X & -X)`
> `ClearLowestSetBit(X) = (X & (X-1))`

#### II.1-t: `BitAbs(X)`

#### II.1-u: `BitMin(X, Y)` `BitMax(X, Y)`

#### II.1-v: `LexicoNextBitPermutation(X)` `LexicoPrevBitPermutation(X)`

#### II.1-w: `NextPowerOfTwo(X)` `PrevPowerOfTwo(X)`

#### II.1-x: `GrayCode(X)` `InverseGrayCode(X)`

#### II.1-x: `ReverseBit(X)`

#### II.1-z: `GenAllBinary(N)` `GenAllTernary(N)` `GenAllQuaternary(N)` `GenAllGrayCode(N)`

### II.2 - Bitmask Bultin

#### II.2-a: `Count Set Bit` `__builtin_popcount**(X)` `(**=NULL,L,LL)`

#### II.2-b: `Count Trailing Zeros` `__builtin_ctz**(X)` `(**=NULL,L,LL)`

#### II.2-c: `Count Leading Zeros` `__builtin_clz**(X)` `(**=NULL,L,LL)`

#### II.2-d: `Parity Check` `__builtin_parity**(X)` `(**=NULL,L,LL)`

#### II.2-e: `Least Significant Setbit` `__builtin_ffs**(X)` `(**=NULL,L,LL)`

#### II.2-f: `Bit Left Rotation` `__builtin_rotateleft**(X, N)` `(**=8,16,32,64)`

#### II.2-g: `Bit Right Rotation` `__builtin_rotateright**(X, N)` `(**=8,16,32,64)`

#### II.2-h: `Bit Swap Endians` `__builtin_bswap**(X)` `(**=8,16,32,64)`

### II.3 - Modular Arithmetic

#### II.3-a: `ModFix(A, P)` $= A \mod P$

#### II.3-b: `ModNeg(A, P)` $= (-A) \mod P$

#### II.3-c: `ModInc(A, P)` $= (A+1) \mod P$

#### II.3-d: `ModDec(A, P)` $= (A-1) \mod P$

#### II.3-e: `ModInv(A, P)` $= (A^{-1}) \mod P$

> Điều kiện thường gặp: $P$ Nguyên tố

#### II.3-f: `ModFib(N, P)` $= \left(Fibonacci(N)\right) \mod P$

#### II.3-g: `ModLucas(N, P)` $= \left(Lucas(N)\right) \mod P$

#### II.3-h: `ModFact(N, P)` $= \left(N!\right) \mod P$

#### II.3-i: `ModInvFact(N, P)` $= \left(N!\right)^{-1} \mod P$

#### II.3-j: `ModAdd(A, B, P)` $= (A+B) \mod P$

#### II.3-k: `ModSub(A, B, P)` $= (A-B) \mod P$

#### II.3-l: `ModMul(A, B, P)` $= (A\times B) \mod P$

#### II.3-m: `ModDiv(A, B, P)` $= (A\div B) \mod P$

> Điều kiện thường gặp: $P$ Nguyên tố

#### II.3-n: `ModPow(X, N, P)` $= \left(X^N\right) \mod P$

#### II.3-o: `DivFloor(X, Y)` $= \left\lfloor\dfrac{X}{Y}\right\rfloor$

#### II.3-p: `DivCeil(X, Y)` $= \left\lceil\dfrac{X}{Y}\right\rceil$

#### II.3-q: `DivRound(X, Y)` $= \left[\dfrac{X}{Y}\right]$

#### II.3-r: `GCD(X, Y)` $= max(G\ |\ X ⋮ G \wedge Y ⋮ G \wedge G \in \mathbb{Z}^+)$

#### II.3-s: `LCM(X, Y)` $= max(G\ |\ L ⋮ X \wedge L ⋮ Y \wedge L \in \mathbb{Z}^+)$

#### II.3-t: `ExtGCD(X, Y)` $= (G,P,Q)\ \text{satisfied} (P*X+Q*Y=G=GCD(X,Y))$

> $(G,P,Q\in\mathbb{Z})^+)$

#### II.3-u: `ModAnk(N, K, P)` $= \left({\Large A}^K_N\ \right) \mod P = ((N!) \div (N-K)!) \mod P$

#### II.3-v: `ModCnk(N, K, P)` $= \left({\Large C}^K_N\ \right) \mod P = \left({\Large A}^K_N\ \div K!\right) \mod P$

#### II.3-w: `ModEq(A, B, P)` $\Leftrightarrow (A \equiv B) \pmod P$

#### II.3-x: `ModPow2(N, P)` $= 2^N \mod P$

#### II.3-y: `ModSquare(X, P)` $= X^2 \mod P$

#### II.3-z: `ModDiv2(X, P)` $= (X \div 2) \mod P$

> $P$ lẻ

### II.4 - Number Theory

#### II.4-a: `IsSquare(X) -> bool`

> Kiểm tra xem X có phải là số chính phương không ?

#### II.4-b: `IsCube(X) -> bool`

> Kiểm tra xem X có phải là số lập phương không ?
>
#### II.4-c: `IsKthRoot(X, K) -> bool`

> Kiểm tra xem X có phải là số dạng $U^K$ với số nguyên $U$ nào đó không ?

#### II.4-d: `SqrtFloor(X) -> int`

> Tìm số nguyên dương $U$ lớn nhất sao cho $U^2 \leq X$

#### II.4-e: `SqrtCeil(X) -> int`

> Tìm số nguyên dương $U$ nhỏ nhất sao cho $U^2 \geq X$

#### II.4-f: `IsSqrtOf(X, N) -> bool`

> Kiểm tra xem $X^2 = N$ là đúng hay sai ?

#### II.4-g: `IsPrime(X) -> bool`

> Kiểm tra xem X có phải là số nguyên tố hay không ?

#### II.4-h: `PrimeSieve(N) -> vector`

> Sàng nguyên tố các số $[1..N]$ để đưa ra danh sách các số nguyên tố trong đoạn

#### II.4-i: `DivisorsOf(X) -> vector`

> Đưa ra danh sách các ước nguyên dương của $X$

#### II.4-j: `PrimeFactorsOf(X) -> vector`

> Đưa ra danh sách các ước nguyên tố dương của $X$

#### II.4-k: `LPF(X) = LowestPrimeFactorsOf(X) -> int`

> Tìm số nguyên tố nhỏ nhất của $X$

#### II.4-l: `Tau(X) = DivisorCountOf(X) -> int`

> Đếm số ước của X

#### II.4-m: `Sig(X) = DivisorSumOf(X) -> int`

> Tính tổng các ước của X

#### II.4-n: `Factorize(X) -> map`

> Phân tích thừa số nguyên tố $X=p_2^{f_2}\times p_3^{f_3}\times p_5^{f_5}\times \ldots$
> Đưa ra map dạng $\{(p_2,f_2), (p_3,f_3), (p_5,f_5),\ldots\}$
> Sao cho $f_2, f_3, f_5, \ldots \in \mathbb{Z}^+$, nếu $f_n = 0$ thì ko cần cặp $(p_n, f_n)$ trong map

#### II.4-o: `Phi(X) = EulerTotient(X) -> int`

> Tính hàm Phi

#### II.4-p: `Factorial(N) -> int`

> Tìm giai thừa thứ N

#### II.4-q: `IsFactorial(N) -> bool`

> Kiểm tra xem N có phải là một giai thừa hay không

#### II.4-r: `Vp(N, P) = PadicValuation(N, P) -> int`

> Số mũ của $p$ trong $N$
>
#### II.4-s: `Legendre(N, P) = PadicValuation(Factorial(N), P) -> int`

> Số mũ của $p$ trong $N!$

#### II.4-t: `LDE(A, B, C) = pair`

> Tìm cặp nghiệm $(X, Y)$ thoả $AX + BY = C$ hoặc trả về $(-1, -1)$ nếu không tồn tại

> aka Divisor Summatory Function

#### II.4-u: `IsCoprime(A, B) -> bool`

> Kiểm tra xem (A, B) có nguyên tố cùng nhau không

#### II.4-v: `DigitLength(X) -> int`

> Đếm số chữ số của $X$ trong hệ thập phân

#### II.4-w: `DigitReverse(X) -> int`

> Đảo các chữ số của $X$ trong hệ thập phân

#### II.4-x: `SquareFree(X) -> int`

> Tìm ước không chính phương lớn nhất của $X$ hoặc $1$ nếu không tồn tại

#### II.4-z: `PrevPrime(X) -> int`

> Tìm số nguyên tố trước đó nhỏ hơn x

#### II.4-z: `NextPrime(X) -> int`

> Tìm số nguyên tố tiếp theo lớn hơn x

### II.5 - String Basics

- Những hàm kiểm tra tính toán căn bản trong xâu

#### II.5-a: `Length(s) -> int`

Tính độ dài xâu s

#### II.5-b: `IsEmpty(s) -> bool`

Kiểm tra xem xâu s có rỗng không

#### II.5-c: `IsPalindrome(s) -> bool`

Kiểm tra xem xâu s có đối xứng không

#### II.5-d: `IsPalindromeInsensitive(s) -> bool`

Kiểm tra xem xâu s có đối xứng không, coi các kí tự in hoa in thường như nhau

#### II.5-e: `IsBalancedBracket(s) -> bool`

Kiểm tra xem xâu s có cân bằng ngoặc hay không

#### II.5-f: `IsStringPower(s) -> bool`

Kiểm tra xem xâu s có phải là xâu mũ hay không

#### II.5-f: `Contains(s, c) -> bool`

Kiểm tra xem xâu s có chứa kí tự c hay không ?

#### II.5-g: `ContainsAny(s, vector char) -> bool`

Kiểm tra xem xâu s có chứa bất kì kí tự nào trong dãy hay không ?

#### II.5-h: `ContainsAll(s, vector char) -> bool`

Kiểm tra xem xâu s có chứa đủ tất cả kí tự nào trong dãy hay không ?

#### II.5-i: `Contains(s, t) -> bool`

Kiểm tra xem xâu s có chứa xâu con t hay không ?

#### II.5-j: `ContainsAny(s, vector string) -> bool`

Kiểm tra xem xâu s có chứa bất kì xâu con nào trong dãy hay không ?

#### II.5-k: `ContainsAll(s, vector char) -> bool`

Kiểm tra xem xâu s có chứa đủ tất cả xâu con nào trong dãy hay không ?

### II.6 - String Search

- Mấy bài toán liên quan tới tìm kiếm hoặc đếm kí tự, xâu, xâu con

#### II.6-a: `FindFirst(s, c) -> int|-1`

Tìm vị trí đầu tiên xuất hiện kí tự c trong xâu s, hoặc in ra -1 nếu không tìm được

#### II.6-b: `FindFirst(s, c, l, r) -> int|-1`

Tìm vị trí đầu tiên xuất hiện kí tự c trong xâu s[l..r], hoặc in ra -1 nếu không tìm được

#### II.6-c: `FindLast(s, c) -> int|-1`

Tìm vị trí cuối cùng xuất hiện kí tự c trong xâu s, hoặc in ra -1 nếu không tìm được

#### II.6-d: `FindLast(s, c, l, r) -> int|-1`

Tìm vị trí cuối cùng xuất hiện kí tự c trong xâu s[l..r], hoặc in ra -1 nếu không tìm được

#### II.6-e: `FindAll(s, c) -> vector int`

Tìm tất cả vị trí xuất hiện kí tự c trong xâu s

#### II.6-f: `FindAll(s, c, l, r) -> vector int`

Tìm tất cả vị trí xuất hiện kí tự c trong xâu s[l..r]

#### II.6-g: `FindFirstOf(s, vector char) -> int|-1`

Tìm kí tự đầu tiên có trong dãy trong xâu, hoặc -1 nếu không tìm thấy

#### II.6-h: `FindFirstNotOf(s, vector char) -> int|-1`

Tìm kí tự đầu tiên không có trong dãy trong xâu, hoặc -1 nếu không tìm thấy

#### II.6-i: `FindLastOf(s, vector char) -> int|-1`

Tìm kí tự cuối cùng có trong dãy trong xâu, hoặc -1 nếu không tìm thấy

#### II.6-k: `FindLastNotOf(s, vector char) -> int|-1`

Tìm kí tự cuối cùng không có trong dãy trong xâu, hoặc -1 nếu không tìm thấy

#### II.6-k: `Count(s, c) -> int`

Đếm số lần xuất hiện của kí tự c trong xâu s

#### II.6-l: `Count(s, c, l, r) -> int`

Đếm số lần xuất hiện của kí tự c trong xâu s[l..r]

#### II.6-m: `Count(s, t) -> int`

Đếm số lần xuất hiện của xâu t trong xâu s

#### II.6-n: `Count(s, vector char) -> int`

Đếm tổng số lần xuất hiện của các kí tự c trong vector trong xâu

#### II.6-o: `AlphabetSize(s) -> int`

Đếm số kí tự khác nhau trong xâu

### II.7 - String Operation

- Hàm mà có thay đổi xâu, trả về xâu, tính toán xâu

#### II.7-a: `Reverse(s) -> string`

Đảo lại thứ tự của xâu s

#### II.7-b: `RotateRight(s, k=1) -> string`

Xoay xâu s sang bên phải 1 đơn vị

#### II.7-c: `RotateLeft(s, k=1) -> string`

Xoay xâu s sang bên trái 1 đơn vị

#### II.7-d: `ToLower(s) -> string`

Đưa tất cả các kí tự in hoa (A-Z) về in thường (a-z)

#### II.7-e: `ToUpper(s) -> string`

Đưa tất cả các kí tự in hoa (a-z) về in thường (A-Z)

#### II.7-f: `TrimLeft(s, spaces=" \t\n") -> string`

Xoá tất cả các kí tự c thuộc spaces bên trái cùng xâu

#### II.7-g: `TrimRight(s, spaces=" \t\n") -> string`

Xoá tất cả các kí tự c thuộc spaces bên phải xâu

#### II.7-h: `Trim(s, spaces=" \t\n") -> string`

Xoá tất cả tất cả các kí tự c thuộc spaces bên trái cùng hoặc bên phải cùng xâu

#### II.7-i: `SpaceCollapse(s, spaces=" \t\n") -> string`

Biến 2 kí tự kề nhau thuộc spaces trong xâu s về một kí tự (xoá kí tự trùng kề nhau)

#### II.7-j: `Capitalize(s) -> string`

Làm in hoa chữ cái đầu và in thường những chữ cái kề sau cho các đoạn từ

#### II.7-k: `Normalize(s) -> string`

Xoá các dấu tận cùng của s, xoá các dấu kề trùng, làm in hoa đầu, in thường còn lại

`Capitalize(SpaceCollapse(Trim(s)))`

#### II.7-l: `EraseBack(s) -> string`

Xoá kí tự cuối trong xâu

#### II.7-m: `EraseFront(s) -> string`

Xoá kí tự đầu tiên trong xâu

#### II.7-n: `Erase(s, p) -> string`

Xoá kí tự tại vị trí p trong xâu

#### II.7-o: `Erase(s, l, r) -> string`

Xoá một đoạn xâu s[l..r]

#### II.7-p: `EraseFirst(s, t) -> string`

Xoá đoạn xâu giống t (pattern) đầu tiên xuất hiện trong xâu s (text)

#### II.7-q: `EraseLast(s, t) -> string`

Xoá đoạn xâu giống t (pattern) cuối cùng xuất hiện trong xâu s (text)

#### II.7-r: `EraseAll(s, t) -> string`

Xoá tất cả các đoạn xâu giống t (pattern) xuất hiện trong xâu s (text)

#### II.7-s: `Erase(s, l, r, t, u, v) -> string`

Xoá tất cả các đoạn xâu giống t[u..v] (pattern) xuất hiện trong xâu s[l..r] (text)

#### II.7-t: `EraseBack(s) -> string`

Xoá kí tự cuối trong xâu

#### II.7-u: `ReplaceFirst(s, c, v) -> string`

Thay thế kí tự đầu tiên c trong xâu s thành kí tự v

#### II.7-v: `ReplaceLast(s, c, v) -> string`

Thay thế kí tự cuối cùng c trong xâu s thành kí tự v

#### II.7-w: `ReplaceAll(s, c, v) -> string`

Thay thế tất cả kí tự c trong xâu s thành kí tự v

### II.8 - String Partition

- Hàm mà có chia tách ra làm các xâu con, hoặc ghép nói thành một xâu to hơn

#### II.8-a: `StringPower(s, k) -> string`

Ghép k xâu s lại với nhau

#### II.8-b: `StringPrimitive(s) -> string`

Tìm xâu con bên trái cùng của s, gồm ít kí tự nhất, mà có thể ghép nhiều lần thành s

Nếu `x=StringPrimitive(s)`, thì tồn tại $k \in \mathbb{N}$ để `s=StringPower(x, k)`

#### II.8-c: `MinimalPeriod(s) -> int`

Độ dài của `StringPrimitive(s)`

$\Leftrightarrow$ `StringPrimitive(s)=Substring(s,MinimalPeriod(s))`

#### II.8-d: `Substring(s, n) -> string`

Lấy n kí tự đầu tiên của xâu s khi $n>0$, hoặc lấy |n| kí tự cuối khi $n<0$

#### II.8-e: `Substring(s, n, p) -> string`

Lấy n kí tự kể từ vị trí p trong xâu s, lấy sang trái nếu n âm, sang phải nếu n dương

#### II.8-f: `Substring(s, pair(l, r)) -> string`

Lấy một đoạn xâu con đoạn s[l..r]

#### II.8-g: `Concat(s, t) -> string`

Nối hai xâu lại với nhau thành một xâu

#### II.8-h: `Split(s, pos) -> vector string`

Ngắt xâu không rỗng tại vị trí pos

#### II.8-i: `Split(s, char) -> vector string`

Ngắt xâu không rỗng tại tất cả các kí tự char

#### II.8-j: `Split(s, delims) -> vector string`

Ngắt xâu không rỗng tại tất cả các kí tự c thuộc delims

#### II.8-k: `Join(vector string, delim) -> string`

Nối các xâu trong vector lại, giữa hai xâu sẽ có một kí tự delim

### II.9 - String Encoding & Decoding

### II.10 - Interval Fundamentals

#### II.10-a: `IsValidInterval((L, R)) -> bool`

Kiểm tra xem đoạn `[L, R]` có hợp lệ không ? ($L \le R$)

#### II.10-b: `IsInvalidInterval((L, R)) -> bool`

Đoạn `[L, R]` thì không hợp lệ phải không ? ($L \le R$)

#### II.10-c: `IsNormalized((L, R)) -> bool`

Kiểm tra xem đoạn `(L, R)` đã được chuẩn hoá chưa

#### II.10-d: `IsUnnormalized((L, R)) -> bool`

Kiểm tra xem đoạn `(L, R)` đã được chuẩn hoá chưa

#### II.10-e: `Norm((L, R)) -> (l, r)`

Trả về đoạn hợp lệ từ `l = min(L, R)` tới `r = max(L, R)`

Nếu đoạn rỗng thì chuẩn hoá về `(1, 0)`

#### II.10-f: `Size((L, R)) -> int|-1`

Trả về độ dài của khoảng từ L tới R, hoặc -1 nếu không hợp lệ

Lấy `R - L` hoặc `-1`

#### II.10-g: `CountCoverPoint((L, R)) -> int|-1`

Trả về số số nguyên trong đoạn `[L, R]`, hoặc -1 nếu không hợp lệ

Lấy `floor(R) - ceil(L) + 1` hoặc `-1`

#### II.10-h: `Midpoint((L, R)) -> int|float`

Trả về tâm, điểm nằm chính giữa đoạn `[L, R]`

#### II.10-i: `Left((L, R)) -> int|float`

Trả về điểm biên bên trái đoạn `[L, R]`

#### II.10-j: `Right((L, R)) -> int|float`

Trả về điểm biên bên phải đoạn `[L, R]`

#### II.10-k: `CanonicalEmptyInterval() -> (l, r)`

Trả về đoạn chuẩn cho việc chuẩn hoá đoạn rỗng

Trả về `(1, 0)`

### II.11 - Interval & Scalar/Points

#### II.11-a: `IsInside(x, (L, R)) -> bool`

Kiểm tra xem X có nằm trong đoạn `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-b: `IsStrictInside(x, (L, R)) -> bool`

Kiểm tra xem X có nằm trong khoảng `(L, R)` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-c: `IsOutside(x, (L, R)) -> bool`

Kiểm tra xem X có nằm ngoài đoạn `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-d: `IsSoftOutside(x, (L, R)) -> bool`

Kiểm tra xem X có nằm ngoài khoảng `(L, R)` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-e: `IsLeftOf(x, (L, R)) -> bool`

Kiểm tra xem X có nằm bên trái điểm biên trái `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-f: `IsSoftLeftOf(x, (L, R)) -> bool`

Kiểm tra xem X có nằm ở trên hay bên trái của điểm biên trái `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-g: `IsLeftmost(x, (L, R)) -> bool`

Kiểm tra xem X có nằm ở trên điểm biên trái `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-h: `IsRightOf(x, (L, R)) -> bool`

Kiểm tra xem X có nằm bên phải điểm biên phải `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-i: `IsSoftRightOf(x, (L, R)) -> bool`

Kiểm tra xem X có nằm ở trên hay bên phải của điểm biên phải `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-j: `IsRightmost(x, (L, R)) -> bool`

Kiểm tra xem X có nằm ở trên điểm biên phải `[L, R]` hay không ?

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-k: `Distance((L, R), x) -> int`

Khoảng cách từ một đoạn `[L, R]` tới điểm `x`

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-l: `ProjectPoint((L, R), x) -> int`

Điểm gần nhất trong hai đầu của đoạn `[L, R]` tới `x`

Nếu `L > R` tức là đoạn rỗng và luôn trả về true

#### II.11-m: `KthPointFromLeft((L, R), k) -> int`

Tìm điểm nguyên thứ `k` từ bên trái qua trên đoạn `[L, R]`

Nếu `L > R` tức là đoạn rỗng và luôn trả về

#### II.11-n: `KthPointFromRight((L, R), k) -> int`

Tìm điểm nguyên thứ `k` từ bên phải qua trên đoạn `[L, R]`

#### II.11-o: `Shift((L, R), d) -> (l, r)`

Dời đoạn [L, R] một khoảng `d`

Trả về `[L+d, R+d]`

#### II.11-p: `Expand((L, R), d) -> (l, r)`

Mở rộng [L, R] một khoảng `d` về hai phía

Trả về `[L-d, R+d]`

#### II.11-q: `ExpandLeft((L, R), d) -> (l, r)`

Mở rộng [L, R] một khoảng `d` về hai phía

Trả về `[L-d, R]`

#### II.11-r: `ExpandRight((L, R), d) -> (l, r)`

Mở rộng [L, R] một khoảng `d` về hai phía

Trả về `[L, R+d]`

#### II.11-s: `Clamp(x, (L, R))`

Giới hạn điểm X nằm trong đoạn [L, R]

X = min(max(X, L), R)

### II.12 - Interval & Intervals

#### II.12-a: `IsDisjoint((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem hai đoạn [AL, AR] và [BL, BR] không giao nhau bất cứ phần tử nào ?

#### II.12-b: `IsIntersect((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem có tồn tại phần tử nào giao giữa hai đoạn `[AL, AR]` và `[BL, BR]` ?

#### II.12-c: `IsCrossing((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem có hai đoạn có điểm giao nhau, nhưng không bao chứa hoàn toàn nhau ?

#### II.12-d: `IsTouching((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem có duy nhất đúng một điểm tại phần giao giữa hai đoạn không ?

#### II.12-e: `IsOverlap((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem có một đoạn giao độ dài lớn hơn 0 tại phần giao giữa hai đoạn ?

#### II.12-f: `IsCovering((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem có một đoạn bao chứa hoan toàn đoạn kia hay không ?

#### II.12-g: `IsSubsetOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem đoạn `[AL, AR]` bị bao bọc hết bởi đoạn `[BL, BR]` hay không ?

#### II.12-h: `IsStrictSubsetOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem đoạn nhỏ hơn `[AL, AR]` bị bao bọc hết bởi đoạn `[BL, BR]` hay không ?

#### II.12-i: `IsSupersetOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem đoạn `[AL, AR]` bao chứa hoàn toàn đoạn `[BL, BR]` hay không ?

#### II.12-j: `IsStrictSupersetOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem đoạn lớn hơn `[AL, AR]` bao chứa hoàn toàn đoạn `[BL, BR]` hay không ?

#### II.12-k: `IsLeftOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem tất cả các điểm trong `[AL, AR]` nằm bên trái điểm biên phải của B ?

#### II.12-l: `IsStrictLeftOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem đoạn `[AL, AR]` nằm bên trái hoàn toàn `[BL, BR]` hay không ?

#### II.12-m: `IsRightOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem tất cả các điểm trong `[AL, AR]` nằm bên phải điểm biên trái của B ?

#### II.12-n: `IsStrictRightOf((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem đoạn `[AL, AR]` nằm bên phải hoàn toàn `[BL, BR]` hay không ?

#### II.12-o: `IsMatched((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem hai đoạn [AL, AR] và [BL, BR] có trùng nhau không

#### II.12-p: `HasEqualSize((AL, AR), (BL, BR)) -> bool`

Kiểm tra xem hai đoạn [AL, AR] và [BL, BR] có cùng độ dài không

#### II.12-q: `Distance((AL, AR), (BL, BR)) -> int`

Khoảng cách giữa hai đoạn

Nếu hai đoạn có phần tử chung thì khoảng cách là 0

Ngược lại là khoảng cách ngắn nhất của PQ, với P thuộc [AL, AR], Q thuộc [BL, BR]

#### II.12-r: `CenterDistance((AL, AR), (BL, BR)) -> int|-1`

Khoảng cách giữa tâm hai đoạn

Nếu có đoạn không hợp lệ khoảng cách là -1

Ngược lại là khoảng cách ngắn nhất của PQ, với P thuộc [AL, AR], Q thuộc [BL, BR]

#### II.12-s: `Clip((XL, XR), (L, R)) -> (L, R)`

Giới hạn đoạn [XL, XR] nằm trong đoạn [L, R]

XL = max(XL, L)
XR = min(XR, R)

#### II.12-t: `GapInterval((AL, AR), (BL, BR)) -> (L, R)`

Tìm đoạn nằm giữa hai đoạn

Trả về đoạn rỗng khi hai đoạn giao nhau

#### II.12-u: `MaxIntersectInterval((AL, AR), (BL, BR)) -> (L, R)`

Tìm đoạn con `[L, R]` lớn nhất nằm trong cả `[AL, AR]` và `[BL, BR]`

#### II.12-v: `MinCoverageInterval((AL, AR), (BL, BR)) -> (L, R)`

Tìm đoạn cha `[L, R]` nhỏ nhất bao chứa cả `[AL, AR]` lẫn `[BL, BR]`

#### II.12-w: `MergeIfOverlap((AL, AR), (BL, BR)) -> (L, R)|(1,0)`

Nếu hai đoạn có ít nhất một điểm giao thì trả về phần phủ nhỏ nhất

Ngược lại trả về đoạn rỗng (tứck không hợp lệ)

## III. Implementation Advance

### III.1 - Sum Aggregate

#### III.1-a: `SumOfFirstNNaturals(N, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}{K}\right) \mod P$

#### III.1-b: `SumOfFirstNSquares(N, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}{K^2}\right) \mod P$

#### III.1-c: `SumOfFirstNCubes(N, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}{K^3}\right) \mod P$

#### III.1-d: `SumOfFirstNQuartics(N, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}{K^4}\right) \mod P$

#### III.1-e: `DivSum(N, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}\left\lfloor\dfrac{N}{K}\right\rfloor\right) \mod P$

#### III.1-f: `GeoSum(X, N, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}X^K\right) \mod P$

#### III.1-g: `FloorSum(N, M, A, B, P)` $= \left(\underset{K=1}{\overset{N}{\Large\Sigma}}\left\lfloor\dfrac{A*K+B}{M}\right\rfloor\right) \mod P$

### III.2 - Array Aggregate

Cho mảng $a[1..n]$

#### III.2-a: `Sum(a[])`

#### III.2-b: `Median(a[])`

#### III.2-c: `Mean(a[])`

#### III.2-d: `Mode(a[])`

#### III.2-e: `PrefixSum[p]` $= \left(\underset{k=1}{\overset{p}{\Large\Sigma}} (a[k])\right)$

`PrefixSum[p]` là tổng của các số trong mảng $a$ xét (từ trái) tới vị trí $p$

#### III.2-f: `PrefixMin[p]` $= \left(\underset{k=1}{\overset{p}{\text{MIN}}} (a[k])\right)$

`PrefixSum[p]` là số nhỏ nhất của các số trong mảng $a$ xét (từ trái) tới vị trí $p$

#### III.2-g: `PrefixMax[p]` $= \left(\underset{k=1}{\overset{p}{\text{MAX}}} (a[k])\right)$

`PrefixSum[p]` là số lớn nhất của các số trong mảng $a$ xét (từ trái) tới vị trí $p$

#### III.2-h: `SuffixSum[p]` $= \left(\underset{k=p}{\overset{n}{\Large\Sigma}} (a[k])\right)$

`SuffixSum[p]` là tổng của các số trong mảng $a$ xét tới từ phải vị trí $p$

#### III.2-i: `SuffixMin[p]` $= \left(\underset{k=p}{\overset{n}{\text{MIN}}} (a[k])\right)$

`SuffixMin[p]` là số nhỏ nhất của các số trong mảng $a$ xét từ phải tới vị trí $p$

#### III.2-j: `SuffixMax[p]` $= \left(\underset{k=p}{\overset{n}{\text{MAX}}} (a[k])\right)$

`SuffixMax[p]` là số lớn nhất của các số trong mảng $a$ xét từ phải tới vị trí $p$

#### III.2-k: `PrevSmaller[p]` $= \left(\underset{k=1}{\overset{p}{\text{MAX}}}(pos\ \vert\ a[pos] < a[p])\right)$

`PrevSmaller[p]` là tìm số nhỏ hơn $p$ trước đó (về phía bên trái)

#### III.2-l: `PrevLarger[p]` $= \left(\underset{k=1}{\overset{p}{\text{MAX}}}(pos\ \vert\ a[pos] > a[p])\right)$

`PrevLarger[p]` là tìm số lớn hơn $p$ trước đó (về phía bên trái)

#### III.2-m: `NextSmaller[p]` $= \left(\underset{k=p}{\overset{n}{\text{MIN}}}(pos\ \vert\ a[pos] < a[p])\right)$

`NextSmaller[p]` là tìm số nhỏ hơn $p$ tiếp theo (về phía bên phải))

#### III.2-n: `NextLarger[p]` $= \left(\underset{k=p}{\overset{n}{\text{MIN}}}(pos\ \vert\ a[pos] > a[p])\right)$

`NextLarger[p]` là tìm số lớn hơn $p$ tiếp theo (về phía bên phải)

Max(positions | a[pos] < a[p])

### III.3 - Pairwise

### III.4 - Table

## A. Abstract Fundamentals

## AA. Abstract

I. Dynamic Programming (DP)
    1. DP Digit
    2. DP Trace
    3. DP Reroot
    4. DP Bitmask
        + Plug DP
        + Submask Enumeration DP
    5. DP Partial Sum
        + DP Prefixsum
        + DP Suffixsum
        + DP Cummulative Product
    6. DP Permutation
    7. DP Broken Profile
        + DP Pattern Tiling
        + DP Domino Covering
        + DP Chess Configuration
    8. DP Lexicographical
    9. DP Matrix Multiplication
    10. DP Exchange Argument
        + DP Sequence Alignment
        + DP with Sorting
        + DP Box Packing
    11. DP Knapsack
        + DP Bounded Knapsack
        + DP 0/1 Knapsack
    12. DP On Tree
        + DP Path Blocking
    13. DP On Range
    14. DP On DAG
    15. DP On Partitions
    16. DP Optimization
        + DP 1d1d Trick
        + DP x2+1 Trick
        + DP Alien Trick
        + DP Slope Trick
        + DP Knuth Trick
        + DP Forward-Backward Trick
        + DP Convex Hull Trick
        + DP Pruning
        + DP Swap Label
        + DP Space Saving
        + DP Open Close Interval
        + DP Connected Component
        + DP Divide and Conquer
        + DP Sum Over Subset (SOS)
        + Randomized DP
    ...
        + DP Longest Increasing Subsequence (LIS)
        + DP Longest Common Subsequence (LCS)
        + DP Maximum Subarray Sum (MSS)
        + DP Edit Distance
        + DP Histogram
        
II. Number Theory (NT)
    1. Linear Diophantine Equation
        + Greatest Common Divisor (GCD)
        + Lowest Common Multiple (LCM)
        + Extended GCD (ExtGCD)
        + Chinese Remainder Theorem (CRT)
    2. Sieve Theory
        + Trivial Division
        + Arithmetic Sieve (Squarefree Sieve)
        + Divisor Sieve
        + Mobius Sieve
        + Euler Totient Sieve
        + Eratosthenes
        + Linear Sieve
        + Sieve Optimization (Wheel Sieve, Segment Sieve, Bitwise Sieve)
    3. Prime
        + Factorization
        + Primality Test
        + Prime Signature
        + Divisor Sum
        + Fermat Theorem
        + Wilson Theorem
    4. Fibonacci
        + Lucas
        + Zeckendorf's Theorem
    5. Phi Function
    6. Mobius Function
    7. Harmonic Sequence
        + Floor
        + Ceil
        + Round Toward Zero
        
III. Data Structure (DS)
    1. STL
        - Pair
        - Tuple
        - Array
        - Valarray
        - Jagged Array
        - Dynamic Array (Vector)
        - Bitarray (Bitset)
        - Linked List
        - Stack
        - Queue
        - Deque
        - Set
        - Map
        - Unordered Set
        - Unordered Map
        - Multiset
        - Multimap
        - Unordered Multiset
        - Unordered Multimap
    2. Heap (Priority Queue)
        - Binary Heap
        - Treap
    3. Disjoint Set Union (DSU)
        - DSU Rollback
        - Persistent DSU
        - DSU Tree (Reachability Tree)
    4. Sparse Table
        - Disjoint Sparse Table
    5. Binary Search Tree (BST)
        - Splay Tree
        - Ordered Statistic Tree
        - AVL Tree
        - Red Black Tree
    6. SQRT Decomposition
        - Mo
        - Mo Optimization (Snake Curve, Hilbert Curve)
        - Mo On Tree
        - Logarithm Decomposition
        - SQRT Tree
        - Block Cut Tree (SQRT Fragmented Tree)
        - Venice Technique
    7. Fenwick Tree (BIT, Binary Indexed Tree)
        - 2D Fenwick Tree
        - Maintain Forward Backward
    8. Segment Tree (SegTree)
        - Segment Tree Beats
        - 2D Segment Tree
        - Lazy Segment Tree
        - Implicit Segment Tree
        - Iterative Segment Tree
        - Persistent Segment Tree
        - Retroactive Segment Tree
    9. Merge Sort Tree
    10. Hash
        - Multihash
        - Overflow Hashing
        - 2D Hash (Table Hashing)
        - Rolling Hash
        - XOR Hashing
    11. String Data Structure
    	- Trie (Prefix Tree)
    	- Suffix Array
    	- Suffix Tree
    	- Suffix Automaton
    	- EerTree
        - Abstract Syntax Tree (AST)
    12. Cartesian Tree
    13. Skip List
    14. Multidimensional Tree (Kd Tree)
        - QuadTree
        - OctTree
    15. Kinetic Data Structure
        - Kinetic Heap
        - Kinetic Convex Hull
        - Kinetic Minimum Spanning Tree
    16. Decomposition
        - Centroid Decomposition
        - Heavy-Light Decomposition (HLD)
    ...
        - Zip Tree
        - Wavelet Tree
        - Dynamic MST
        - Dynamic Median
        - Dynamic Convex Hull
        - Emilia Trick Tree
        - Aho Corasick
        
IV. Bitmask
    1. Bit Manipulation
        - OR
        - AND
        - XOR
        - NOT
        - NOR
        - XNOR
        - Short Circuit
        - Set
        - Unset / Clear
        - Flip / Toggle
        - Get Bit / Extract
        - Odd Even Check (Parity Check)
        - Power Of 2 Check (Single Bit Check)
        - Count Set Bit (Popcount)
        - Next Power Of 2 (bitceil)
        - Prev Power Of 2 (bitfloor)
        - Count Trailing Zeros (CTZ)
        - Count Trailing Ones (CTO)
        - Count Leading Zeros (CLZ)
        - Count Leading Ones (CLO)
        - Last Set Bit
        - Last Unset Bit
        - Remove Trailing Zeros
        - Clear Trailing Ones
        - Shift Left
        - Shift Right
        - Find First Set Bit (FFS)
        - Most Significant Bit (MSB)
        - Sign Extending
        - Opposing Sign Check (Positive Negative Check)
        - Reverse Bit
    2. Bitmask
        - Prime Signature
        - Gosper hack
        - Gray Code
        - Intersection
        - Union
        - Complementatary
        - Rotate Bit Left
        - Rotate Bit Right
        - Next Bit Permutation
        - Prev Bit Permutation
        - Bruteforces 2^n (Bit Enumeration)
        - Bruteforces 3^n (Submask Enumeration)
        - Supermask Enumeration
        - De Bruijn Sequence
    3. Arithmetic Via Bit
        - Addition with BIT
        - Subtraction with BIT
        - Multiplication with BIT
        - Division with BIT
        - Mod with BIT
        - Integer Xor Swapping
        - Abs without branching
        - Integer Sign Negation
        - Log2
    4. Bit Convolution
        - OR Conv
        - AND Conv
        - XOR Conv
        
V. Graph
    1. Traversal
        - Depth First Search (DFS)
        - Breadth First Search (BFS)
        - Priority First Search (PFS)
        - Topo Sort
        - Euler Tour
        - Eulerian Path
        - Eulerian Cycle (Fleury Algo)
        - Hamilton Path
        - Hamilton Cycle
        - Bipartite Check
        - Acyclicity Check
        - Connectivity Check
        - Negative Cycle Check
    2. Single Source Shortest Path
        - Flood Fill
        - BFS01
        - Dial Algo
        - Dijkstra
        - Bellman Ford
        - SPFA
    3. Multisource Shortest Path
        - Floyd Warshall
        - Optimized Dijkstra
    4. Bridge & Cut Point (Articulation Point)
        - Tarjan Algo
        - Kosaraju Algo
        - 2nd MST
        - Online Bridge
        - Bridge Tree
    5. Disjoint Set Union (DSU)
        - DSU Roll Back
        - Persistent DSU
        - Arpa Trick
        - Offline LCA
        - Partial Refinement
        - Dynamic Connectivity
        - Reachability Tree
        - Sack (DSU On Tree)
    6. Minimum Spanning Tree (MST)
        - Prim
        - Kruskal
        - Boruvka
        - 2nd MST
        - Euclidean Minimum Spanning Tree (EMST)
        - Rectilinear Minimum Spanning Tree (RMST)
    7. Strongly Connected Component (SCC)
        - Weakly Connected Component
        - Strong Orientation
        - Graph Condensation
        - K-Connected Graph
    8. Tree
        - Tree Traversal (Inorder, Preorder, Postorder)
        - Centroid Decomposition
        - Heavy-Light Decomposition (HLD)
        - Steiner Tree
        - Tree Isomorphism
        - Tree Diameter
        - Tree Center
    9. Graph Coloring
        - Vertex Coloring Problem
        - Edge Coloring Problem
        - Component Coloring Problem
    10. Graph Covering
        - Vertex Cover
        - Edge Cover
        - Dominating Set
    11. Graph Configuration
        - Tree
        - Forest
        - Sparse/Dense
        - Connected/Isolated
        - Weighted/Unweghted
        - Directed/Undirected/Bidirected/Multi-edge
        - Grid Graph
        - Line/Path Graph
        - Implicit Graph
        - Simple/Regular Graph
        - Multigraph/Hypergraph
        - Permutation Graph
        - Bipartite Graph
        - Cactus Graph
        - Caterpillar Graph
        - Cycle Graph
        - Star Graph
        - Sun Graph
        - Directed Acyclic Graph (DAG)
        - Eulerian
        - Hamilton
        - Gabriel
        - Kautz
        - De Brujin
        - Complete/Clique/Biclique Graph
        - 2SAT/3Sat/KSat Graph
        - Planar/Outerplanar/Apex Graph
        - Modular/Triangle-free Graph
        - Cayley Graph
        - Dual Graph
    12. Graph Operation
        - Condensation
        - Prune
        - Merge
        - Partition
    13. Maximum Matching & Flow Network
        - Ford Fulkerson
        - Edmonds Karp
        - Dinic
        - Push Relabel
        - Kuhn
        - Hopcropt-Karp
        - Blossom
        - Assignment & Scheduling Problems
        - Max Flow Min Cut
        - Min Cost Flow
        - Multisource/Multisink Flow
        - Maximum Cainality Matching
        - Maximum Bipartite Matching
        - General Maximum Matching

VI. String
    1. Hash
        - Overflow Hash
        - Multihash
        - Rolling Hash
        - Table Hash
        - XOR Hash
    2. String Table Search
        - Border Table
        - Best Prefix Table
        - Good Suffix Table
        - Last Occurence Table
    3. Trie = Prefix Tree
        - Bitwise Trie (Binary Trie)
        - Radix Trie (Patricia Tree)
    4. Z-Function
    5. KMP
        - Booth Algorithm
        - Ahocorasick
    6. Palindrome
        - Longest Palindrome Substring (LP Subsequence)
        - Palindrome Tree (Eertree)
        - Manacher Algo
    7. Suffix Array
        - DC3 Algo
        - Dynamic Suffix Array
        - Kasai Algo
    8. Suffix Tree
        - Linear Construction
        - RBT (std::map) + BST: O(log Σ) lookup, O(log Σ) insert, O(1) traverse, less data & medium constant
        - hashmap (std::unordred_map): O(1) loopup, O(1) insert, O(1) traverse, large data & high constant
        - Generalized Suffix Tree
    9. Suffix Automaton
        - Deterministic Finite Automaton (DFA, Reverse Factor, 2NFA, Backward Oracle Matching, Forward DAWG Matching, Backward Nondeterministic DAWG Matching)
        - Minimal DFA (Simon Algo, Brzozowski Algo, ...)
        - Pushdown Aumaton (PDA)
        - Finite State Automaton (Levenshtein Automaton)
    10. String Decomposition
        - Lyndon Duval Algo
        - LZW Algo
        - Run-Lenge Encoded (RLE)
        - Lexicographically Minimal String Rotation (LMSR)
        - String Period (String Power)
    11. String Matching
        - Longest Common Substring/Subsequence (LCS)
        - Longest Common Prefix (LCP)
        - Longest Palindrome Substring/Subsequence (LPS)
        - Shortest String Period (SSP)
        - Longest Repeated Substring (LRS)
        - Find All Distint Palindromic Substring
        - Pattern Matching
        - All-Pair Prefix-Suffix Matching
        - Edit Distance
        - String Alignment
        - Bioinformatics Gene Matching
        - Maximal Repeat (Supermaximal Repeat)
        - Boyer-Moore Algo
        - Occurence Count
        - Occurence Search
        - Ordered String Matching
    12. String Parsing & Conversion
        - Z <-> KMP
        - Odd Manacher <-> Even Manacher
        - Suffix Array <-> Suffix Tree
        - Suffix Tree <-> Suffix Automaton
        - Suffix Automaton <-> Suffix Array
        - Regular Expression (Regex)
        - Abstract Syntax Tree (AST)
    ...
        - Dendrogram
        - Wildcard
        - String Order Preserving (String Value Compression)
        - Streaming
        
VII. Implementation & Paradigm
    1. Backtracking
    2. Branch and bound
    3. Brute-force search
    4. Divide and conquer
    5. Recursion
    6. Prune and search
    7. Greedy
        - General Greedy (Huffman Code, Fractional Knapsack)
        - Exchange Argument Greedy
        - Load Balancing
        - Interval Covering
        - Scheduler
        - Approximation
        - Beam Search
        - Presorting Input
    
VIII. Sorting & Searching (SnS)
    1. Distribution Sorting
        - Counting Sort
        - Radix Sort
        - Bucket Sort
        - Pigeonhole Sort
        - Spread Sort
        - Burst Sort
        - Flash Sort
        - Shatter Sort
        - Gravity Sort  
    2. Impractical Sort
        - Pancake Sort
        - Bogo Sort
        - Silly Sort
        - Stooge Sort
    3. Exchange Sort
        - Exchange Sort
        - Bubble Sort
        - Cocktail Sort
        - Gnome Sort
        - Comb Sort
        - Odd-Even Sort
    4. Insertion Sort
        - Insertion Sort
        - Shell Sort
    5. Divide & Conquer Sort
        - Merge Sort
        - Quick Sort
    6. Hybrid Sort
        - Timsort
        - Block Merge Sort
        - Introsort
        - Sqrtsort
        - Grailsort
    7. Search
        - Linear Search
        - Ternary Search
        - Kary Search
        - Graph-based Search (DFS, BFS, PFS)
        - Search On Sorted List
        - Bisection Method
        - Tabu Search
    8. Binary Search
        - Binary Lifting
        - Binary Search
        - Parallel Binary Search
        
IX. Algebra (Alg)
    1. 
    
X. Statistic & Probability

XI. Geometry (Geo)

XII. Game Theory

XIII. Calculus & Analytic

XIV. Adhoc
    1. Childhood Game (Tic Tac Toe)
    2. Puzzle (Anagram)
    3. Card (Shuffle)
    4. Chess (8 Queen)
    5. Real-Life (Gridlock)
    6. Converter (Language Conversion)
    7. Simulation (Game Of Life)

XV. Metaheuristic

XVI. NonCP

|ID| Username  | Fullname             | Count | Index
|--|-----------|----------------------|-------|-------------------------------
|#1| NLMKhang  | Nguyễn Lê Minh Khang |...+20 | (I.1-abcdefgh;) II.1-abcde; II.3-abjklnop; II.4-afghpqs
|#2| NHBach    | Nguyễn Huy Bách      |...+15 | (I.1-abcdefghigklmno; I.3-abc;) II.1-abcdefghijklmno;
|#3| NPDang    | Nguyễn Phi Đăng      |...+10 | II.1-abcdefghij

|ID| Username  | Fullname             | Count | Index
|--|-----------|----------------------|-------|-------------------------------
|01| VNTMinh   | Vũ Nguyễn Thiên Minh |  126  | I.1->I.7, I.8-abcdefh, I.9-abcdefgh I.10, I.12, I.14-ab, I.21, I.22, I.19-a, II.1-ab //OK now
|02| DGLinh    | Đỗ Gia Linh          |  106  | I.1->I.3, I.4-abcdefghijklmnopqrstuv, I.5-abc, I.10, I.11, I.12-abcdef, I.13-ab, I.14, I.16-a, I.19-a, I.20-a, I.21, I.23, II.1-abcd
|03| NLHLam    | Nguyễn Lý Hoàng Lâm  |  103  | I.1->I.13, I.14-abcdef, II.1-df.
|04| NKThanh   | Nguyễn Khắc Thành    |   87  | I.1->I.4, I.14-abcdef, II.1-abegijklm 
|05| BKNguyen  | Bùi Khôi Nguyên      |   67  | I.2-ghijlmn; I.3; I.4-abclmnqruxy; I.6 abcfkl;I.9 ad;  I.10-efgh; I.11; I.12; I.13-ab; I.14-ab; I.17;I.20 d; I.21 ; I.23-a; II.1 g
|06| HMNhat    | Hồ Minh Nhật         |   56  | II.1(e chx lm đc 3 cái); II.3; II.4-abcdefghi;
|07| HDGMinh   | Huỳnh Đoàn Gia Minh  |   50  | I.1; I.2; I.3; II.1; I.21; I.14; I.11; I.12;   
|08| NTHung    | Nguyễn Tuấn Hưng     |   47  | I.1, I.2, I.3, I.4-a, II.1-abcdefghijklmnopq 
|09| BHNam     | Bùi Hải Nam          |   47  | I.1->I.8, II.3, II.4-abcdefghi;
|10| VHDuc     | Vũ Hồng Đức          |   45  | I.1; I.2; I.3; I.4 (trừ phần stream)
|11| NMQuan    | Nguyễn Minh Quân     |   45  | I.1-abcdefghijklmno; I.2-abghijklmnop; I.3-abc; II.2-cdghijkmnqrstuz
|12| VNNKhang  | Võ Ngọc Nguyên Khang |   38  | I.1-abcdefhijklmno; I.2-hijklmnopq;; I.3 abc; I.4 abcdef; II.1-bcdef;
|13| TTPhat    | Trần Tín Phát        |   32  | I.1; II.1-abcdef
|14| HMKhoi    | Huỳnh Minh Khôi      |   32  | I.1-abcdefghjkimo; I.2-abcdefgh; II.1-abcdefghjk  
|15| PMKhai    | Phan Mạnh Khải       |   31  | I.1-abcdefghjkimno; I.2-abcdefg; I.4-defghjkimno,II.2-cd
|16| BTNguyen  | Bùi Trọng Nguyên     |   21  | I.1-cfghjkn; II.1-k, I.2-ac, I.3-ab, I.4-dqr, I.21-abcdefg
|17| TBKhang   | Tống Bảo Khang       |   14  | I.19-ab, I.21-abcdefg II.1-cdef
|18| HTKhoi    | Huỳnh Trí Khôi       |   11  | I.1-abcdefghijk 
|19| LHNKhang  | Lê Hoàn Nhật Khang   |    5  | II.1-klmno

## AAA.

## O. Observation

## OO.

## OOO.

## Other

https://hackmd.io/@spyofgame/t13

{%preview https://hackmd.io/_ga_LpXPTF2Wrzz0KZSi6A %}

### X

### Y

### Z

{%hackmd Z2nEm4n1Tp-G7l32aQD37A %}