// C Standard Library Cheatsheet Template
// A clean, two-column layout for quick reference during coding interviews.
// Created with Typst.

// ================= DOCUMENT SETUP =================
#set document(title: "C Standard Library Reference", author: "David Gao")

#let base-text-size = 9pt

#set text(font: ("Arial", "DengXian"), size: base-text-size, lang: "zh")
#show raw: set text(
  font: (
    "Cascadia Code",
    "SimHei",
  ),
)

#set page(paper: "a4", margin: (top: 0.75in, bottom: 0.75in, left: 0.5in, right: 0.5in))

// Define colors for styling to make sections stand out.
#let primary_color = navy
#let secondary_color = luma(230)

// ================= CUSTOM SHOW RULE (The Cheatsheet Engine) =================
#let entry(signature, description, code_lang: "cpp") = {
  grid.cell[
    #rect(width: 100%, inset: (x: 4pt, y: 3pt), fill: luma(240), radius: 2pt, [#raw(signature, lang: code_lang)])
  ]
  grid.cell[
    #description
  ]
}

// This function formats a larger code snippet for algorithms/data structures.
#let code_snippet(body, title: none) = {
  // This `if` statement checks if a title was passed.
  // If `title` is anything other than `none`, this block is rendered.
  if title != none {
    pad(bottom: 4pt, text(weight: "bold", title))
  }

  // The main block for the code is always rendered.
  block(
    width: 100%,
    inset: 8pt,
    fill: luma(240),
    radius: 3pt,
    body,
  )
  v(1em)
}

// ================= HEADER FUNCTION =================
#let section_header(title) = {
  // v(0.5em)
  block(width: 100%, fill: primary_color, inset: 6pt, radius: 3pt, text(white, weight: "bold", title))
  v(0.5em)
}

// ================= SUBSECTION HEADER FUNCTION =================
#let subsection_header(title) = {
  // v(1.2em) // A bit of space above the subsection title.
  // Make text bold, slightly larger, and use the primary color.
  text(weight: "bold", title)
  // Add a subtle line underneath to separate it from the content.
  line(length: 100%, stroke: 0.5pt + primary_color)
  v(0.6em) // Space after the subsection header.
}

#show heading.where(level: 1): it => section_header(it.body)
#show heading.where(level: 2): it => subsection_header(it.body)

// ================= CHEATSHEET CONTENT =================

// Main Title
#align(center)[
  #text(size: 20pt, weight: "bold", "C Standard Library Reference")
  #line(length: 100%, stroke: 1pt)
  #v(1em)
]

#section_header([`stdio.h`])

#grid(
  columns: (auto, 1fr),
  column-gutter: 8pt,
  row-gutter: 6pt,
)[
  #entry(
    "int printf(const char* format, ...);",
    [Prints formatted output to `stdout`. Common specifiers: `%d` (int), `%f` (float/double), `%c` (char), `%s` (string), `%p` (pointer).],
  )
  #entry(
    "int sprintf(char* str, const char* format, ...);",
    [Prints formatted output to a string `str`.],
  )
  #entry(
    "int scanf(const char* format, ...);",
    [Reads formatted input from `stdin`.],
  )
  #entry(
    "int getchar(void);",
    [Reads the next character from `stdin`.],
  )
  #entry(
    "int putchar(int ch);",
    [Writes a character `ch` to `stdout`.],
  )
]

#section_header([`string.h`])

#grid(
  columns: (auto, 1fr),
  column-gutter: 8pt,
  row-gutter: 6pt,
)[
  #entry(
    "void *memset(void *str, int c, size_t n);",
    [`n` is the number of bytes needed to be set. Can be obtained by `sizeof(array)`, where `array` is of type `T[]`.],
  )
  #entry(
    "void *memcpy(void *dst, const void *src, size_t n);",
    [
      Copy `n` bytes of data starting from `src` into `dst`. 需要确保`src`和`dst`空间不重叠。
    ],
  )
  #entry(
    "int strcmp (const char * str1, const char * str2);",
    [返回`str1`与`str2`的字典序，`str1`在前则$<0$，`str1`在后则$>0$。返回0则相等。],
  )
  #entry(
    "size_t strlen(const char *str);",
    [返回字符串长度],
  )
  #entry(
    "char *strcpy(char *__restrict__ _Dest, const char *__restrict__ _Source);",
    [将`src`内的字符串复制进`dest`],
  )
  #entry(
    "char *strcat(char *dest, const char *src);",
    [把`src`所指向的字符串追加到`dest`所指向的字符串的结尾],
  )
  #entry(
    "char *strchr(const char *str, int c);",
    [在参数`str`所指向的字符串中搜索第一次出现字符 `c`（一个无符号字符）的位置。],
  )
  #entry(
    "char *strpbrk(const char *str1, const char *str2);",
    [检索字符串`str1`中第一个匹配字符串`str2`中某个字符的字符，不包含空结束字符。也就是说，依次检验字符串`str1`中的字符，当被检验字符在字符串`str2`中也包含时，则停止检验，并返回该字符位置。],
  )
  #entry(
    "char *strstr(const char *haystack, const char *needle);",
    [在字符串`haystack`中查找第一次出现字符串`needle`（不包含空结束字符）的位置。],
  )
  #entry(
    "char *strtok(char *str, const char *delim);",
    [
      分解字符串 str 为一组字符串，delim 为分隔符。
      ```c
      char *token = strtok(str, s);
      /* 继续获取其他的子字符串 */
      while(token != NULL) {
          printf("%s\n", token);
          token = strtok(NULL, s);
      }
      ```
    ],
  )
]


