Competitive Programming Guide

https://oi-wiki.org/
Admin
This project provides a comprehensive guide and documentation for competitive programming, covering...
Tokens:289,534
Snippets:2,055
Trust Score:9.7
Update:3 months ago
Show doc for...
Tokens:
Raw
### Install Xubuntu Desktop for a Full GUI Experience

Source: https://oi-wiki.org/tools/wsl

Installs the complete Xubuntu desktop environment, providing a richer graphical experience than just Xfce. This is suitable if a more comprehensive desktop is desired.

```bash
$ sudo apt install xubuntu-desktop -y
```

--------------------------------

### Install Third-Party Library with Pip

Source: https://oi-wiki.org/lang/python

Use pip to install packages from PyPI, specifying a mirror if needed. Ensure pip is installed (default in Python 3.4+).

```bash
pip install -i https://mirrors.tuna.tsinghua.edu.cn/pypi/web/simple <some-package>
```

--------------------------------

### Install Xfce Desktop Environment and VNC Server

Source: https://oi-wiki.org/tools/wsl

Installs the Xfce desktop environment and a VNC server, preparing the WSL instance for graphical remote access. This is an alternative for users whose WSL version does not support WSLg.

```bash
$ sudo apt install xfce4 tightvncserver -y
```

--------------------------------

### Install Essential Build Tools and Editors in WSL

Source: https://oi-wiki.org/tools/wsl

Installs a comprehensive set of development tools including compilers, debuggers, and text editors. This is a foundational setup for compiling code and general development within WSL.

```bash
# apt install -y build-essential vim ddd gdb fpc emacs gedit anjuta lazarus
```

--------------------------------

### Start gdb session

Source: https://oi-wiki.org/tools/compile-debug

Compile 'a.cpp' with debug information and then launch the gdb debugger for the resulting executable 'a'.

```bash
$ g++ a.cpp -o a -g
$ gdb ./a
```

--------------------------------

### Bitwise OR Example

Source: https://oi-wiki.org/math/bit

Demonstrates the bitwise OR operation. For 01010011 OR 00110010, the result is 01110011.

```text
01010011 OR 00110010 = 01110011
```

--------------------------------

### Install Chinese Man Pages and Configure Manpath

Source: https://oi-wiki.org/tools/wsl

Installs Chinese man pages and modifies the manpath configuration to point to the Chinese man page directory. This allows 'man' commands to display help in Chinese.

```bash
# apt install manpages-zh
# sed -i 's|/usr/share/man|/usr/share/man/zh_CN|g' /etc/manpath.config
```

--------------------------------

### Bitwise AND Example

Source: https://oi-wiki.org/math/bit

Demonstrates the bitwise AND operation. For 01010011 AND 00110010, the result is 00010010.

```text
01010011 AND 00110010 = 00010010
```

--------------------------------

### Return Value Optimization (RVO) Example (C++)

Source: https://oi-wiki.org/lang/value-category

Shows how Return Value Optimization (RVO) can reduce temporary object creation and destruction, even when constructors and destructors have side effects. This example demonstrates a single construction and copy construction.

```cpp
struct X {
  X() { std::puts("X::X()"); }

  X(const X &) { std::puts("X::X(const X &)"); }

  ~X() { std::puts("X::~X()"); }
};

X get() {
  X x;
  return x;
}

int main() {
  X x = get();
  X y = X(X(X(X(x))));
  return 0;
}
```

--------------------------------

### Bitwise XOR Example

Source: https://oi-wiki.org/math/bit

Demonstrates the bitwise XOR operation. For 01010011 XOR 00110010, the result is 01100001.

```text
01010011 XOR 00110010 = 01100001
```

--------------------------------

### Function Inlining Example

Source: https://oi-wiki.org/lang/optimizations

Demonstrates a standard function call where parameters are passed and registers might be saved. This incurs overhead compared to inlining.

```C
int add(int x) { return x + 1; }

int foo() {
  int a = 1;
  a = add(a);
}
```

--------------------------------

### Lambda Capture Clause Examples

Source: https://oi-wiki.org/lang/lambda

Demonstrates various ways to capture variables in a lambda, including by value, by reference, and using initializers.

