VSCode C++ 配置与模板
设置¶
settings.json¶
{
// 删除文件不确认
"explorer.confirmDelete": false,
// 移动文件不确认
"explorer.confirmDragAndDrop": false,
// 添加希望被忽略的文件,这样一些文件虽然存在于当前工作目录下,但是不会被显示在左侧的文件浏览器里
"files.exclude": {
// dSYM 文件具有调试信息,普通使用的话不看到它就可以了
"**/*.exe": true,
"**/*.out": true,
".cph": true,
".clang-format": true,
},
// 启用 code-runner 快捷键
"workspaceKeybindings.code-runner.enable": true,
"code-runner.executorMap": {
/* ------ 编译、运行只有一个文件的cpp文件 ------ */
// 注：路径中有空格不会出现问题
"cpp": "clang++ $fullFileName -o $workspaceRoot/main.out -W -Wall -O2 -std=c++20 -stdlib=libc++ -I$workspaceRoot/lib && $workspaceRoot/main.out",
// 其中 $fullFileName 是绝对路径，是主文件
// 自己决定是否加入 && rm $dir\"$fileNameWithoutExt\"\".out\"（也可以添加"files.exclude"）
/* ------ 编译、运行多个cpp文件 ------ */
// "cpp": "g++ $fullFileName <file_to_link> -o $dir\"$fileNameWithoutExt\"\".out\" -W -Wall -O2 -std=c++20 && $dir\"$fileNameWithoutExt\"\".out\"",
// <file_to_link>的写法：
// 一般的，你也可以直接写绝对路径
// \"/path/xxxx.cpp\"
// 如果你链接的cpp文件和主文件在一个目录下：
// $dir\"xxxx.cpp\"
// 更一般的，如果你链接的cpp文件不和主文件在一个目录下，需要从当前VSCode的工作目录补充相对路径从而形成绝对路径：
// $workspaceRoot\"relative/path/xxxx.cpp\"
/* ------ 编译c文件 ------ */
"c": "clang $fullFileName -o $workspaceRoot/main.out -W -Wall -O2 -std=c11 && $workspaceRoot/main.out",
// "c": "gcc $fullFileName <file_to_link> -o $dir\"$fileNameWithoutExt\"\".out\" -W -Wall -O2 -std=c17 && $dir\"$fileNameWithoutExt\"\".out\"",
},
// Whether to clear previous output before each run (default is false):
"code-runner.clearPreviousOutput": true,
// Whether to save all files before running (default is false):
"code-runner.saveAllFilesBeforeRun": false,
// Whether to save the current file before running (default is false):
"code-runner.saveFileBeforeRun": true,
// Whether to show extra execution message like [Running] ... and [Done] ... (default is true):
"code-runner.showExecutionMessage": true, // cannot see that message is you set "code-runner.runInTerminal" to true
// Whether to run code in Integrated Terminal (only support to run whole file in Integrated Terminal, neither untitled file nor code snippet) (default is false):
"code-runner.runInTerminal": true, // cannot input data when setting to false
// Whether to preserve focus on code editor after code run is triggered (default is true, the code editor will keep focus; when it is false, Terminal or Output Channel will take focus):
"code-runner.preserveFocus": false,
// Whether to ignore selection to always run entire file. (Default is false)
"code-runner.ignoreSelection": true,
// 本地 clangd 路径
// "clangd.path": "/usr/bin/clangd",
"clangd.arguments": [
// "--header-insertion=never", // 是否重复插入头文件，用万能头的话设置成never
"--query-driver=/usr/bin/clang++", // 将编译的所有工具链都添加进 LSP
"--log=verbose"
],
// 没有找到 compile_commands.json 时默认的编译器参数是什么
"clangd.fallbackFlags": [
"-W",
"-Wall",
"-O2",
"-std=c++20",
"-stdlib=libc++",
"-I/root/cpp/lib",
],
"C_Cpp.intelliSenseEngine": "disabled",
"lldb.launch.expressions": "native",
}
launch.json¶
{
// One of the key features of Visual Studio Code is its great debugging support.
// VS Code's built-in debugger helps accelerate your edit, compile and debug loop.
// VS Code keeps debugging configuration information in a launch.json file
// located in a .vscode folder in your workspace (project root folder).
"version": "0.2.0",
"configurations": [
{
"type": "lldb", // lldb 表示使用 CodeLLDB 来调试
"request": "launch", // 启动调试
"name": "C++ Debug", // launch 配置的名字
"preLaunchTask": "clang++ compile", // 启动调试任务前先执行 task.json 的 "clang++ compile"
"program": "${workspaceFolder}/main.out", // 调试的程序
"args": [], // 程序参数
"env": {}, // 环境变量
"cwd": "${workspaceFolder}",
"stopOnEntry": false, // 调试开始时在 main 函数中停止
"terminal": "integrated", // 使用 vscode 自带的终端进行调试
}
]
}
task.json¶
{
// Tasks in VS Code can be configured to run scripts and start processes
// so that many of these existing tools can be used from within VS Code
// without having to enter a command line or write new code.
// Workspace or folder specific tasks are configured from the tasks.json file in the .vscode folder for a workspace.
"version": "2.0.0",
"tasks": [
{
// The task's label used in the user interface.
// Terminal -> Run Task... 看到的名字
"label": "clang++ compile",
// The task's type. For a custom task, this can either be shell or process.
// If shell is specified, the command is interpreted as a shell command (for example: bash, cmd, or PowerShell).
// If process is specified, the command is interpreted as a process to execute.
"type": "shell", // shell: 输入命令
// The actual command to execute.
// 因为g++已经在环境变量中了，所以我们这里写命令就行不用写g++的绝对路径
"command": "clang++",
"args": [
"${file}", // 表示当前文件（绝对路径）
// 在这里添加你还需要链接的.cpp文件
"-o",
"${workspaceFolder}/main.out",
"-W",
"-Wall",
"-g",
"-std=c++20",
"-stdlib=libc++",
"-I",
"${workspaceFolder}/lib",
// "-fstandalone-debug",
],
// Defines to which execution group this task belongs to.
// It supports "build" to add it to the build group and "test" to add it to the test group.
// Tasks that belong to the build/test group can be executed by running Run Build/Test Task from the Command Palette (sft cmd P).
// Valid values:
// "build",
// {"kind":"build","isDefault":true},
// "test",
// {"kind":"test","isDefault":true},
// "none".
"group": {
"kind": "build",
"isDefault": true, // Defines if this task is the default task in the group.
},
// Configures the panel that is used to present the task's output and reads its input.
"presentation": {
// Controls whether the executed command is echoed to the panel. Default is true.
"echo": true, // 打开可以看到编译的命令，把命令本身输出一次
// Controls whether the terminal running the task is revealed or not. Default is "always".
// always: Always reveals the terminal when this task is executed.
// silent: Only reveals the terminal if the task exits with an error or the problem matcher finds an error.(会显示错误，但不会显示警告)
// never: Never reveals the terminal when this task is executed.
"reveal": "silent", // 控制在集成终端中是否显示。如果没问题那我不希望终端被切换、如果有问题我希望能看到编译过程哪里出错，所以选silent(可能always会好一些)
// Controls whether the panel takes focus. Default is false.
"focus": false, // 我的理解是：是否将鼠标移过去。因为这个是编译任务，我们不需要输入什么东西，所以选false
// Controls if the panel is shared between tasks, dedicated to this task or a new one is created on every run.
"panel": "shared", // shared:不同任务的输出使用同一个终端panel（为了少生成几个panel我们选shared）
// Controls whether to show the `Terminal will be reused by tasks, press any key to close it` message.
"showReuseMessage": true, // 就一句话，你想看就true，不想看就false
// Controls whether the terminal is cleared before executing the task.
"clear": false, // 还是保留之前的task输出信息比较好。所以不清理
},
// Other two choices: options & runOptions (cmd I to use IntelliSense)
"options": {
// The current working directory of the executed program or script. If omitted Code's current workspace root is used.
"cwd": "${workspaceFolder}", // 默认就是这个，删掉也没问题
},
// problemMatcher: 用正则表达式提取g++的输出中的错误信息并将其显示到VS Code下方的Problems窗口
// check: https://code.visualstudio.com/docs/editor/tasks#_defining-a-problem-matcher
"problemMatcher": {
"owner": "cpp",
"fileLocation": "absolute",
"pattern": {
"regexp": "^(.*):(\\d+):(\\d+):\\s+(warning|error):\\s+(.*)$",
"file": 1,
"line": 2,
"column": 3,
"severity": 4,
"message": 5,
},
},
// 官网教程 https://code.visualstudio.com/docs/cpp/config-clang-mac#_build-helloworldcpp
// 提到了另一种problemMatcher，但试了之后好像不起作用，甚至还把我原本的电脑搞出了一些问题……
},
]
}
.clang-format¶
BasedOnStyle: LLVM
UseTab: Never
IndentWidth: 4
TabWidth: 4
BreakBeforeBraces: Allman
AllowShortIfStatementsOnASingleLine: false
IndentCaseLabels: false
ColumnLimit: 0
AccessModifierOffset: -4
NamespaceIndentation: All
FixNamespaceComments: false
算法模板¶
使用教程：
- 在 VSCode 工作区的 .vscode 文件夹下创建 XXX.code-snippets 文件，其中 XXX 表示工作区的名字，例如 cpp 工作区，就创建 cpp.code-snippets。
- 复制下列内容，粘贴进去。
- 使用 prefix 字段的快捷键就可以呼出代码模板，例如 tpdsu 就可以输出并查集模板。
- 快速生成新模板，参考 snippet generator
{
"C语言默认代码模板": {
"prefix": "cyy",
"body": [
"#include <stdio.h>",
"#include <string.h>",
"",
"$0",
"",
"int main()",
"{",
" return 0;",
"}"
],
"description": "C语言默认代码模板"
},
"C++默认代码模板": {
"prefix": "cpp",
"body": [
"#include <iostream>",
"",
"using namespace std;",
"$1",
"int main()",
"{",
"\t$0",
" return 0;",
"}"
],
"description": "C++默认代码模板"
},
"重定向标准输入到文件": {
"prefix": "tpfreopen",
"body": [
"freopen(\"in.txt\", \"r\", stdin);",
],
"description": "重定向标准输入到文件"
},
"cin快读": {
"prefix": "tpcin",
"body": [
"ios::sync_with_stdio(false);",
"cin.tie(nullptr);"
],
"description": "cin快读"
},
"并查集": {
"prefix": "tpdsu",
"body": [
"class DSU",
"{",
"public:",
" explicit DSU(int n) : parent_or_size(n, -1) {}",
"",
" int merge(int a, int b)",
" {",
" int x = leader(a), y = leader(b);",
" if (x == y)",
" return x;",
" if (-parent_or_size[x] < -parent_or_size[y])",
" swap(x, y);",
" parent_or_size[x] += parent_or_size[y];",
" parent_or_size[y] = x;",
" return x;",
" }",
"",
" int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }",
"",
" bool same(int a, int b) { return leader(a) == leader(b); }",
"",
" int size(int a) { return -parent_or_size[leader(a)]; }",
"",
"private:",
" vector<int> parent_or_size;",
"};"
],
"description": "并查集（按秩合并）"
},
"并查集(group)": {
"prefix": "tpdsu",
"body": [
"class DSU",
"{",
"public:",
" explicit DSU(int n) : parent_or_size(n, -1) {}",
"",
" int merge(int a, int b)",
" {",
" int x = leader(a), y = leader(b);",
" if (x == y)",
" return x;",
" if (-parent_or_size[x] < -parent_or_size[y])",
" swap(x, y);",
" parent_or_size[x] += parent_or_size[y];",
" parent_or_size[y] = x;",
" return x;",
" }",
"",
" int leader(int a) { return parent_or_size[a] < 0 ? a : parent_or_size[a] = leader(parent_or_size[a]); }",
"",
" bool same(int a, int b) { return leader(a) == leader(b); }",
"",
" int size(int a) { return -parent_or_size[leader(a)]; }",
"",
" vector<vector<int>> group()",
" {",
" int n = parent_or_size.size();",
" std::vector<int> leader_buf(n), group_size(n);",
" for (int i = 0; i < n; i++)",
" {",
" leader_buf[i] = leader(i);",
" group_size[leader_buf[i]]++;",
" }",
" std::vector<std::vector<int>> result(n);",
" for (int i = 0; i < n; i++)",
" result[i].reserve(group_size[i]);",
" for (int i = 0; i < n; i++)",
" result[leader_buf[i]].push_back(i);",
" result.erase(",
" std::remove_if(result.begin(), result.end(),",
" [&](const std::vector<int> &v)",
" { return v.empty(); }),",
" result.end());",
" return result;",
" }",
"",
"private:",
" vector<int> parent_or_size;",
"};"
],
"description": "并查集(支持group)"
},
"扩展欧几里得": {
"prefix": "tpexgcd",
"body": [
"pair<LL, LL> exgcd(LL a, LL b)",
"{",
" if (b == 0)",
" return {1, 0};",
" auto [x, y] = exgcd(b, a % b);",
" return {y, x - a / b * y};",
"}",
"",
"LL inv(LL a, LL p)",
"{",
" auto [x, y] = exgcd(a, p);",
" if (x < 0)",
" x += p;",
" return x;",
"}"
],
"description": "扩展欧几里得"
},
"树状数组": {
"prefix": "tpfenwick",
"body": [
"template <typename T>",
"class FenwickTree",
"{",
"public:",
" FenwickTree(int n) : n(n), t(n) {}",
"",
" void add(int x, T k)",
" {",
" for (; x < n; x += lowbit(x))",
" t[x] += k;",
" }",
"",
" T range(int l, int r) const { return prefix(r) - prefix(l - 1); }",
"",
"private:",
" int n;",
" vector<T> t;",
"",
" int lowbit(int x) const { return x & -x; }",
"",
" T prefix(int x) const",
" {",
" T ans = 0;",
" for (; x; x -= lowbit(x))",
" ans += t[x];",
" return ans;",
" }",
"};"
],
"description": "树状数组"
},
"树状数组(支持二分)": {
"prefix": "tpfenwick",
"body": [
"template <typename T>",
"class FenwickTree",
"{",
"public:",
" FenwickTree(int n) : n(n), t(n) {}",
"",
" void add(int x, T k)",
" {",
" for (; x < n; x += lowbit(x))",
" t[x] += k;",
" }",
"",
" int lower_bound(T k) const",
" {",
" int x = 0;",
" T sum = 0;",
" for (int i = 1 << (int)log2(n); i; i >>= 1)",
" {",
" if (x + i >= n || sum + t[x + i] >= k)",
" continue;",
" x += i;",
" sum += t[x];",
" }",
" return x + 1;",
" }",
"",
" T range(int l, int r) const { return prefix(r) - prefix(l - 1); }",
"",
"private:",
" int n;",
" vector<T> t;",
"",
" int lowbit(int x) const { return x & -x; }",
"",
" T prefix(int x) const",
" {",
" T ans = 0;",
" for (; x; x -= lowbit(x))",
" ans += t[x];",
" return ans;",
" }",
"};"
],
"description": "树状数组"
},
"线段树": {
"prefix": "tpsegtree",
"body": [
"#include <bit>",
"template <class S, auto op, auto e>",
"class SegTree",
"{",
"public:",
" explicit SegTree(int n) : SegTree(vector<S>(n, e())) {}",
"",
" explicit SegTree(const vector<S> &v) : n(v.size())",
" {",
" size = bit_ceil((unsigned int)n);",
" d = vector<S>(2 * size, e());",
" for (int i = 0; i < n; i++)",
" d[size + i] = v[i];",
" for (int i = size - 1; i >= 1; i--)",
" push_up(i);",
" }",
"",
" void set(int p, S x)",
" {",
" p += size;",
" d[p] = x;",
" for (p >>= 1; p; p >>= 1)",
" push_up(p);",
" }",
"",
" S get(int p) const { return d[p + size]; }",
"",
" S prod(int l, int r) const",
" {",
" S ansl = e(), ansr = e();",
" for (l += size, r += size; l < r; l >>= 1, r >>= 1)",
" {",
" if (l & 1)",
" ansl = op(ansl, d[l++]);",
" if (r & 1)",
" ansr = op(d[--r], ansr);",
" }",
" return op(ansl, ansr);",
" }",
"",
" S all_prod() const { return d[1]; }",
"",
"private:",
" int n, size;",
" vector<S> d;",
"",
" void push_up(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }",
"};"
],
"description": "线段树"
},
"线段树(支持二分)": {
"prefix": "tpsegtree",
"body": [
"#include <bit>",
"template <class S, auto op, auto e>",
"class SegTree",
"{",
"public:",
" explicit SegTree(int n) : SegTree(vector<S>(n, e())) {}",
"",
" explicit SegTree(const vector<S> &v) : n(v.size())",
" {",
" size = bit_ceil((unsigned int)n);",
" d = vector<S>(2 * size, e());",
" for (int i = 0; i < n; i++)",
" d[size + i] = v[i];",
" for (int i = size - 1; i >= 1; i--)",
" push_up(i);",
" }",
"",
" void set(int p, S x)",
" {",
" p += size;",
" d[p] = x;",
" for (p >>= 1; p; p >>= 1)",
" push_up(p);",
" }",
"",
" S get(int p) const { return d[p + size]; }",
"",
" S prod(int l, int r) const",
" {",
" S ans = e();",
" for (l += size, r += size; l < r; l >>= 1, r >>= 1)",
" {",
" if (l & 1)",
" ans = op(ans, d[l++]);",
" if (r & 1)",
" ans = op(d[--r], ans);",
" }",
" return ans;",
" }",
"",
" S all_prod() const { return d[1]; }",
"",
" template <bool (*f)(S)>",
" int max_right(int l) const",
" {",
" return max_right(l, [](S x)",
" { return f(x); });",
" }",
" template <class F>",
" int max_right(int l, F f) const",
" {",
" if (l == n)",
" return n;",
" l += size;",
" S sm = e();",
" do",
" {",
" while (l % 2 == 0)",
" l >>= 1;",
" if (!f(op(sm, d[l])))",
" {",
" while (l < size)",
" {",
" l = (2 * l);",
" if (f(op(sm, d[l])))",
" {",
" sm = op(sm, d[l]);",
" l++;",
" }",
" }",
" return l - size;",
" }",
" sm = op(sm, d[l]);",
" l++;",
" } while ((l & -l) != l);",
" return n;",
" }",
"",
" template <bool (*f)(S)>",
" int min_left(int r) const",
" {",
" return min_left(r, [](S x)",
" { return f(x); });",
" }",
" template <class F>",
" int min_left(int r, F f) const",
" {",
" if (r == 0)",
" return 0;",
" r += size;",
" S sm = e();",
" do",
" {",
" r--;",
" while (r > 1 && (r % 2))",
" r >>= 1;",
" if (!f(op(d[r], sm)))",
" {",
" while (r < size)",
" {",
" r = (2 * r + 1);",
" if (f(op(d[r], sm)))",
" {",
" sm = op(d[r], sm);",
" r--;",
" }",
" }",
" return r + 1 - size;",
" }",
" sm = op(d[r], sm);",
" } while ((r & -r) != r);",
" return 0;",
" }",
"",
"private:",
" int n, size;",
" vector<S> d;",
"",
" void push_up(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }",
"};"
],
"description": "线段树(支持二分)"
},
"线段树(动态开点))": {
"prefix": "tpdynamicsegtree",
"body": [
"#include <bit>",
"template <class S, auto op, auto e, auto m>",
"class DynamicSegTree",
"{",
"public:",
" explicit DynamicSegTree(int n, int q) : DynamicSegTree<S, op, e, m>(0, n, q) {}",
" explicit DynamicSegTree(int beg, int end, int q) : beg(beg), end(end)",
" {",
" int dep = countr_zero(bit_ceil((unsigned int)(end - beg))) + 1;",
" int t = countr_zero(bit_floor((unsigned)q));",
" int k = (dep - t) * q + (1 << (t + 1)) - q;",
" if (k < 0)",
" k = 1 << dep;",
" d = vector<S>(k, e());",
" ch = vector<pair<int, int>>(k, {0, 0});",
" }",
"",
" void add(int p, S k) { _add(root, beg, end, p, k); }",
"",
" S get(int p) { return _get(root, beg, end, p); }",
"",
" S prod(int l, int r) { return _prod(root, beg, end, l, r); }",
"",
" S all_prod() const { return d[root]; }",
"",
" template <bool (*f)(S)>",
" int max_right(int l) const",
" {",
" return max_right(l, [](S x)",
" { return f(x); });",
" }",
" template <class F>",
" int max_right(int l, F f)",
" {",
" const int INVALID = end;",
" S now = e();",
"",
" auto _max_right = [&](auto &&self, int p, int beg, int end) -> int",
" {",
" if (!p || end - 1 < l)",
" return INVALID;",
" if (beg >= l)",
" {",
" S ans = d[p];",
" if (f(op(now, ans)))",
" {",
" now = op(now, ans);",
" return INVALID;",
" }",
" if (beg + 1 == end)",
" return beg;",
" }",
" int mid = (beg + end) / 2;",
" int pos = self(self, lch(p), beg, mid);",
" return pos == INVALID ? self(self, rch(p), mid, end) : pos;",
" };",
"",
" return _max_right(_max_right, root, beg, end);",
" }",
"",
" template <bool (*f)(S)>",
" int min_left(int r)",
" {",
" return min_left(r, [](S x)",
" { return f(x); });",
" }",
" template <class F>",
" int min_left(int r, F f)",
" {",
" const int INVALID = beg - 1;",
" S now = e();",
"",
" auto _min_right = [&](auto &&self, int p, int beg, int end) -> int",
" {",
" if (!p || beg > r)",
" return INVALID;",
" if (end - 1 <= r)",
" {",
" S ans = d[p];",
" if (f(op(ans, now)))",
" {",
" now = op(ans, now);",
" return INVALID;",
" }",
" if (beg + 1 == end)",
" return beg;",
" }",
" int mid = (beg + end) / 2;",
" int pos = self(self, rch(p), mid, end);",
" return pos == INVALID ? self(self, lch(p), beg, mid) : pos;",
" };",
"",
" return _min_right(_min_right, root, beg, end);",
" }",
"",
"private:",
" const int beg, end;",
" int root = 1;",
" int idx = 2;",
" vector<S> d;",
" vector<pair<int, int>> ch;",
"",
" int &lch(int k) { return ch[k].first; }",
" int &rch(int k) { return ch[k].second; }",
"",
" void push_up(int k) { d[k] = op(d[lch(k)], d[rch(k)]); }",
"",
" S _get(int p, int beg, int end, int pos)",
" {",
" if (!p)",
" return e();",
" if (beg + 1 == end)",
" return d[p];",
" int mid = (beg + end) / 2;",
" return pos < mid ? _get(lch(p), beg, mid, pos) : _get(rch(p), mid, end, pos);",
" }",
"",
" S _prod(int p, int beg, int end, int l, int r)",
" {",
" if (!p || beg > r || end < l)",
" return e();",
" if (beg >= l && end <= r)",
" return d[p];",
" int mid = (beg + end) / 2;",
" S ansl = _prod(lch(p), beg, mid, l, r);",
" S ansr = _prod(rch(p), mid, end, l, r);",
" return op(ansl, ansr);",
" }",
"",
" void _add(int &p, int beg, int end, int pos, S k)",
" {",
" if (!p)",
" p = idx++;",
" if (beg + 1 == end)",
" {",
" m(d[p], k);",
" return;",
" }",
" int mid = (beg + end) / 2;",
" if (pos < mid)",
" _add(lch(p), beg, mid, pos, k);",
" else",
" _add(rch(p), mid, end, pos, k);",
" push_up(p);",
" }",
"};"
],
"description": "线段树(动态开点))"
},
"线段树(区间修改)": {
"prefix": "tplazysegtree",
"body": [
"#include <bit>",
"template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()>",
"struct LazySegTree",
"{",
"public:",
" LazySegTree() : LazySegTree(0) {}",
" explicit LazySegTree(int n) : LazySegTree(vector<S>(n, e())) {}",
" explicit LazySegTree(const vector<S> &v) : n(int(v.size()))",
" {",
" size = bit_ceil((unsigned int)(n));",
" log = countr_zero((unsigned int)size);",
" d = vector<S>(2 * size, e());",
" lz = vector<F>(size, id());",
" for (int i = 0; i < n; i++)",
" d[size + i] = v[i];",
" for (int i = size - 1; i >= 1; i--)",
" push_up(i);",
" }",
"",
" void set(int p, S x)",
" {",
" p += size;",
" for (int i = log; i >= 1; i--)",
" push_down(p >> i);",
" d[p] = x;",
" for (int i = 1; i <= log; i++)",
" push_up(p >> i);",
" }",
"",
" S get(int p)",
" {",
" p += size;",
" for (int i = log; i >= 1; i--)",
" push_down(p >> i);",
" return d[p];",
" }",
"",
" S prod(int l, int r)",
" {",
" if (l == r)",
" return e();",
"",
" l += size;",
" r += size;",
"",
" for (int i = log; i >= 1; i--)",
" {",
" if (((l >> i) << i) != l)",
" push_down(l >> i);",
" if (((r >> i) << i) != r)",
" push_down((r - 1) >> i);",
" }",
"",
" S ansl = e(), ansr = e();",
" for (; l < r; l >>= 1, r >>= 1)",
" {",
" if (l & 1)",
" ansl = op(ansl, d[l++]);",
" if (r & 1)",
" ansr = op(d[--r], ansr);",
" }",
"",
" return op(ansl, ansr);",
" }",
"",
" S all_prod() { return d[1]; }",
"",
" void apply(int p, F f)",
" {",
" p += size;",
" for (int i = log; i >= 1; i--)",
" push_down(p >> i);",
" d[p] = mapping(f, d[p]);",
" for (int i = 1; i <= log; i++)",
" push_up(p >> i);",
" }",
"",
" void apply(int l, int r, F f)",
" {",
" if (l == r)",
" return;",
"",
" l += size;",
" r += size;",
"",
" for (int i = log; i >= 1; i--)",
" {",
" if (((l >> i) << i) != l)",
" push_down(l >> i);",
" if (((r >> i) << i) != r)",
" push_down((r - 1) >> i);",
" }",
"",
" for (int x = l, y = r; x < y; x >>= 1, y >>= 1)",
" {",
" if (x & 1)",
" all_apply(x++, f);",
" if (y & 1)",
" all_apply(--y, f);",
" }",
"",
" for (int i = 1; i <= log; i++)",
" {",
" if (((l >> i) << i) != l)",
" push_up(l >> i);",
" if (((r >> i) << i) != r)",
" push_up((r - 1) >> i);",
" }",
" }",
"",
"private:",
" int n, size, log;",
" vector<S> d;",
" vector<F> lz;",
"",
" void all_apply(int k, F f)",
" {",
" d[k] = mapping(f, d[k]);",
" if (k < size)",
" lz[k] = composition(f, lz[k]);",
" }",
"",
" void push_up(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }",
"",
" void push_down(int k)",
" {",
" all_apply(2 * k, lz[k]);",
" all_apply(2 * k + 1, lz[k]);",
" lz[k] = id();",
" }",
"};"
],
"description": "线段树(区间修改)"
},
"Treap普通平衡树": {
"prefix": "tptreap",
"body": [
"template <typename K>",
"class TreapMultiSet",
"{",
"public:",
" explicit TreapMultiSet(int q) : key(q + 1), pri(q + 1), size(q + 1), cnt(q + 1), lch(q + 1), rch(q + 1) {}",
"",
" void insert(K k)",
" {",
" auto [x, temp] = split_by_key(root, k - 1);",
" auto [y, z] = split_by_key(temp, k);",
" if (y)",
" inc(y);",
" else",
" y = new_node(k);",
" root = merge(merge(x, y), z);",
" }",
"",
" void erase(K k)",
" {",
" auto [x, temp] = split_by_key(root, k - 1);",
" auto [y, z] = split_by_key(temp, k);",
" dec(y);",
" if (cnt[y] == 0)",
" y = 0;",
" root = merge(merge(x, y), z);",
" }",
"",
" int rank(K val)",
" {",
" auto [x, y] = split_by_key(root, val - 1);",
" int ans = size[x] + 1;",
" root = merge(x, y);",
" return ans;",
" }",
"",
" K kth_element(int k)",
" {",
" auto [x, y] = split_by_rank(root, k);",
" int ans = max_son(x);",
" root = merge(x, y);",
" return ans;",
" }",
"",
" K prev_element(K val)",
" {",
" auto [x, y] = split_by_key(root, val - 1);",
" K ans = max_son(x);",
" root = merge(x, y);",
" return ans;",
" }",
"",
" K next_element(K val)",
" {",
" auto [x, y] = split_by_key(root, val);",
" K ans = min_son(y);",
" root = merge(x, y);",
" return ans;",
" }",
"",
" vector<K> debug() const",
" {",
" vector<K> ans;",
" auto mid_order = [&](auto &self, int p) -> void",
" {",
" if (!p)",
" return;",
" self(self, lch[p]);",
" for (int i = 0; i < cnt[p]; i++)",
" ans.push_back(key[p]);",
" self(self, rch[p]);",
" };",
" mid_order(mid_order, root);",
" return ans;",
" }",
"",
"private:",
" vector<K> key;",
" vector<int> pri, size, cnt, lch, rch;",
" int root = 0;",
" int idx = 1;",
"",
" int new_node(K k)",
" {",
" key[idx] = k;",
" pri[idx] = gen_priority();",
" size[idx] = cnt[idx] = 1;",
" lch[idx] = rch[idx] = 0;",
" return idx++;",
" }",
"",
" static int gen_priority()",
" {",
" static mt19937 gen(random_device{}());",
" static uniform_int_distribution<> dis;",
" return dis(gen);",
" }",
"",
" void push_up(int p) { size[p] = cnt[p] + size[lch[p]] + size[rch[p]]; }",
" void inc(int p) { size[p]++, cnt[p]++; }",
" void dec(int p) { size[p]--, cnt[p]--; }",
"",
" int max_son(int p) const",
" {",
" while (rch[p])",
" p = rch[p];",
" return key[p];",
" }",
"",
" int min_son(int p) const",
" {",
" while (lch[p])",
" p = lch[p];",
" return key[p];",
" }",
"",
" // 返回的左子树小于等于 k",
" pair<int, int> split_by_key(int p, K k)",
" {",
" if (!p)",
" return {0, 0};",
" if (key[p] < k)",
" {",
" auto [x, y] = split_by_key(rch[p], k);",
" rch[p] = x;",
" push_up(p);",
" return {p, y};",
" }",
" else if (k < key[p])",
" {",
" auto [x, y] = split_by_key(lch[p], k);",
" lch[p] = y;",
" push_up(p);",
" return {x, p};",
" }",
" else",
" {",
" int y = rch[p];",
" rch[p] = 0;",
" push_up(p);",
" return {p, y};",
" }",
" }",
"",
" // 返回的左子树至少有 k 个元素",
" pair<int, int> split_by_rank(int p, int k)",
" {",
" if (!p)",
" return {0, 0};",
" int lch_size = size[lch[p]];",
" int mid_cnt = cnt[p];",
" if (lch_size + mid_cnt < k)",
" {",
" auto [x, y] = split_by_rank(rch[p], k - lch_size - mid_cnt);",
" rch[p] = x;",
" push_up(p);",
" return {p, y};",
" }",
" else if (lch_size >= k)",
" {",
" auto [x, y] = split_by_rank(lch[p], k);",
" lch[p] = y;",
" push_up(p);",
" return {x, p};",
" }",
" else",
" {",
" int y = rch[p];",
" rch[p] = 0;",
" push_up(p);",
" return {p, y};",
" }",
" }",
"",
" int merge(int x, int y)",
" {",
" if (!x || !y)",
" return x + y;",
" if (pri[x] < pri[y])",
" {",
" rch[x] = merge(rch[x], y);",
" push_up(x);",
" return x;",
" }",
" else",
" {",
" lch[y] = merge(x, lch[y]);",
" push_up(y);",
" return y;",
" }",
" }",
"};"
],
"description": "Treap普通平衡树"
},
"Treap文艺平衡树(区间反转)": {
"prefix": "tptreap",
"body": [
"template <typename K>",
"class LazyRangeTreap",
"{",
"public:",
" explicit LazyRangeTreap(const vector<K> &a) : n(a.size()), key(n + 1), pri(n + 1), size(n + 1), lch(n + 1), rch(n + 1), lazy(n + 1)",
" {",
" stack<int> st;",
" for (auto i : a)",
" {",
" int x = new_node(i);",
" while (!st.empty() && pri[st.top()] >= pri[x])",
" {",
" push_up(st.top());",
" st.pop();",
" }",
" if (st.empty())",
" {",
" lch[x] = root;",
" root = x;",
" }",
" else",
" {",
" int f = st.top();",
" lch[x] = rch[f];",
" rch[f] = x;",
" }",
" st.push(x);",
" }",
" while (!st.empty())",
" {",
" push_up(st.top());",
" st.pop();",
" }",
" }",
"",
" void reverse(int l, int r)",
" {",
" auto [x, temp] = split_by_rank(root, l);",
" auto [y, z] = split_by_rank(temp, r - l);",
" all_apply(y);",
" root = merge(merge(x, y), z);",
" }",
"",
" vector<K> debug()",
" {",
" vector<K> ans;",
" auto mid_order = [&](auto &self, int p) -> void",
" {",
" if (!p)",
" return;",
" push_down(p);",
" self(self, lch[p]);",
" ans.push_back(key[p]);",
" self(self, rch[p]);",
" };",
" mid_order(mid_order, root);",
" return ans;",
" }",
"",
"private:",
" int n;",
" vector<K> key;",
" vector<int> pri, size, lch, rch;",
" vector<bool> lazy;",
" int root = 0;",
"",
" int new_node(K k)",
" {",
" static int idx = 1;",
" key[idx] = k;",
" pri[idx] = gen_priority();",
" size[idx] = 1;",
" lch[idx] = rch[idx] = 0;",
" return idx++;",
" }",
"",
" static int gen_priority()",
" {",
" static mt19937 gen(random_device{}());",
" static uniform_int_distribution<> dis;",
" return dis(gen);",
" }",
"",
" void push_up(int p) { size[p] = 1 + size[lch[p]] + size[rch[p]]; }",
"",
" void push_down(int p)",
" {",
" if (!lazy[p])",
" return;",
" all_apply(lch[p]);",
" all_apply(rch[p]);",
" lazy[p] = false;",
" }",
"",
" void all_apply(int p)",
" {",
" swap(lch[p], rch[p]);",
" lazy[p] = !lazy[p];",
" }",
"",
" // 返回的左子树至少有 k 个元素",
" pair<int, int> split_by_rank(int p, int k)",
" {",
" if (!p)",
" return {0, 0};",
" push_down(p);",
" int lch_size = size[lch[p]];",
" int mid_cnt = 1;",
" if (lch_size + mid_cnt < k)",
" {",
" auto [x, y] = split_by_rank(rch[p], k - lch_size - mid_cnt);",
" rch[p] = x;",
" push_up(p);",
" return {p, y};",
" }",
" else if (lch_size >= k)",
" {",
" auto [x, y] = split_by_rank(lch[p], k);",
" lch[p] = y;",
" push_up(p);",
" return {x, p};",
" }",
" else",
" {",
" int y = rch[p];",
" rch[p] = 0;",
" push_up(p);",
" return {p, y};",
" }",
" }",
"",
" int merge(int x, int y)",
" {",
" if (!x || !y)",
" return x + y;",
" if (pri[x] < pri[y])",
" {",
" push_down(x);",
" rch[x] = merge(rch[x], y);",
" push_up(x);",
" return x;",
" }",
" else",
" {",
" push_down(y);",
" lch[y] = merge(x, lch[y]);",
" push_up(y);",
" return y;",
" }",
" }",
"};"
],
"description": "Treap文艺平衡树(区间反转)"
},
"字典树": {
"prefix": "tptrie",
"body": [
"template <int m, auto get_id>",
"class Trie",
"{",
"public:",
" explicit Trie(int n) : ne(n, array<int, m>{}) {}",
"",
" int insert(const string &s) { return insert_path(s).back(); }",
"",
" vector<int> insert_path(const string &s)",
" {",
" int p = 0;",
" vector<int> path;",
" path.reserve(s.size());",
" for (auto ch : s)",
" {",
" p = at_or_new(p, ch);",
" path.push_back(p);",
" }",
" return path;",
" }",
"",
" int find(const string &s) const { return find_path(s).back(); }",
"",
" vector<int> find_path(const string &s) const",
" {",
" int p = 0;",
" vector<int> path;",
" path.reserve(s.size());",
" for (auto ch : s)",
" {",
" p = at(p, ch);",
" path.push_back(p);",
" if (!p)",
" break;",
" }",
" return path;",
" }",
"",
"private:",
" vector<array<int, m>> ne;",
" int idx = 1;",
"",
" int at_or_new(int p, char ch)",
" {",
" int &q = ne[p][get_id(ch)];",
" if (q == 0)",
" q = idx++;",
" return q;",
" }",
"",
" int at(int p, char ch) const { return ne[p][get_id(ch)]; }",
"};"
],
"description": "字典树"
},
"AC自动机": {
"prefix": "tpac",
"body": [
"template <int m, auto get_id>",
"class AC",
"{",
"public:",
" explicit AC(int n_) : n(n_), ne(n_, array<int, m>{}) {}",
"",
" int insert(const string &s) { return insert_path(s).back(); }",
"",
" vector<int> insert_path(const string &s)",
" {",
" int p = 0;",
" vector<int> path;",
" path.reserve(s.size());",
" for (auto ch : s)",
" {",
" p = at_or_new(p, ch);",
" path.push_back(p);",
" }",
" return path;",
" }",
"",
" vector<vector<int>> build()",
" {",
" vector<vector<int>> edge(n);",
" vector<int> fail(n);",
" queue<int> q;",
" for (auto v : ne[0])",
" if (v)",
" {",
" q.push(v);",
" edge[0].push_back(v);",
" }",
" while (!q.empty())",
" {",
" int u = q.front();",
" int f = fail[u];",
" q.pop();",
" for (int i = 0; i < m; i++)",
" {",
" int &v = ne[u][i];",
" if (v)",
" {",
" fail[v] = ne[f][i];",
" q.push(v);",
" edge[fail[v]].push_back(v);",
" }",
" else",
" v = ne[f][i];",
" }",
" }",
" return edge;",
" }",
"",
" vector<int> get_path(const string &s) const",
" {",
" int p = 0;",
" vector<int> path;",
" path.reserve(s.size());",
" for (auto ch : s)",
" {",
" p = at(p, ch);",
" path.push_back(p);",
" }",
" return path;",
" }",
"",
"private:",
" int n, idx = 1;",
" vector<array<int, m>> ne;",
"",
" int at_or_new(int p, char ch)",
" {",
" int &q = ne[p][get_id(ch)];",
" if (q == 0)",
" q = idx++;",
" return q;",
" }",
"",
" int at(int p, char ch) const { return ne[p][get_id(ch)]; }",
"};"
],
"description": "AC自动机"
},
"无权图": {
"prefix": "tpgraph",
"body": [
"struct Graph",
"{",
" int n;",
" vector<vector<int>> edge;",
"",
" Graph(int n) : n(n), edge(n) {}",
"",
" void add(int u, int v) { edge[u].push_back(v); }",
"};"
],
"description": "无权图"
},
"有权图": {
"prefix": "tpgraph",
"body": [
"struct Graph",
"{",
" struct Edge",
" {",
" int to, cost;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
"",
" Graph(int n) : n(n), edge(n) {}",
"",
" void add(int u, int v, int w) { edge[u].push_back({v, w}); }",
"};"
],
"description": "有权图"
},
"Dijkstra最短路": {
"prefix": "tpdijkstra",
"body": [
"template <typename T>",
"struct Graph",
"{",
" struct Edge",
" {",
" int to, cost;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
"",
" Graph(int n) : n(n), edge(n) {}",
"",
" void add_edge(int u, int v, int w) { edge[u].push_back({v, w}); }",
"",
" vector<T> dijkstra(int s) const",
" {",
" struct Node",
" {",
" int u;",
" T d;",
" bool operator>(const Node &other) const { return d > other.d; }",
" };",
"",
" vector<T> dis(n, numeric_limits<T>::max());",
" dis[s] = 0;",
" priority_queue<Node, vector<Node>, greater<Node>> heap;",
" heap.push({s, 0});",
" while (!heap.empty())",
" {",
" auto [u, d] = heap.top();",
" heap.pop();",
" if (d > dis[u])",
" continue;",
" for (auto [v, w] : edge[u])",
" {",
" if (d + w < dis[v])",
" {",
" dis[v] = d + w;",
" heap.push({v, dis[v]});",
" }",
" }",
" }",
" return dis;",
" }",
"};"
],
"description": "Dijkstra最短路"
},
"网络最大流": {
"prefix": "tpdininc",
"body": [
"template <class Cap>",
"struct Network",
"{",
" struct Edge",
" {",
" int to;",
" Cap flow;",
" int rev_idx;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
"",
" Network(int n) : n(n), edge(n) {}",
"",
" void add_edge(int u, int v, Cap w)",
" {",
" int ui = edge[u].size();",
" int vi = edge[v].size();",
" edge[u].push_back({v, w, vi});",
" edge[v].push_back({u, 0, ui});",
" }",
"",
" Cap dinic(int s, int t)",
" {",
" vector<int> dep(n);",
" vector<size_t> cur(n);",
"",
" auto bfs = [&]() -> bool",
" {",
" dep.assign(n, -1);",
" cur.assign(n, 0);",
" dep[s] = 0;",
" queue<int> q;",
" q.push(s);",
" while (!q.empty())",
" {",
" int u = q.front();",
" q.pop();",
" int d = dep[u];",
" for (auto e : edge[u])",
" {",
" int v = e.to;",
" if (e.flow && dep[v] == -1)",
" {",
" dep[v] = d + 1;",
" q.push(v);",
" }",
" }",
" }",
" return dep[t] != -1;",
" };",
"",
" auto dfs = [&](auto &self, int u, Cap in) -> Cap",
" {",
" if (u == t)",
" return in;",
" Cap out = 0;",
" for (size_t &i = cur[u]; i < edge[u].size(); i++)",
" {",
" Edge &e = edge[u][i];",
" int v = e.to;",
" if (dep[v] == dep[u] + 1 && e.flow)",
" {",
" Edge &r = edge[v][e.rev_idx];",
" Cap res = self(self, v, min(in, e.flow));",
" e.flow -= res;",
" r.flow += res;",
" in -= res;",
" out += res;",
" if (!in)",
" break;",
" }",
" }",
" return out;",
" };",
"",
" Cap ans = 0;",
" while (bfs())",
" ans += dfs(dfs, s, numeric_limits<Cap>::max());",
" return ans;",
" }",
"};"
],
"description": "网络最大流"
},
"最小费用流": {
"prefix": "tpmcmf",
"body": [
"template <typename Cost = int>",
"class Network",
"{",
"public:",
" Network(int n) : n(n), edge(n), h(n, MAX_COST) {}",
"",
" void add_edge(int u, int v, int f, Cost c)",
" {",
" int ui = edge[u].size();",
" int vi = edge[v].size();",
" edge[u].push_back({v, f, c, vi});",
" edge[v].push_back({u, 0, -c, ui});",
" }",
"",
" // spfa",
" void init(int s)",
" {",
" h[s] = 0;",
" queue<int> q;",
" q.push(s);",
" while (!q.empty())",
" {",
" int u = q.front();",
" q.pop();",
" Cost d = h[u];",
" for (auto e : edge[u])",
" {",
" int v = e.to;",
" if (e.flow && d + e.cost < h[v])",
" {",
" h[v] = d + e.cost;",
" q.push(v);",
" }",
" }",
" }",
" }",
"",
" pair<Cost, int> slope(int s, int t)",
" {",
" vector<Cost> dis(n, MAX_COST);",
" vector<Edge *> from(n);",
"",
" auto dijkstra = [&]() -> bool",
" {",
" struct Node",
" {",
" int u;",
" Cost d;",
" bool operator>(const Node &other) const { return d > other.d; }",
" };",
"",
" dis.assign(n, MAX_COST);",
" dis[s] = 0;",
" priority_queue<Node, vector<Node>, greater<Node>> heap;",
" heap.push({s, 0});",
" while (!heap.empty())",
" {",
" auto [u, d] = heap.top();",
" heap.pop();",
" if (d > dis[u])",
" continue;",
" for (auto &e : edge[u])",
" {",
" int v = e.to;",
" Cost c = e.cost + h[u] - h[v];",
" if (e.flow && d + c < dis[v])",
" {",
" dis[v] = d + c;",
" heap.push({v, dis[v]});",
" from[v] = &e;",
" }",
" }",
" }",
" return dis[t] != MAX_COST;",
" };",
"",
" if (!dijkstra())",
" return {0, 0};",
"",
" Cost mincost = 0;",
" int maxflow = 0;",
" for (int u = 0; u < n; u++)",
" h[u] += dis[u];",
" int flow = numeric_limits<int>::max();",
" for (Edge *p = from[t]; p;)",
" {",
" flow = min(flow, p->flow);",
" int v = p->to, rev_idx = p->rev_idx;",
" Edge *r = &edge[v][rev_idx];",
" p = from[r->to];",
" }",
" for (Edge *p = from[t]; p;)",
" {",
" int v = p->to, rev_idx = p->rev_idx;",
" Edge *r = &edge[v][rev_idx];",
" p->flow -= flow;",
" r->flow += flow;",
" p = from[r->to];",
" }",
" mincost += h[t] * flow;",
" maxflow += flow;",
" return {mincost, maxflow};",
" }",
"",
" pair<Cost, int> mcmf(int s, int t)",
" {",
" init(s);",
" Cost mincost = 0;",
" int maxflow = 0;",
" while (true)",
" {",
" auto [cost, flow] = slope(s, t);",
" if (flow == 0)",
" break;",
" mincost += cost;",
" maxflow += flow;",
" }",
" return {mincost, maxflow};",
" }",
"",
"private:",
" const Cost MAX_COST = numeric_limits<Cost>::max();",
"",
" struct Edge",
" {",
" int to, flow;",
" Cost cost;",
" int rev_idx;",
" };",
"",
" int n;",
" vector<vector<Edge>> edge;",
" vector<Cost> h;",
"};"
],
"description": "最小费用流"
},
"莫队算法": {
"prefix": "tpmoalgo",
"body": [
"template <class G, class A, void (*op)(G &, int, bool), A (*answer)(const G &)>",
"class MoAlgo",
"{",
"public:",
" explicit MoAlgo(int n, G g, const vector<pair<int, int>> &intervals) : n(n), m(intervals.size()), g(g)",
" {",
" int sq = sqrt(n);",
" query.reserve(m);",
" for (int i = 0; i < m; i++)",
" {",
" auto [l, r] = intervals[i];",
" query.push_back({l, r, l / sq, i});",
" }",
" sort(query.begin(), query.end());",
" }",
"",
" vector<A> solve()",
" {",
" vector<A> ans(m);",
" int l = 0, r = 0;",
" for (auto &[ql, qr, _, id] : query)",
" {",
" while (l > ql)",
" op(g, --l, true);",
" while (r < qr)",
" op(g, r++, true);",
" while (l < ql)",
" op(g, l++, false);",
" while (r > qr)",
" op(g, --r, false);",
" ans[id] = answer(g);",
" }",
" return ans;",
" }",
"",
"private:",
" struct Query",
" {",
" int l, r, b, id;",
" bool operator<(const Query &other) const { return b != other.b ? b < other.b : (b & 1) ^ (r < other.r); }",
" };",
"",
" int n, m;",
" G g;",
" vector<Query> query;",
"};"
],
"description": "莫队算法"
},
"manacher算法": {
"prefix": "tpmanacher",
"body": [
"int manacher(const string &s, char ch)",
"{",
" int n = s.size();",
" int m = 2 * n + 1;",
" string t(m, ch);",
" for (int i = 0, j = 1; i < n; i++, j += 2)",
" t[j] = s[i];",
" vector<int> d(m);",
" int ans = 0;",
" for(int i = 0, l = 0, r = -1; i < m; i++)",
" {",
" int k = i > r ? 1 : min(d[l+r-i], r-i+1);",
" while(i-k >= 0 && i + k < m && t[i-k] == t[i+k])",
" k++;",
" d[i] = k;",
" ans = max(ans, 2 * k - 1);",
" if(i + k - 1 > r)",
" {",
" r = i + k - 1;",
" l = i - k + 1;",
" }",
" }",
" return ans / 2;",
"}"
],
"description": "manacher算法"
},
"KMP": {
"prefix": "tpkmp",
"body": [
"vector<int> get_next(const string &s)",
"{",
" int n = s.size();",
" vector<int> next(n);",
" for (int i = 1, j = 0; i < n; i++)",
" {",
" while (j && s[i] != s[j])",
" j = next[j - 1];",
" if (s[i] == s[j])",
" j++;",
" next[i] = j;",
" }",
" return next;",
"}",
""
],
"description": "KMP"
},
"modint": {
"prefix": "tpmint",
"body": [
"template <int m, bool isp = true>",
"class static_modint",
"{",
" using mint = static_modint;",
" using u32 = unsigned int;",
" using u64 = unsigned long long;",
" using i32 = int;",
" using i64 = long long;",
"",
"public:",
" static_modint() : _v(0) {}",
" static_modint(u32 v) : _v(v % umod()) {}",
" static_modint(u64 v) : _v(v % umod()) {}",
" static_modint(i32 v)",
" {",
" i32 x = (i32)(v % (i32)umod());",
" if (x < 0)",
" x += umod();",
" _v = (u32)x;",
" }",
" static_modint(i64 v)",
" {",
" i64 x = (i64)(v % (i64)umod());",
" if (x < 0)",
" x += umod();",
" _v = (u32)x;",
" }",
"",
" u32 val() const { return _v; }",
"",
" mint &operator++()",
" {",
" _v++;",
" if (_v == umod())",
" _v = 0;",
" return *this;",
" }",
" mint &operator--()",
" {",
" if (_v == 0)",
" _v = umod();",
" _v--;",
" return *this;",
" }",
" mint operator++(int)",
" {",
" mint result = *this;",
" ++*this;",
" return result;",
" }",
" mint operator--(int)",
" {",
" mint result = *this;",
" --*this;",
" return result;",
" }",
"",
" mint &operator+=(const mint &rhs)",
" {",
" _v += rhs._v;",
" if (_v >= umod())",
" _v -= umod();",
" return *this;",
" }",
" mint &operator-=(const mint &rhs)",
" {",
" _v -= rhs._v;",
" if (_v >= umod())",
" _v += umod();",
" return *this;",
" }",
" mint &operator*=(const mint &rhs)",
" {",
" u64 z = (u64)_v * (u64)rhs._v;",
" _v = (u32)(z % umod());",
" return *this;",
" }",
" mint &operator/=(const mint &rhs) { return *this = *this * rhs.inv(); }",
"",
" mint operator+() const { return *this; }",
" mint operator-() const { return mint(0) - *this; }",
"",
" mint pow(i64 n) const",
" {",
" mint x = *this, r = 1;",
" while (n)",
" {",
" if (n & 1)",
" r *= x;",
" x *= x;",
" n >>= 1;",
" }",
" return r;",
" }",
"",
" mint inv() const { return isp ? pow(umod() - 2) : inv_gcd(_v, m); }",
"",
" friend mint operator+(const mint &lhs, const mint &rhs) { return mint(lhs) += rhs; }",
" friend mint operator-(const mint &lhs, const mint &rhs) { return mint(lhs) -= rhs; }",
" friend mint operator*(const mint &lhs, const mint &rhs) { return mint(lhs) *= rhs; }",
" friend mint operator/(const mint &lhs, const mint &rhs) { return mint(lhs) /= rhs; }",
" friend bool operator==(const mint &lhs, const mint &rhs) { return lhs._v == rhs._v; }",
" friend bool operator!=(const mint &lhs, const mint &rhs) { return lhs._v != rhs._v; }",
"",
"private:",
" u32 _v;",
"",
" static constexpr unsigned int umod() { return m; }",
"",
" static mint inv_gcd(i64 a, i64 b)",
" {",
" auto exgcd = [](auto &&self, i64 a, i64 b) -> pair<i64, i64>",
" {",
" if (b == 0)",
" return {1, 0};",
" auto [x, y] = self(self, b, a % b);",
" return {y, x - a / b * y};",
" };",
"",
" auto [x, _] = exgcd(exgcd, a, b);",
" return mint(x);",
" }",
"};"
],
"description": "modint"
},
"布尔矩阵": {
"prefix": "tpmatrix",
"body": [
"const int N = $0;",
"using RowVec = bitset<N>;",
"",
"class Matrix",
"{",
"public:",
" RowVec &operator[](int i) { return a[i]; }",
" const RowVec &operator[](int i) const { return a[i]; }",
"",
" Matrix operator*(const Matrix &y) const;",
"",
"private:",
" array<RowVec, N> a;",
"};",
"",
"RowVec operator*(const RowVec &v, const Matrix &m)",
"{",
" RowVec res;",
" for (int j = 0; j < N; j++)",
" if (v[j])",
" res |= m[j];",
" return res;",
"}",
"",
"Matrix Matrix::operator*(const Matrix &y) const",
"{",
" Matrix res;",
" for (int i = 0; i < N; i++)",
" res[i] = a[i] * y;",
" return res;",
"}",
"",
"Matrix qpow(Matrix a, LL b)",
"{",
" Matrix res;",
" for (int i = 0; i < N; i++)",
" res[i][i] = 1;",
" while (b)",
" {",
" if (b & 1)",
" res = res * a;",
" b >>= 1;",
" a = a * a;",
" }",
" return res;",
"}"
],
"description": "布尔矩阵"
},
}
对拍程序¶
testlib/testlib.h at master · MikeMirzayanov/testlib
duipai.cpp¶
#include <cstdio>
#include <cstdlib>
using namespace std;
int main()
{
system("clang++ ac.cpp -o ac.out -W -Wall -O2 -std=c++20 -stdlib=libc++ -I/root/cpp/lib");
system("clang++ wa.cpp -o wa.out -W -Wall -O2 -std=c++20 -stdlib=libc++ -I/root/cpp/lib");
system("clang++ data.cpp -o data.out -W -Wall -O2 -std=c++20 -stdlib=libc++");
char data_gen_cmd[64];
int seed = 0;
while(1)
{
sprintf(data_gen_cmd, "./data.out %d > ./in.txt 897", seed);
printf("%d...\n", seed++);
system(data_gen_cmd);
system("./ac.out < ./in.txt > ./ac.txt");
system("./wa.out < ./in.txt > ./wa.txt");
if (system("diff ./ac.txt ./wa.txt"))
{
system("cat ./in.txt");
break;
}
}
return 0;
}
data.cpp¶
#include "testlib.h"
#include <cstdio>
#include <iostream>
using namespace std;
using LL = long long;
int main(int argc, char **argv)
{
registerGen(argc, argv, 1);
FILE *fp = freopen("in.txt", "w", stdout);
LL n = rnd.next(1ll, (LL)1E15);
int m = rnd.next(1, (int)2E5);
cout << n << ' ' << m << '\n';
while (m--)
{
int a = rnd.next(2, 300);
int b = rnd.next(1, a - 1);
cout << a << ' ' << b << '\n';
}
// println(rnd.next(1, 10)); /* Random number in the range [1,10]. */
// println(rnd.next("[a-zA-Z0-9]{1,1000}")); /* Random word of length [1,1000]. */
fclose(fp);
return 0;
}
最后更新:
2025-07-30
创建日期: 2024-12-30
创建日期: 2024-12-30