// --- stdlib.h Section ---
#section_header([`stdlib.h`])

#grid(
  columns: (auto, 1fr),
  column-gutter: 8pt,
  row-gutter: 6pt,
)[
  #entry(
    "void* malloc(size_t size);",
    "Allocates `size` bytes of uninitialized memory. Returns a void pointer to the allocated space.",
  )
  #entry(
    "void* calloc(size_t nmemb, size_t size);",
    "Allocates memory for an array of `nmemb` elements of `size` bytes each and initializes all bits to zero.",
  )
  #entry(
    "void* realloc(void* ptr, size_t size);",
    "Resizes the memory block pointed to by `ptr` to `size` bytes. The content will be unchanged up to the minimum of the old and new sizes.",
  )
  #entry(
    "void free(void* ptr);",
    "Deallocates a block of memory previously allocated by `malloc`, `calloc`, or `realloc`.",
  )
  #entry("int atoi(const char* str);", "Converts the initial portion of the string `str` to an `int`.")
  #entry(
    "long int strtol(const char* str, char** endptr, int base);",
    "Converts string `str` to a `long int`. `endptr` can be used to see where conversion stopped. `base` is the number base (e.g., 10).",
  )
  #entry(
    "void qsort(void* base, size_t nmemb, size_t size, int (*compar)(const void*, const void*));",
    "Sorts an array. `compar` is a pointer to a function that compares two elements.",
  )
  #entry("int rand(void);", "Returns a pseudo-random integer between 0 and `RAND_MAX`.")
  #entry("void srand(unsigned int seed);", "Seeds the pseudo-random number generator used by `rand()`.")
  #entry("void exit(int status);", "Causes normal program termination. `EXIT_SUCCESS` or `EXIT_FAILURE`.")
]

#v(1.5em)

// --- string.h Section ---
= `string.h` — String Manipulation

#grid(
  columns: (auto, 1fr),
  column-gutter: 8pt,
  row-gutter: 6pt,
)[
  #entry(
    "size_t strlen(const char* s);",
    "Calculates the length of string `s`, excluding the terminating null byte (`'\\0'`).",
  )
  #entry(
    "char* strcpy(char* dest, const char* src);",
    "Copies the string `src` to `dest`. *Unsafe*, does not check buffer size.",
  )
  #entry(
    "char* strncpy(char* dest, const char* src, size_t n);",
    "Copies up to `n` characters from `src` to `dest`. May not be null-terminated if `src` is too long.",
  )
  #entry(
    "int strcmp(const char* s1, const char* s2);",
    "Compares two strings. Returns < 0 if s1 < s2, 0 if s1 == s2, > 0 if s1 > s2.",
  )
  #entry(
    "char* strchr(const char* s, int c);",
    "Returns a pointer to the first occurrence of character `c` in string `s`, or `NULL` if not found.",
  )
  #entry(
    "char* strstr(const char* haystack, const char* needle);",
    "Finds the first occurrence of the substring `needle` in the string `haystack`.",
  )
  #entry(
    "void* memset(void* s, int c, size_t n);",
    "Fills the first `n` bytes of the memory area pointed to by `s` with the constant byte `c`.",
  )
  #entry(
    "void* memcpy(void* dest, const void* src, size_t n);",
    "Copies `n` bytes from memory area `src` to memory area `dest`.",
  )
]

= 常用技巧