```C++
int a = 0;
auto f0 = []() { return a * 9; };   // Error, 无法访问 'a'
auto f1 = [a]() { return a * 9; };  // OK, 'a' 被值「捕获」
auto f2 = [&a]() { return a++; };   // OK, 'a' 被引用「捕获」
auto f3 = [v = a + 1]() {
  return v + 1;
};  // OK, 使用初始化器声明变量 v，类型与 a 相同

// 注意，使用引用捕获时，请保证被调用时 a 没有被销毁
auto b = f2();  // f2 从捕获列表里获得 a 的值，无需通过参数传入 a

```

--------------------------------

### Install Chinese Language Pack and Fonts for WSL

Source: https://oi-wiki.org/tools/wsl

Installs the Chinese language pack, font configuration, and necessary CJK fonts for proper display within WSL. After installation, reconfigure locales to select Chinese.

```bash
# apt install language-pack-zh-hans -y
# apt install fontconfig -y
# apt install fonts-noto-cjk fonts-wqy-microhei fonts-wqy-zenhei -y # 中文字体
# dpkg-reconfigure locales
```

--------------------------------

### Get Size of Subtree in Red-Black Tree

Source: https://oi-wiki.org/ds/rbtree

Helper function to get the size of a subtree rooted at 'p'. Returns 0 if 'p' is nullptr.

```cpp
static auto size(const_pointer p) -> size_t { return p ? p->sz : 0; }
```

--------------------------------

### Initialize LinkedList Instances

Source: https://oi-wiki.org/lang/java-pro

Shows how to create LinkedList instances, both empty and initialized with elements from another list.

```java
import java.io.PrintWriter;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        List<Integer> list1 = new LinkedList<>();  // 创建一个名字为 list1 的双链表 
        List<Integer> list2 = new LinkedList<>(list1);  // 创建一个名字为 list2 的双链表，将 list1 内所有元素加入进来 
    }
}
```

--------------------------------

### Install Xterm in WSL

Source: https://oi-wiki.org/tools/wsl

Installs the xterm terminal emulator within the WSL environment. This is a prerequisite for using Xming or other X server clients to display graphical applications.

```bash
# apt install xterm -y
```

--------------------------------

### Initialize ArrayList Instances

Source: https://oi-wiki.org/lang/java-pro

Demonstrates creating ArrayList instances with default capacity, a specified initial capacity, and by copying elements from another list.

```java
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);

    public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>();  // 创建一个名字为 list1 的可自增数组，初始长度为默认值（10）
        List<Integer> list2 = new ArrayList<>(30);  // 创建一个名字为list2的可自增数组，初始长度为 30
        List<Integer> list3 = new ArrayList<>(list2);  // 创建一个名字为 list3 的可自增数组，使用 list2 里的元素和 size 作为自己的初始值
    }
}
```

--------------------------------

### Activate Xfce Session via Xming

Source: https://oi-wiki.org/tools/wsl

Starts the Xfce desktop environment session, directing its graphical output to the Xming X server. This allows for a full graphical desktop experience from within WSL.

```bash
$ xfce4-session
```

--------------------------------

### Dead Code Elimination Example

Source: https://oi-wiki.org/lang/optimizations

Shows how unused code, including variables and computations, is removed by the compiler. This example first applies constant folding, then eliminates inactive variables and their calculations.

```cpp
int test() {
  int a = 233;
  int b = a * 2;
  int c = 234;
  return c;
}
```

```cpp
int test() { return 234; }
```

--------------------------------

### Compile and Run a C++ Program in WSL

Source: https://oi-wiki.org/tools/wsl

Demonstrates the process of creating a C++ source file, compiling it using g++, and then executing the compiled program within the WSL environment. Note that executable files do not require an extension.

```bash
$ vim cpuid.cpp
...
$ g++ -Wall cpuid.cpp -o cpuid
$ ./cpuid
AMD Ryzen 5 1400 Quad-Core Processor
```

--------------------------------

### Configure and Restart XRDP Service for Remote Desktop

Source: https://oi-wiki.org/tools/wsl

Installs XRDP, sets the default session to Xfce, and restarts the XRDP service. This configures WSL to accept remote desktop connections using the XRDP protocol.