== 防止栈溢出
```c
#pragma comment(linker, "/STACK:1024000000,1024000000")
```

== C++常用头文件
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<functional>
#include<bits/stdc++.h>
```

= Common Algorithms & Data Structures

== 字符串匹配

=== KMP算法：$O(n)$

#code_snippet[
  ```cpp
  int next[MAXN];
  int KMP(string txt, string pattern) {
    int i = next[0] = -1
    int j = 0;
    int n = text.size();
    int m = pattern.size();

    // 生成next表
    while (j < m) {
      if (i == -1 || pattern[j] == pattern[i]) {
        i++;
        j++;
        next[j] = i;
      } else {
        i = next[i];
      }
    }

    // KMP
    i = j = 0;
    while (i < m && j < n) {
      if (i == -1 || text[j] == pattern[i]) {
        i++;
        j++;
      } else {
        i = next[i];
      }

      if (i == m) {
        // 成功匹配，第一个字符在text的index为i - j + 1
        // 完美匹配，当作失配处理
        // i = next[i];
      }
    }
  }
  ```]

== 日期处理

#code_snippet[```cpp
struct Date{
    int year, month, day;
    Date(int y, int m, int d): year(y), month(m), day(d) {}
    int week(){   // 今天是星期几？ 基姆拉尔森公式
        int y = year, m = month, d = day;
        if( m == 1 || m == 2 ) {
          m += 12;
          y--;
        };
        int w = (d + 2*m + 3*(m+1)/5 + y + y/4 - y/100 + y/400) % 7;
        return ++w; // w：0:星期一...依此类推
    }
    int MONTH[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
    int kthDay(){  // 给定一个日期，输出这个日期是该年的第几天
        if(year % 4 == 0 && (year % 100 || year % 400 == 0))
            MONTH[2] = 29;
        int days = 0;
        for (int i = 1; i < month; i++) days += MONTH[i];
        return days += day;
    }
};
```]


== 排序

=== 快速排序：$Theta (n log n) + O(1)$

#code_snippet[```cpp
void quicksort(vector<int> &a, int le, int ri) {
  // 排序[le, ri)
  int i = le, j = ri - 1;
  int pivot = a[(rand()%(ri-le))+le];
  while (i <= j) {
    while (a[i] < pivot) i++;
    while (a[j] > pivot) j--;
    if (i <= j) swap(&a[i++], &a[j--]); // 先swap，之后执行自增
  }

  if (le < j) quicksort(a, le, j + 1);
  if (i < ri - 1) quicksort(a, i, ri);
}
```]

=== 归并排序/求逆序对：$O(n log n) + O(n)$

#code_snippet[```cpp
long long mergesort(vector<int>& a, long long le, long long ri){
    long long ans = 0;
    if(le >= ri - 1) return 0;
    long long mid = (le + ri) >> 1;
    ans += mergesort(a, le, mid);
    ans += mergesort(a, mid, ri);

    vector<long long> b;  //辅助数组
    long long p = le, q = mid;
    long long count = 0;
    while(p < mid && q < ri){
        if(a[p] <= a[q]) b.push_back(a[p++]);
        else{
            b.push_back(a[q++]);
            count += (mid - p); // 求逆序
        }
    }
    while(p < mid) b.push_back(a[p++]);
    while(q < ri)  b.push_back(a[q++]);
    for(long long i = le; i < ri; ++i)
        a[i] = b[i-le];

    ans += count;
    //ans += min(count, (mid - le)*(ri - mid) - count); //求二叉树最小逆序
    return ans;
}
```]

== 二分查找：$O(log n)$

#code_snippet[```cpp
int binarySearch(vector<int> &a, int e){ // 保证输入有序; lower_bound形式
    int le = 0, ri = a.size();
    while(ri - le > 1){ // [le, ri)夹逼
        int mid = (le + ri) >> 1;
        if(a[mid] <= e)
            le = mid; // le处元素总是<=
        else
            ri = mid; // ri处元素总是>
    }
    return le; // 返回下标
}
```]

== 贪心问题

=== 区间选点

数轴上$n$个闭区间，尽可能选择少的点，使得每个区间内至少有一个点被选到。

解法：将区间结束点从小到大排列；选第一个结束点作为我们选择的第一个点，删去所有已经被选了点的区间；不停地选择剩余区间中结束点最靠前的点，直到所有区间都有至少一个点。

=== 区间覆盖

数轴上有数个区间$[a, b]$。给定一个线段$[s, t]$，使用最少数量的区间将线段完全覆盖。

解法：在预处理：将各个区间按$a$的大小排序。首先确认最小的开头在$s$前，否则直接无解。之后使用贪心。对于所有$a < s$的区间，找$b$最大的（这样能覆盖更多）。之后将$s$移动到$b$，接着寻找新的最长的，直到全部覆盖。

== DP

=== 普通背包问题：$O(n V) + O(V)$

第`i`个物品的体积为`w[i]`，价值为`v[i]`，`d[i][j]`代表从开头到第`i`个物品（包含）在`j`体积内能达到的最大价值。由于`d[i + 1]`只依赖于`d[i]`，数组只需要一维。需要从`j`较大的往下更新，防止更新大`j`时用到的小`j`的价值是已经是加入了本物品的价值。

#code_snippet(```cpp
int dp[MAXN];
int backpack(vector<int> w, vector<int> v, int n, int V) { // n为物品数，V为总容量
  for (int i = 0; i < n; i++) {
    for (int j = V; j >= w[i]; j--) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
}
```)

=== 完美背包问题：$O(n V) + O(V)$

与普通背包的区别是每个物品都有无限个。只要正向更新，刚好满足要求（考虑大体积时可以用之前已经加了这个物品的接着加入）。

#code_snippet(```cpp
int dp[MAXN];
int backpack(vector<int> w, vector<int> v, int n, int V) { // n为物品数，V为总容量
  for (int i = 0; i < n; i++) {
    for (int j = w[i]; j <= V; j++) {
      dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
  }
}
```)

=== 多重背包：$O(V sum(log_2(k_i)))$

对于第`i`种物品，体积`w[i]`，价值`v[i]`，数量`k[i]`。对数量进行二进制拆分：$k = 1 + 2 + 4 + dots + 2^p + (k - (2^(p + 1) - 1))$。这些数量的物品各自算作一个新物品，继续做01背包。

拆分代码：

#code_snippet(```cpp
int __v[MAXN], __w[MAXN], cnt = 0; // 拆分后物品总数
for(int i = 0; i < n; ++i){ // 分组
  int v, w, k;
  scanf("%d%d%d", &w, &v, &k);
  int c = 1;
  while(k - c > 0){
    k -= c;
    __w[cnt]   = c*w;
    __v[cnt++] = c*v;
    c *= 1;
  }
	__w[cnt]   = k*w;
  __v[cnt++] = k*v;
}
```)

=== 最优多边形剖分：$O(n^3)$

多边形中任意两点$i, j$间的弦有某个权值$w(i, j)$。求将多边形分割成数个三角形所需的最低权值。我们可以用$d(i, j)$表示子多边形$i, i + 1, dots, j - 1, j$的最优解（这个多边形是我们通过选择$i j$这条弦切割出来的）。那么
$ d(i, j) = max_(i < k < j){d(i, k) + d(k, j) + w(i, k) + w(k, j)} $

#figure(
  image(
    "./img/三角形剖分.png",
    width: 30%,
  ),
) #label("fig: 三角剖分")

=== 数位DP

给出某个范围$[a, b]$求在这个范围中满足一定要求的数有多少个（通常与数大小等没有关系，与数的数位（digit）有关）。例如，给定$[a,b]$，求范围内每个数位出现次数。

解法：首先需要几个数组：$text("ten")(i)$为$10^i$，$f(i)$为$[0, 10^i - 1]$范围内任意数位出现的次数。这是我们DP算法的核心。核心状态转移：
$ f(i) = f(i - 1) times 10 + text("ten")(i) $

即对于所有小于等于$i$位的数，我们$i - 1$中重复了10次，最高位中我们关心的这个数（不论是0-9中的哪个）作为最高位的数都有$10^i$个。

#code_snippet(```cpp
#include<bits/stdc++.h>
using namespace std;
long long a,b;
long long ten[20],f[20];
long long cnta[20],cntb[20];
void solve(long long x,long long *cnt){
  long long num[20]={0};
  int len=0;
  while(x){   // 对x进行数位分解
    num[++len]=x%10;
    x=x/10;
  }
  // 最低位在num[1]，最高位在num[len]

  // 一下以543这个数为例。num = {0, 3, 4, 5}
  // 从最高位开始往下。以5为例
  for(int i=len; i>=1; i--){
    // 处理0 - 499的计数，以及5作为首位的计数
    for(int j=0; j<=9; j++)
      // 每个数位在0-499的十位和个位均匀出现。
      cnt[j] += f[i-1] * num[i];
    for(int j=0; j<num[i]; j++)
      // 0, 1, 2, 3, 4作为百位多出现了一些次数。
      cnt[j] += ten[i-1];
    long long num2=0;
    // 下面这个循环把43从数位再拼回来
    for(int j= i-1; j>=1; j--){
      num2 = num2 * 10 + num[j];
    }
    // 5作为百位出现了43 + 1次
    cnt[num[i]]+=num2+1;
    // 0作为百位时不会被写出来。
    cnt[0]-= ten[i-1];
  }
}
int main()
{
  scanf("%lld %lld",&a,&b);    // 区间范围
  ten[0]=1;
  for(int i=1;i<=15;i++)
  {
    f[i]=f[i-1]*10+ten[i-1];
    ten[i]=10*ten[i-1];
  }
  solve(a-1,cnta);   // [1, a-1]总计数
  solve(b,cntb);     // [a,   b]总计数
  for(int i=0;i<=9;i++)
  printf("%lld ",cntb[i]-cnta[i]);    // 两者相减
}
```)

== 数学

=== 快速幂：$O(log n)$

Python中自带快速幂。

矩阵快速幂只需重载乘法。

#code_snippet(```cpp
int q_power(int a, int n) {
  if (n == 0) return 1;
  if (n == 1) return a;
  int base = q_power(a, n / 2);
  base *= base;
  return (n % 2) ? a * base : base;
}
```)

=== 费马小定理求幂的模：$O(log P)$

计算模意义下的幂。$p$必须为质数。因为$a^(p - 1) equiv 1 (mod p)$，因此$a^b equiv a^(b mod (p - 1)) (mod p)$

#code_snippet(```cpp
int q_power(int a, int n, int mod) {
  int ans = 1, base = a;
  while(n) {
    if (n & 1) ans *= base;
    base *= base;
    ans %= mod;
    base %= mod;
    n >>=1;
  }
  return ans;
}

int q_big_power(int a, int n, int p) {
  return q_power(a, n % (p - 1), p)
}
```)

=== 更快的快速幂：$O(T)$

在$a$不变的情况下进行$T$次幂查询$t_1, t_2, dots t_T$，可以记$n = max{t_i}$，则
$ a^t = (a^(sqrt(n)))^(t \/ sqrt(n)) times a^(t % sqrt(n)) $

即，我们可以提前算好$a$的$0$到$sqrt(n)$次幂进行计算并存储，之后可以以$O(1)$的速度进行计算。

=== 最大公约数gcd：$O(log n)$

使用欧几里得算法。STL中提供了`__gcd(a, b)`。

#code_snippet(```cpp
inline int gcd(int a, int b) {
  return b == 0 ? a: gcd(b, a % b);
}
```)

快速gcd：
#code_snippet(```cpp
int kgcd(int a, int b) {
  if (a == 0) return b;
  if (b == 0) return a;
  if (!(a & 1) && !(b &1)) return kgcd(a >> 1, b >> 1) << 1;
  else if (!(b & 1)) return kgcd(a, b >> 1);
  else if (!(a & 1)) return kgcd(a >> 1, b);
  else return kgcd(abs(a - b), min(a, b));
}
```)

=== 最小公倍数lcm

#code_snippet(```cpp
int lcm(int a, int b) {
  return a * b / gcd(a, b)
}
```)

=== 扩展欧几里得算法

可以解出$a x + b y = gcd(a, b)$的一组特解。

#code_snippet(```cpp
void exgcd(int a, int b, int &x, int &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return;
  }
  exgcd(b, a % b, y, x);
  y -= a / b * x;
}
```)

== 数位分解

=== 除余法

#code_snippet(```cpp
vector<int> split(int n){ // 传入整数
    vector<int> ret;
    while(n){
        int t = n % 10; ret.push_back(t);
        n /= 10;
    }
    reverse(ret.begin(), ret.end()); // 反转，按需
    return ret;
}
```)

=== ASCII转数字

#code_snippet(```cpp
vector<int> split(string n){ // 传入字符串
    vector<int> ret;
    ret.resize(n.size());
    for(int i = 0; i < n.size(); ++i)
        ret[i] = n[i] - '0'; // 利用ASCII减法获得真实数字
    return ret;
}
```)

=== 格雷码

格雷序列中的第$i$个项目的格雷码为$i xor (i >> 1)$。

#code_snippet(```cpp
vector<int> Gray_Create(int n){
    vector<int> res; res.clear();
    for(int i = 0; i < (1 << n); ++i)
        res.push_back(i ^ (i >> 1));
    return res;
}
```)

== 高精度类

#code_snippet(```cpp
struct BigInt{ // 仅限正整数，当MAXN较大时容易栈溢出，尽量定义为全局变量
  int digit[MAXN]; // [低位 -> 高位)，与I/O顺序相反
  int SIZE, BASE; // 数位和进制

  BigInt(){BASE = 10; SIZE = 0;} // 默认十进制
  BigInt(int base){BASE = base; SIZE = 0;}
  BigInt(const string& S, int base = 10){
    SIZE = S.size();
    BASE = base;
    string baseChar = "0123456789ABCDEF"; // 数位
    for (int i = 0, i < SIZE; i++) {
      digit[i] = baseChar.find(S[i]);
    }
  }
  void overflow(){ // 溢出进位
    for(int i = 0; i < SIZE; ++i) {
      if(digit[i] >= BASE){
        if(i < SIZE - 1){
          digit[i + 1] += digit[i] / BASE;
          digit[i] %= BASE;
        } else{
          digit[SIZE++] = digit[i] / BASE;
          digit[i] %= BASE;
        }
      }
    }
  }

  BigInt operator +(const BigInt &A){  // 高精度加法
    BigInt ret(BASE);  // 采取前者的BASE，使用时注意保证两个数进制相同
    int max_size = max(SIZE, A.SIZE);
    ret.SIZE = max_size;
    for(int i =0; i < max_size; ++i){
      if(i <   SIZE) ret.digit[i] +=   digit[i];
      if(i < A.SIZE) ret.digit[i] += A.digit[i];
    }
    ret.overflow();
    return ret;
  }
  BigInt operator +(const int x){      // 普通加法
    BigInt ret = *this;
    ret.digit[0] += x;
    ret.overflow();
    return ret;
  }
  BigInt operator *(const BigInt &A){  // 高精度朴素乘法 O(n^2)
    BigInt ret(BASE);
    int max_size = SIZE + A.SIZE - 1;
    ret.SIZE = max_size;
    for(int i = 0; i < SIZE; ++i)
      for(int j = 0; j < A.SIZE; ++j)
        ret.digit[i + j] += digit[i] * A.digit[j];
    ret.overflow();
    return ret;
  }
  BigInt operator *(const int x){      // 普通乘法
    BigInt ret = *this;
    for(int i = 0; i < SIZE; ++i)
      ret.digit[i] *= x;
    ret.overflow();
    return ret;
  }
  BigInt operator /(const int x){      // 普通除法
    BigInt ret(BASE); ret.SIZE = SIZE;
    int remainder = 0; // 余数
    for(int i = SIZE - 1; i >= 0; --i){ // 高位 -> 低位
      int t = (remainder * BASE + digit[i]) / x;
      int r = (remainder * BASE + digit[i]) % x;
      ret.digit[ret.SIZE++] = t; remainder = r;
    }
    reverse(ret.digit, ret.digit + SIZE); // 反置为[低位 -> 高位)
    while(ret.digit[ret.SIZE - 1] == 0 && ret.SIZE > 1) ret.SIZE--; // 去掉前缀0
    return ret;
  }
  int operator %(const int x){         // 普通模运算
    int remainder = 0; // 余数
    for(int i = SIZE - 1; i >= 0; --i) // 高位 -> 低位
      remainder = (remainder * BASE + digit[i]) % x;
    return remainder;
  }
  bool operator ==(const BigInt &A){
    if(SIZE == A.SIZE){
      for(int i = SIZE -1; i >= 0; --i){
        if(digit[i] != A.digit[i]) return false;
      }
      return true;
    } else return false;
  }
  bool operator <(const BigInt &A){
    if(SIZE == A.SIZE){
      for(int i = SIZE -1; i >= 0; --i){
        if(digit[i] < A.digit[i])
          return true;
        else if(digit[i] > A.digit[i])
          return false;
      }
      return false; // 相等时返回false
    } else return SIZE < A.SIZE;
  }
  bool operator <=(const BigInt &A){
    if(SIZE == A.SIZE){
      for(int i = SIZE -1; i >= 0; --i){
        if(digit[i] < A.digit[i])
          return true;
        else if(digit[i] > A.digit[i])
          return false;
      }
      return true; // 相等时返回true
    } else return SIZE < A.SIZE;
  }
};

BigInt convert_to(BigInt A, int base){ // 进制转换，该方法存在BUG，慎用
  BigInt ret(base);
  while(A.SIZE > 1 || A.digit[0] > 0){ // 保证A>0
    ret.digit[ret.SIZE++] = A % base;
    A = A / base;
  }
  return ret;
}

string baseChar = "0123456789ABCDEF"; // 数位
char S[MAXN];
istream& operator >>(istream &in , BigInt &A){
  scanf("%s", S);
  A.SIZE = 0; A.BASE = 10; // 可调整输入进制
  for(int i = strlen(S) - 1; i >= 0; --i){
    A.digit[A.SIZE++] = baseChar.find(S[i]);
  }
  return in;
}
ostream& operator <<(ostream &out, const BigInt& A){
  for(int i = A.SIZE - 1; i >= 0; --i)
    printf("%c", baseChar[A.digit[i]]);
  return out;
}
```)

== 最小生成树

=== Kruskal算法：$O(e log e)$

将所有的边按从小到大排列，依次取出。如果取到的边可以将两个不连通的部分联通，则选择它；如果取到的边连接的是已经连图的两个点，则不做操作。提前退出可以生成最小生成森林（$n - k$次连接对应$k$棵树的$k-text("森林")$。

#code_snippet(```cpp
struct Edge{   // 带权边
    int from, to, dist;
    Edge(int u, int v, int d): from(u), to(v), dist(d) {}
    bool operator < (Edge x) const{  // const才能用PQ调用
        return dist > x.dist; //【最小】/最大支撑树
    }
};
int n, m;
priority_queue<Edge> PQ; // 按边权排序（默认大根堆）
uf_set U(MAXNODE); // 【并查集模板】
int Kruskal(){
  int ret = 0, cnt = 0;
  while(!PQ.empty()){
    Edge t = PQ.top(); PQ.pop(); // 取出最小边
    // cout << "dist:" <<t.dist <<endl; 
    if(U.find(t.from) != U.find(t.to)){ // 不属于同一集合
      U.Union(t.from, t.to);
      // EXECUTE(t); // 对当前边做特定操作
      ret += t.dist;
      cnt ++;
    }
  }
  if(cnt != n - 1) return INF;   // 原图不连通
  return ret;                    // 返回最小生成树权值
}

int main(){
  // freopen("OJ.in", "r", stdin);
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int x, y, z; cin >> x >> y >> z;
    PQ.push(Edge(x, y, z));
  }
  int ret = Kruskal();
    
	if(ret == INF) cout << "orz" <<endl;
	else cout << ret << endl;

  return 0;
}
```)

=== Prim算法：$O(n log n)$

维护一个已经加入树的点。选所有从已在数中的点延伸出的边中最短的一条，将对应的点加入树。

#code_snippet(```cpp
// 使用二叉堆优化的 Prim 算法。
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int N = 5050, M = 2e5 + 10;

struct E {
  // v: 终点的编号
  // w: 权
  // x: 同起始点的下一个边在e[]中的编号
  int v, w, x;
} e[M * 2];

int n, m, h[N], cnte;

// h[n] 为n号点为起始点的第一个边在e[]中的编号

// 最后一个加入的u起始的边将成为h[u]
void adde(int u, int v, int w) { e[++cnte] = E{v, w, h[u]}, h[u] = cnte; }

// 以u为起点到达目前已生成树的一条边
struct S {
  int u, d;
};

// STL默认priority queue是大堆，这样可以使得它变为小堆
bool operator<(const S &x, const S &y) { return x.d > y.d; }

priority_queue<S> q;
// dis[u]为u到当前最小树的最近距离
int dis[N];
bool vis[N];

int res = 0, cnt = 0;

void Prim() {
  memset(dis, 0x3f, sizeof(dis));
  dis[1] = 0;
  q.push({1, 0});
  while (!q.empty()) {
    if (cnt >= n) break;
    int u = q.top().u, d = q.top().d;
    q.pop();
    if (vis[u]) continue;
    vis[u] = true;
    ++cnt;
    res += d;
    for (int i = h[u]; i; i = e[i].x) {
      int v = e[i].v, w = e[i].w;
      if (w < dis[v]) {
        dis[v] = w, q.push({v, w});
      }
    }
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1, u, v, w; i <= m; ++i) {
    cin >> u >> v >> w, adde(u, v, w), adde(v, u, w);
  }
  Prim();
  if (cnt == n)
    cout << res;
  else
    cout << "No MST.";
  return 0;
}
```)

== 最短路

=== Dijkstra算法：$O(e log n)$

将起点加入集合；找集合点向外连接的边中最短的边；将终点加入集合，并记录最短距离。

#code_snippet(```cpp
struct edge {
  int v, w;
};

struct node {
  int dis, u;

  bool operator>(const node& a) const { return dis > a.dis; }
};

vector<edge> e[MAXN];
int dis[MAXN], vis[MAXN];
priority_queue<node, vector<node>, greater<node>> q;

void dijkstra(int n, int s) {
  memset(dis, 0x3f, (n + 1) * sizeof(int));
  memset(vis, 0, (n + 1) * sizeof(int));
  dis[s] = 0;
  q.push({0, s});
  while (!q.empty()) {
    int u = q.top().u;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push({dis[v], v});
      }
    }
  }
}
```)

== 树状数组

#code_snippet(```cpp
int C[MAXN];
int lowbit(int x) {return x&(-x);}  // 计算x二进制下只保留最低位1后的值
vector<int> A(1,0);
struct BIT{ // 树状数组
  int n;
  //所有数组统一从下标1开始使用！！！
  BIT(vector<int>& A){  // 初始化，O(nlogn)
    n = A.size() - 1;
    for(int i = 1; i < A.size(); ++i)
      add(i, A[i]); // 从C[1]开始插入
  }
  int sum(int x){  // 前缀和[1, x]
    int ret = 0;
    while(x > 0){ ret += C[x]; x-= lowbit(x);}
    return ret;
  }
  int query(int L, int R){  // 查询操作，O(logn)
    return sum(R) - sum(L-1);
  }
  void add(int x, int d){ // 修改操作，O(logn)
    while(x <= n){
      C[x] += d; x += lowbit(x);
    }
  }
};
```)

== 线段树

与树状数组的基本思路类似，都是维护一段的信息。支持
- `update(x, v)`，将$A_x$修改为$v$：$O(log n)$。
- `query(L, R)`，求集合${A_L, A_(L + 1), dots, A_R}$的min，max，sum或者其它性质。这个性质必须满足结合律。

#code_snippet(```cpp
struct SegmentTree{ // 区间求和型,所有下标从1开始!!!
  int n;                        // 元素个数
  int *a;
  int d[2 * MAXN - 1];        // 保存节点信息
  SegmentTree(int N, int *A){
    n = N; a = A;    // 传入初始数组
    build(1, n, 1);
  }
  void build(int s, int t, int p) {   // build(1, n, 1)
    // 对 [s,t] 区间建立线段树,当前根的编号为 p
    if (s == t) { d[p] = a[s]; return;}
    int m = (s + t) / 2;
    build(s, m, p * 2), build(m + 1, t, p * 2 + 1); // 递归对左右区间建树
    d[p] = d[p * 2] + d[(p * 2) + 1];  // 【求和】
  }
  void update(int x, int v, int s, int t, int p){  // 将A[x]修改为v
    // update(x, v, 1, n, 1);
    if(x == s && x == t) return;
    d[p] += v - a[x]; a[x] = v;  // 【更新】
    int m = (s + t) >> 1;
    if (s <= x && x <= m) update(x, v, s, m, p * 2);
    else update(x, v, m + 1, t, p * 2 + 1);
  }
  int query_sum(int le, int ri, int s, int t, int p) {  // 计算区间和
    // query_sum(le, ri, 1, n, 1);
    // [le,ri] 为查询区间,[s,t] 为当前节点包含的区间,p 为当前节点的编号
    if (le <= s && t <= ri)
      return d[p];  // 当前区间为询问区间的子集时直接返回当前区间的和
    int m = (s + t) >> 1, sum = 0;
    if (le <= m) sum += query_sum(le, ri, s, m, p * 2);
    if (ri > m)  sum += query_sum(le, ri, m + 1, t, p * 2 + 1);
    return sum;
  }
};
```)

== 并查集

#code_snippet(```cpp
#define MAXNODE 5005
struct uf_set{
  int f[MAXNODE], SIZE;
  int size[MAXNODE]; // 子树大小，初始为1
  uf_set(int s): SIZE(s) {
    _for(i, 0, SIZE) f[i] = i;  // i就在它本身的集合里
    _for(i, 0, SIZE) size[i] = 1;
  }
  int find(int x){ // ≈ O(!)
      return (f[x] == x) ? x: f[x] = find(f[x]); // 路径压缩
  }
  void Union(int x, int y){
    int xx = find(x), yy = find(y);
    if (xx == yy) return;
    if (size[xx] > size[yy])  //启发式合并，保证小的合到大的里
      swap(xx, yy);
    f[xx] = yy;
    size[yy] += size[xx];
  }
};
```)