```bash
$ sudo apt install xrdp -y
$ echo "xfce4-session" >~/.xsession
$ sudo service xrdp restart
```

--------------------------------

### Basic Block Placement Example

Source: https://oi-wiki.org/lang/optimizations

Illustrates two different layouts for basic blocks. Layout 2 places hot code blocks contiguously, reducing execution cost compared to Layout 1 which incurs high cost due to spanning many instructions.

```C++
// clang-format off
hotblock1:
    Stmts; // <-- 热！
    if (/* 边界条件不成立 */ true)
        goto hotblock2; // 经常发生！ ------+
coldblock:                           /*   |   */
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |  跨越了大量指令，代价高昂！
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
    Stmt; // <- 冷                        |
hotblock2:                          /*    |   */
    Stmts; // <- 热！           <----------+
```

```C++
// clang-format off
hotblock1:
    Stmts; // <-- 热！
    if (/* 边界条件 */ false)
        goto coldblock; // 很少发生
hotblock2:                         /*   |  低代价！  */
    Stmts; // <- 热！  <-----------------+
coldblock:
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
    Stmt; // <- 冷
```

--------------------------------

### List Operations: Add, Get, Set, Size Comparison

Source: https://oi-wiki.org/lang/java-pro

Compares the time complexity of common List operations (add, get, set, size) between ArrayList and LinkedList. Note the performance differences for indexed access and insertion/deletion.

```java
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {
    static PrintWriter out = new PrintWriter(System.out);
    static List<Integer> array = new ArrayList<>();
    static List<Integer> linked = new LinkedList<>();

    static void add() {
        array.add(1);  // 时间复杂度为 O(1) 
        linked.add(1);  // 时间复杂度为 O(1) 
    }

    static void get() {
        array.get(10);  // 时间复杂度为 O(1) 
        linked.get(10);  // 时间复杂度为 O(11) 
    }

    static void addIdx() {
        array.add(0, 2);  // 最坏情况下时间复杂度为 O(n)
        linked.add(0, 2);  // 最坏情况下时间复杂度为 O(n)
    }

    static void size() {
        array.size();  // 时间复杂度为 O(1)
        linked.size();  // 时间复杂度为 O(1)
    }

    static void set() {  // 该方法返回值为原本该位置元素的值
        array.set(0, 1);  // 时间复杂度为 O(1)
        linked.set(0, 1);  // 最坏时间复杂度为 O(n)
    }

}
```

--------------------------------

### Recommended Link Formatting

Source: https://oi-wiki.org/intro/format

When creating links, provide a complete title or a recognizable hint. Avoid bare URLs or vague descriptions like 'this' or 'here'.

```Markdown
请参考 GitHub 官方的帮助页面 [Syncing a fork - GitHub Docs](https://docs.github.com/en/github/collaborating-with-issues-and-pull-requests/syncing-a-fork)
```

```Markdown
请参考 GitHub 官方的帮助页面 Syncing a fork - GitHub Docs
```

--------------------------------

### Linked List Assign Operation

Source: https://oi-wiki.org/misc/odt

Assigns a new value 'val' to the range [l, r]. It first calls 'prepare' to split the list, then modifies the 'r' and 'val' of the block starting at 'l' (pointed to by 'lb'), and links it to the block starting after 'r' (pointed to by 'rb').

```cpp
void assign(int l, int r, i64 val) {
  prepare(l, r);
  lb->r = r;  // 将区间 [lb.l, lb.r] 修改成 [lb.l, r]
  lb->val = val;
  lb->next = rb;  // 将 [lb.l, r] 链至其右侧相邻区间
}

// 注：这里没有释放被删除节点的内存，若有需要可自行添加
```

--------------------------------

### Linked List Prepare Operation

Source: https://oi-wiki.org/misc/odt

Prepares for range operations by splitting the linked list at 'l-1' and 'r'. This ensures that the subsequent operations are confined within the desired range [l, r]. 'lb' points to the block starting at or before 'l', and 'rb' points to the block starting at or after 'r'.

```cpp
Block *lb, *rb;

// 预分裂，保证后续操作在 [l, r] 内部
void prepare(int l, int r) {
  lb = split(l - 1);
  rb = split(r);
}
```

--------------------------------

### Red-Black Tree Operations Example

Source: https://oi-wiki.org/ds/rbtree

Demonstrates various operations on a Red-Black tree, including insertion, deletion, finding order of key, finding by order, and finding neighbors. Ensure proper initialization and input handling for these operations.

```cpp
int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  io.init();
  std::size_t n = io.n, m = io.m;
  rb_tree<std::pair<int, int>> bt;
  int cnt = 0;
  for (auto i : io.a) bt.insert(std::make_pair(i, cnt++));
  for (int i = 0, opt, x; (std::size_t)i < m; ++i) {
    opt = io.opt(), x = io.x();
    switch (opt) {
      case 1:
        bt.insert({x, cnt++});
        break;
      case 2:
        bt.erase(bt.lower_bound({x, 0}));
        break;
      case 3:
        io.print((int)bt.order_of_key({x, 0}) + 1);
        break;
      case 4:
        io.print(bt.find_by_order((uint32_t)x - 1)->data.first);
        break;
      case 6:
        io.print(bt.upper_bound({x, n + m})->data.first);
        break;
      case 5:
        auto it = bt.lower_bound({x, 0});
        io.print((it ? bt.prev(it) : bt.rightmost(bt.root))->data.first);
        break;
    }
  }
  io.print_total_ans();
  return 0;
}
```

--------------------------------

### Configure C++ Debugger (LLDB)

Source: https://oi-wiki.org/tools/editor/vscode

Configure the LLDB debugger using the CodeLLDB extension. After initial GDB setup, modify launch.json to use LLDB and adjust the program path.

```json
{
    "version": "0.2.0",
    "configurations": [
        {
            "name": "LLDB",
            "type": "cppdbg",
            "request": "launch",
            "program": "${fileDirname}/${fileBasenameNoExtension}",
            "args": [],
            "stopAtEntry": false,
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "lldb"
        }
    ]
}
```

--------------------------------

### Bitwise NOT Example

Source: https://oi-wiki.org/math/bit

Demonstrates the bitwise NOT operation. Note that NOT 01010111 results in 10101000.

```text
NOT 01010111 = 10101000
```

--------------------------------

### Integer Promotion Example: Bool

Source: https://oi-wiki.org/lang/var

Demonstrates integer promotion of bool. The operation 'false - (unsigned short)12' promotes 'false' to int, then performs an int calculation.

```cpp
false - (unsigned short)12
```

--------------------------------

### Get Size of Set

Source: https://oi-wiki.org/ds/llrbt

Returns the total number of nodes currently in the Red-Black Tree.

```cpp
template <class Key, class Compare>
typename Set<Key, Compare>::SizeType Set<Key, Compare>::size() const {
  return size(root_);
}
```

--------------------------------

### Retrieving Value or Default

Source: https://oi-wiki.org/ds/sbt

Gets the value for a key, or inserts a default value if the key is not present.

```C++
  /**
   * Returns the value to which the specified key is mapped; If this map
   * contains no mapping for the key, a new mapping with a default value
   * will be inserted.
   * @param key
   * @return SizeBalancedTreeMap<Key, Value>::Value &
   */
  Value &getOrDefault(K key) {
    if (this->root == nullptr) {
      this->root = Node::from(key);
      return this->root->value;
    }
    return this->getNodeOrProvide(this->root, key, [&key]() { return Node::from(key); })->value;
  }
```

--------------------------------

### Priority Queue Operations with Pairing Heap

Source: https://oi-wiki.org/lang/pb-ds/pq

Demonstrates basic operations like push, top, pop, modify, erase, and join using a pairing heap from __gnu_pbds. This is useful for implementing algorithms that require efficient priority queue management.

```cpp
#include <algorithm>
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#include <iostream>
using namespace __gnu_pbds;
// 由于面向OIer, 本文以常用堆 : pairing_heap_tag作为范例
// 为了更好的阅读体验，定义宏如下 ：
using pair_heap = __gnu_pbds::priority_queue<int>;
pair_heap q1;  // 大根堆, 配对堆
pair_heap q2;
pair_heap::point_iterator id;  // 一个迭代器

int main() {
  id = q1.push(1);
  // 堆中元素 ： [1];
  for (int i = 2; i <= 5; i++) q1.push(i);
  // 堆中元素 :  [1, 2, 3, 4, 5];
  std::cout << q1.top() << std::endl;
  // 输出结果 : 5;
  q1.pop();
  // 堆中元素 : [1, 2, 3, 4];
  id = q1.push(10);
  // 堆中元素 : [1, 2, 3, 4, 10];
  q1.modify(id, 1);
  // 堆中元素 :  [1, 1, 2, 3, 4];
  std::cout << q1.top() << std::endl;
  // 输出结果 : 4;
  q1.pop();
  // 堆中元素 : [1, 1, 2, 3];
  id = q1.push(7);
  // 堆中元素 : [1, 1, 2, 3, 7];
  q1.erase(id);
  // 堆中元素 : [1, 1, 2, 3];
  q2.push(1), q2.push(3), q2.push(5);
  // q1中元素 : [1, 1, 2, 3], q2中元素 : [1, 3, 5];
  q2.join(q1);
  // q1中无元素，q2中元素 ：[1, 1, 1, 2, 3, 3, 5];
}
```

--------------------------------

### Retrieving a Value by Key

Source: https://oi-wiki.org/ds/sbt

Gets the value associated with a key. Throws NoSuchMappingException if the key is not found.

```C++
  /**
   * Returns the value to which the specified key is mapped; If this map
   * contains no mapping for the key, a {@code NoSuchMappingException} will
   * be thrown.
   * @param key
   * @return SizeBalancedTreeMap<Key, Value>::Value
   * @throws NoSuchMappingException
   */
  Value get(K key) const {
    if (this->root == nullptr) {
      throw NoSuchMappingException("Invalid key");
    } else {
      NodePtr node = this->getNode(this->root, key);
      if (node != nullptr) {
        return node->value;
      }
      throw NoSuchMappingException("Invalid key");
    }
  }
```

--------------------------------

### Remove Value from WBLT

Source: https://oi-wiki.org/ds/wblt

Public interface to remove a value from the WBLT, starting the operation from the root.

```C++
// Remove v.
bool remove(int v) { return remove(rt, v); }
```

--------------------------------

### Main Function for DSU on Tree Setup and Querying

Source: https://oi-wiki.org/graph/dsu-on-tree

Handles input reading for tree structure, node colors, and queries. It orchestrates the DSU on Tree algorithm by calling the necessary DFS functions and then processes the queries to output the answers.

```cpp
#define N 100005
vector<int> g[N];
int n, m;

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    g[u].push_back(v);
    g[v].push_back(u);
  }
  for (int i = 1; i <= n; i++) scanf("%d", &col[i]);
  dfs0(1, 1);
  dfs1(1, 1);
  dsu_on_tree();
  scanf("%d", &m);
  for (int i = 1; i <= m; i++) {
    int q;
    scanf("%d", &q);
    printf("%d\n", ans[q]);
  }
  return 0;
}
```

--------------------------------

### Min-Cost Max-Flow using Primal-Dual Algorithm (C++)

Source: https://oi-wiki.org/graph/flow/min-cost

This C++ implementation demonstrates the Primal-Dual algorithm for min-cost max-flow. It uses SPFA to initialize potentials and Dijkstra with potentials for finding augmenting paths. The potentials are updated after each augmentation.

```cpp
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
constexpr int INF = 0x3f3f3f3f;
using namespace std;

struct edge {
  int v, f, c, next;
} e[100005];

struct node {
  int v, e;
}
p[10005];

struct mypair {
  int dis, id;

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

  mypair(int d, int x) { dis = d, id = x; }
};

int head[5005], dis[5005], vis[5005], h[5005];
int n, m, s, t, cnt = 1, maxf, minc;

void addedge(int u, int v, int f, int c) {
  e[++cnt].v = v;
  e[cnt].f = f;
  e[cnt].c = c;
  e[cnt].next = head[u];
  head[u] = cnt;
}

bool dijkstra() {
  priority_queue<mypair> q;
  for (int i = 1; i <= n; i++) dis[i] = INF;
  memset(vis, 0, sizeof(vis));
  dis[s] = 0;
  q.push(mypair(0, s));
  while (!q.empty()) {
    int u = q.top().id;
    q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v, nc = e[i].c + h[u] - h[v];
      if (e[i].f && dis[v] > dis[u] + nc) {
        dis[v] = dis[u] + nc;
        p[v].v = u;
        p[v].e = i;
        if (!vis[v]) q.push(mypair(dis[v], v));
      }
    }
  }
  return dis[t] != INF;
}

void spfa() {
  queue<int> q;
  memset(h, 63, sizeof(h));
  h[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    vis[u] = 0;
    for (int i = head[u]; i; i = e[i].next) {
      int v = e[i].v;
      if (e[i].f && h[v] > h[u] + e[i].c) {
        h[v] = h[u] + e[i].c;
        if (!vis[v]) {
          vis[v] = 1;
          q.push(v);
        }
      }
    }
  }
}

int main() {
  scanf("%d%d%d%d", &n, &m, &s, &t);
  for (int i = 1; i <= m; i++) {
    int u, v, f, c;
    scanf("%d%d%d%d", &u, &v, &f, &c);
    addedge(u, v, f, c);
    addedge(v, u, 0, -c);
  }
  spfa();  // 先求出初始势能
  while (dijkstra()) {
    int minf = INF;
    for (int i = 1; i <= n; i++) h[i] += dis[i];
    for (int i = t; i != s; i = p[i].v) minf = min(minf, e[p[i].e].f);
    for (int i = t; i != s; i = p[i].v) {
      e[p[i].e].f -= minf;
      e[p[i].e ^ 1].f += minf;
    }
    maxf += minf;
    minc += minf * h[t];
  }
  printf("%d %d\n", maxf, minc);
  return 0;
}

```

--------------------------------

### Insert Value into WBLT

Source: https://oi-wiki.org/ds/wblt

Public interface to insert a value into the WBLT, starting the operation from the root.

```C++
// Insert v.
void insert(int v) { insert(rt, v); }
```

--------------------------------

### Custom `read` and `write` using `getchar`/`putchar`

Source: https://oi-wiki.org/contest/io

Implements fast integer input and output using `getchar` and `putchar` with manual buffering. This is useful for competitive programming when standard I/O is too slow.

```C++
void read(int &x) {
  bool neg = false;
  x = 0;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') neg = true;
    ch = getchar();
  }
  if (neg) {
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + ('0' - ch);
      ch = getchar();
    }
  } else {
    while (ch >= '0' && ch <= '9') {
      x = x * 10 + (ch - '0');
      ch = getchar();
    }
  }
}

void write(int x) {
  bool neg = false;
  if (x < 0) {
    neg = true;
    putchar('-');
  }
  static int sta[40];
  int top = 0;
  do {
    sta[top++] = x % 10;
    x /= 10;
  } while (x);
  if (neg)
    while (top) putchar('0' - sta[--top]);
  else
    while (top) putchar('0' + sta[--top]);
}
```

--------------------------------

### Map Size and Emptiness Check

Source: https://oi-wiki.org/ds/sbt

Provides methods to get the number of entries and check if the map is empty.

```C++
  /**
   * Returns the number of entries in this map.
   * @return size_t
   */
  inline USize size() const noexcept {
    if (this->root != nullptr) {
      return this->root->size;
    } else {
      return 0;
    }
  }

  /**
   * Returns true if this collection contains no elements.
   * @return bool
   */
  inline bool empty() const noexcept { return this->root == nullptr; }
```

--------------------------------

### Array Environment for Mathematical Formulas

Source: https://oi-wiki.org/intro/format

Demonstrates the correct usage of the array environment for displaying mathematical formulas with specified column alignment. Ensure the number of alignment specifiers matches the actual number of columns.

```latex
$$\begin{array}{lll}
F_1=\{\frac{0}{1},, \frac{1}{1}\}\\
F_2=\{\frac{0}{1},&\frac{1}{2},&\frac{1}{1}\}\\
\end{array}$$
```

--------------------------------

### Range-Based For Loop Example

Source: https://oi-wiki.org/lang/new

Iterates through elements of a `std::array` and prints each element. This is equivalent to using iterators.

```cpp
std::array<int, 4> arr = {1, 2, 3, 4};
for (int x : arr) {
  std::cout << x << std::endl;
}
```
Tokens:
Raw