快速 IO 操作
quick_io.hpp：
#include <cstdio>
#include <cstring>
template <const size_t _Size = 16>
class quick_io {
private:
char buf_in[1 << _Size], buf_out[1 << _Size];
size_t index_in, index_out;
FILE *in, *out;
public:
inline void flush_in() {
fread(buf_in, sizeof(char), 1 << _Size, in), index_in = 0;
}
inline void flush_out() {
fwrite(buf_out, index_out, 1, out), index_out = 0;
}
inline quick_io& operator>>(char& ch) {
if (index_in == (1 << _Size)) flush_in();
ch = buf_in[index_in++];
return *this;
}
inline quick_io& operator>>(char* str) {
size_t origin = strlen(str);
char ch = 0;
size_t len = 0;
do {
*this >> ch;
if (!isgraph(ch)) break;
str[len++] = ch;
} while (true);
if (len < origin)
while (len < origin) str[len++] = 0;
return *this;
}
template <typename T>
inline quick_io& operator>>(T& value) {
value = 0;
short sign = 1;
char ch = 0;
do sign = ch == '-' ? -1 : sign, *this >> ch;
while (ch < '0' || ch > '9');
do value = (value << 3) + (value << 1) + ch - '0', *this >> ch;
while ('0' <= ch && ch <= '9');
value *= sign;
return *this;
}
inline quick_io& operator<<(const char ch) {
if (index_out == (1 << _Size)) flush_out();
buf_out[index_out++] = ch;
return *this;
}
inline quick_io& operator<<(const char* str) {
size_t len = strlen(str);
for (size_t i = 0; i < len; ++i) *this << str[i];
return *this;
}
inline quick_io& operator<<(char* str) {
size_t len = strlen(str);
for (size_t i = 0; i < len; ++i) *this << str[i];
return *this;
}
template <typename T>
inline quick_io& operator<<(T value) {
if (value < 0) *this << '-', value = -value;
static size_t stack[50], dep = 0;
do stack[++dep] = value % 10, value /= 10;
while (value);
do *this << (char)(stack[dep--] + '0');
while (dep);
return *this;
}
quick_io(FILE* in = stdin, FILE* out = stdout)
: index_in(0), index_out(0), in(in), out(out) {}
~quick_io() { flush_out(); }
};
example
#include "quick_io.hpp>"
quick_io<16> io;
int main() {
int a, b;
io >> a >> b << a + b << '\n';
return 0;
}
线段树
传递函数指针的版本（Before C++ 20）
lazysegtree.hpp
#include <vector>
template <typename index_T, typename value_t, value_t (*opt)(value_t, value_t),
value_t (*e_val)(), typename tag_T,
value_t (*apply)(value_t, tag_T, index_T),
tag_T (*attach)(tag_T, tag_T), tag_T (*e_tag)()>
class LazySegmentTree {
private:
index_T n;
std::vector<value_t> val;
std::vector<tag_T> tag;
mutable std::vector<std::pair<index_T, index_T>> child;
index_T root;
const index_T no_child = 0;
inline void new_node(index_T& index) {
index = val.size();
val.push_back(e_val());
tag.push_back(e_tag());
child.push_back(std::make_pair(no_child, no_child));
}
inline void push_up(const index_T index) {
val[index] = opt(val[child[index].first], val[child[index].second]);
}
inline void push_down(const index_T index, const index_T size) {
if (child[index].first == no_child) new_node(child[index].first);
if (child[index].second == no_child) new_node(child[index].second);
val[child[index].first] =
apply(val[child[index].first], tag[index], size / 2);
val[child[index].second] =
apply(val[child[index].second], tag[index], size - size / 2);
tag[child[index].first] = attach(tag[child[index].first], tag[index]);
tag[child[index].second] = attach(tag[child[index].second], tag[index]);
tag[index] = e_tag();
}
void set(const index_T _l, const index_T _r, const tag_T _tag,
const index_T l, const index_T r, const index_T index) {
if (_l >= r || _r <= l) return;
if (_l <= l && r <= _r) {
val[index] = apply(val[index], _tag, r - l);
tag[index] = attach(tag[index], _tag);
return;
}
push_down(index, r - l);
index_T mid = (l + r) >> 1;
if (_l < mid) set(_l, _r, _tag, l, mid, child[index].first);
if (_r >= mid) set(_l, _r, _tag, mid, r, child[index].second);
push_up(index);
}
value_t get(const index_T _l, const index_T _r, const index_T l,
const index_T r, const index_T index) {
if (_l >= r || _r <= l) return e_val();
if (_l <= l && r <= _r) return val[index];
push_down(index, r - l);
index_T mid = (l + r) >> 1;
if (_l >= mid) return get(_l, _r, mid, r, child[index].second);
if (_r < mid) return get(_l, _r, l, mid, child[index].first);
return opt(get(_l, _r, l, mid, child[index].first),
get(_l, _r, mid, r, child[index].second));
}
public:
inline void set(const index_T _l, const index_T _r, const tag_T _tag) {
set(_l, _r, _tag, 0, n, 0);
}
inline void set(const index_T _pos, const tag_T _tag) {
set(_pos, _pos + 1, _tag, 0, n, 0);
}
inline value_t get(const index_T _l, const index_T _r) {
return get(_l, _r, 0, n, 0);
}
inline value_t get(const index_T _pos) {
return get(_pos, _pos + 1, 0, n, 0);
}
inline value_t get() { return val.front(); }
LazySegmentTree(index_T n) : n(n) { new_node(root); }
};
example
P3372 Submission Record
#include <iostream>
#include "lazysegtree.hpp"
using i64 = long long;
i64 opt(i64 x, i64 y) { return x + y; }
i64 apply(i64 x, i64 y, int size) { return x + y * size; }
i64 attach(i64 x, i64 y) { return x + y; }
i64 e_val() { return 0ll; }
i64 e_tag() { return 0ll; }
int main() {
int n, m;
std::cin >> n >> m;
LazySegmentTree<int, i64, opt, e_val, i64, apply, attach, e_tag> T(n);
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
T.set(i, x);
}
for (int i = 0; i < m; ++i) {
int opt, l, r;
std::cin >> opt >> l >> r, --l;
if (opt == 1) {
i64 k;
std::cin >> k;
T.set(l, r, k);
} else {
std::cout << T.get(l, r) << '\n';
}
}
return 0;
}
传递 lambda 表达式的版本（C++ 20）
lazysegtree_lambda.hpp
#include <vector>
template <typename index_T, typename value_t, typename tag_T, auto merge,
auto apply, auto attach, auto e_val, auto e_tag>
class LazySegmentTree {
private:
index_T n;
std::vector<value_t> val;
std::vector<tag_T> tag;
mutable std::vector<std::pair<index_T, index_T>> child;
index_T root;
const index_T no_child = 0;
inline void new_node(index_T& index) {
index = val.size();
val.push_back(e_val());
tag.push_back(e_tag());
child.push_back(std::make_pair(no_child, no_child));
}
inline void push_up(const index_T index) {
val[index] = merge(val[child[index].first], val[child[index].second]);
}
inline void push_down(const index_T index, const index_T size) {
if (child[index].first == no_child) new_node(child[index].first);
if (child[index].second == no_child) new_node(child[index].second);
val[child[index].first] =
apply(val[child[index].first], tag[index], size / 2);
val[child[index].second] =
apply(val[child[index].second], tag[index], size - size / 2);
tag[child[index].first] = attach(tag[child[index].first], tag[index]);
tag[child[index].second] = attach(tag[child[index].second], tag[index]);
tag[index] = e_tag();
}
void set(const index_T _l, const index_T _r, const tag_T _tag,
const index_T l, const index_T r, const index_T index) {
if (_l >= r || _r <= l) return;
if (_l <= l && r <= _r) {
val[index] = apply(val[index], _tag, r - l);
tag[index] = attach(tag[index], _tag);
return;
}
push_down(index, r - l);
index_T mid = (l + r) >> 1;
if (_l < mid) set(_l, _r, _tag, l, mid, child[index].first);
if (_r >= mid) set(_l, _r, _tag, mid, r, child[index].second);
push_up(index);
}
value_t get(const index_T _l, const index_T _r, const index_T l,
const index_T r, const index_T index) {
if (_l >= r || _r <= l) return e_val();
if (_l <= l && r <= _r) return val[index];
push_down(index, r - l);
index_T mid = (l + r) >> 1;
if (_l >= mid) return get(_l, _r, mid, r, child[index].second);
if (_r < mid) return get(_l, _r, l, mid, child[index].first);
return merge(get(_l, _r, l, mid, child[index].first),
get(_l, _r, mid, r, child[index].second));
}
public:
inline void set(const index_T _l, const index_T _r, const tag_T _tag) {
set(_l, _r, _tag, 0, n, 0);
}
inline void set(const index_T _pos, const tag_T _tag) {
set(_pos, _pos + 1, _tag, 0, n, 0);
}
inline value_t get(const index_T _l, const index_T _r) {
return get(_l, _r, 0, n, 0);
}
inline value_t get(const index_T _pos) {
return get(_pos, _pos + 1, 0, n, 0);
}
inline value_t get() { return val.front(); }
LazySegmentTree(index_T n) : n(n) { new_node(root); }
};
example
P3372 Submission Record
#include "lazysegtree_lambda.hpp"
using i64 = long long;
int main() {
int n, m;
std::cin >> n >> m;
LazySegmentTree<int, i64, i64, [](i64 a, i64 b) { return a + b; },
[](i64 a, i64 b, int size) { return a + b * size; },
[](i64 a, i64 b) { return a + b; }, []() { return 0ll; },
[]() { return 0ll; }>
T(n);
for (int i = 0; i < n; ++i) {
i64 x;
std::cin >> x;
T.set(i, x);
}
for (int i = 0; i < m; ++i) {
int opt;
std::cin >> opt;
if (opt == 1) {
int x, y, k;
std::cin >> x >> y >> k;
--x;
T.set(x, y, k);
} else {
int x, y;
std::cin >> x >> y;
--x;
std::cout << T.get(x, y) << '\n';
}
}
}
P2572 Submission Record
#include "lazysegtree_lambda.hpp"
struct Value {
std::array<int, 2> num, pre, suf, bet;
Value(std::array<int, 2> num = {0, 0}, std::array<int, 2> pre = {0, 0},
std::array<int, 2> suf = {0, 0}, std::array<int, 2> bet = {0, 0})
: num(num), pre(pre), suf(suf), bet(bet) {}
};
#include <iostream>
int main() {
int n, m;
std::cin >> n >> m;
LazySegmentTree<
int, Value, short,
[](Value ls, Value rs) {
return Value(
{ls.num[0] + rs.num[0], ls.num[1] + rs.num[1]},
{ls.pre[0] + (ls.num[1] == 0 ? rs.pre[0] : 0),
ls.pre[1] + (ls.num[0] == 0 ? rs.pre[1] : 0)},
{rs.suf[0] + (rs.num[1] == 0 ? ls.suf[0] : 0),
rs.suf[1] + (rs.num[0] == 0 ? ls.suf[1] : 0)},
{std::max({ls.bet[0], rs.bet[0], ls.suf[0] + rs.pre[0]}),
std::max({ls.bet[1], rs.bet[1], ls.suf[1] + rs.pre[1]})});
},
[](Value x, short y, int size) {
if (y == -1) return x;
if (y == 0)
return Value({size, 0}, {size, 0}, {size, 0}, {size, 0});
if (y == 1)
return Value({0, size}, {0, size}, {0, size}, {0, size});
std::swap(x.num[0], x.num[1]);
std::swap(x.pre[0], x.pre[1]);
std::swap(x.suf[0], x.suf[1]);
std::swap(x.bet[0], x.bet[1]);
return x;
},
[](short tag_old, short tag_new) {
if (tag_new == -1) return tag_old;
if (tag_new == 0) return (short)0;
if (tag_new == 1) return (short)1;
if (tag_old == 0 || tag_old == 1) return (short)(tag_old ^ 1);
return tag_old == 2 ? (short)(-1) : (short)2;
},
[]() { return Value(); }, []() { return (short)-1; }>
T(n);
for (int i = 0; i < n; ++i) {
int x;
std::cin >> x;
T.set(i, (short)x);
}
for (int i = 0; i < m; ++i) {
int opt, l, r;
std::cin >> opt >> l >> r;
++r;
if (opt == 0) {
T.set(l, r, 0);
} else if (opt == 1) {
T.set(l, r, 1);
} else if (opt == 2) {
T.set(l, r, 2);
} else if (opt == 3) {
std::cout << T.get(l, r).num[1] << '\n';
} else if (opt == 4) {
std::cout << T.get(l, r).bet[1] << '\n';
} else {
exit(1);
}
}
return 0;
}
Dinic 网络流
networkflow.hpp
#include <queue>
#include <vector>
struct Edge {
int to, nxt;
Edge(const int to = 0, const int nxt = -1) : to(to), nxt(nxt) {}
};
template <typename T>
struct Flow : public Edge {
T capicity, flow;
Flow(const int to = 0, const int nxt = -1, const T capicity = 0, const T flow = 0)
: Edge(to, nxt), capicity(capicity), flow(flow) {}
};
class Graph {
public:
int n, m;
std::vector<int> head;
int cnt;
Graph(int n, int m) : n(n), m(m), head(n, -1), cnt(-1) {}
};
template <typename T>
class NetworkFlow : public Graph {
public:
int s, t;
T inf;
std::vector<int> dep, cur;
std::vector<Flow<T>> ed;
inline void add_edge(const int from = 0, const int to = 0, const T capicity = 0, const T flow = 0) {
ed[++cnt].to = to, ed[cnt].nxt = head[from], head[from] = cnt, ed[cnt].capicity = capicity,
ed[cnt].flow = flow;
}
NetworkFlow(int n, int m, int s, int t, T inf)
: Graph(n, m), s(s), t(t), inf(inf), dep(n), cur(n, -1), ed(m) {}
private:
auto bfs(int s, int t) {
std::queue<int> q;
while (q.size()) q.pop();
dep.assign(n, 0);
dep[s] = 1;
q.push(s);
while (q.size()) {
int x = q.front();
q.pop();
for (int i = head[x]; ~i; i = ed[i].nxt) {
if ((!dep[ed[i].to]) && (ed[i].capicity > ed[i].flow)) {
dep[ed[i].to] = dep[x] + 1;
q.push(ed[i].to);
}
}
}
return dep[t] > 0;
}
T dfs(int x, int t, T flow) {
if (x == t || (!flow)) return flow;
T ret = 0;
for (int& i = cur[x]; ~i; i = ed[i].nxt) {
T d;
if ((dep[ed[i].to] == dep[x] + 1) &&
(d = dfs(ed[i].to, t, std::min(flow - ret, ed[i].capicity - ed[i].flow)))) {
ret += d;
ed[i].flow += d;
ed[i ^ 1].flow -= d;
if (ret == flow) return ret;
}
}
return ret;
}
public:
T dinic() {
T max_flow = 0;
while (bfs(s, t)) {
cur = head;
max_flow += dfs(s, t, inf);
}
return max_flow;
}
};
并查集
dsu.hpp
#include <vector>
template <typename T>
class Dsu {
private:
T n;
std::vector<T> fa, siz;
public:
Dsu(T n) : n(n), fa(n), siz(n) {
for (T i = 0; i < n; ++i) fa[i] = i, siz[i] = 1;
}
bool empty() { return n == 0; }
T size() { return n; }
void reset() {
for (T i = 0; i < n; ++i) fa[i] = i, siz[i] = 1;
}
void resize(T _n) : n(_n) { reset(); }
T father(T x) { return fa[x] == x ? x : fa[x] = father(fa[x]); }
bool is_root(T x) { return father(x) == x; }
bool merge(T _u, T _v) {
_u = father(_u), _v = father(_v);
if (_u == _v) return false;
if (siz[_u] < siz[_v]) std::swap(_u, _v);
siz[fa[_u] = _v] += siz[_u];
return true;
}
bool check(T _u, T _v) { return father(_u) == father(_v); }
T size(T x) { return siz[father(x)]; }
};
BST
bst.hpp
#include <queue>
#include <tuple>
#include <utility>
#include <vector>
template <typename value_T, typename index_T>
class Splay {
const int not_exist = 0;
public:
index_T root;
private:
enum child_t { left = false, right = true };
struct Node {
value_T key;
index_T size, count;
index_T child[2];
index_T parent;
Node(const value_T key = value_T())
: key(key), size(0), count(0), parent(not_exist) {
child[left] = child[right] = not_exist;
}
};
std::vector<Node> data;
std::queue<index_T> bin;
void maintain(index_T index) {
if (index == not_exist) return;
data[index].size = data[data[index].child[left]].size +
data[data[index].child[right]].size +
data[index].count;
}
child_t identify(index_T index) {
return data[data[index].parent].child[right] == index ? right : left;
}
void clear(index_T index) {
data[index] = Node();
bin.push(index);
}
void rotate(index_T index) {
int parent = data[index].parent;
int grand = data[parent].parent;
child_t type = identify(index);
data[parent].child[type] = data[index].child[type ^ 1];
if (data[index].child[type ^ 1])
data[data[index].child[type ^ 1]].parent = parent;
data[index].child[type ^ 1] = parent;
if (grand) data[grand].child[identify(parent)] = index;
data[index].parent = grand;
data[parent].parent = index;
maintain(parent), maintain(index);
}
void splay(index_T index) {
for (index_T cur = data[index].parent; cur = data[index].parent, cur;
rotate(index)) {
if (data[cur].parent != not_exist)
rotate(identify(index) == identify(cur) ? cur : index);
}
root = index;
}
index_T new_node(value_T key) {
index_T index;
if (!bin.empty()) {
index = bin.front();
bin.pop();
} else {
index = data.size();
data.push_back(Node());
}
data[index].key = key;
data[index].count = 1;
data[index].size = 1;
return index;
}
public:
void insert(value_T key) {
if (root == not_exist) {
root = new_node(key);
return;
}
index_T cur = root, parent = not_exist;
while (cur != not_exist && data[cur].key != key) {
parent = cur, cur = data[cur].child[data[cur].key < key];
}
if (cur == not_exist) {
cur = new_node(key);
data[cur].parent = parent;
data[parent].child[data[parent].key < key] = cur;
} else
++data[cur].count;
maintain(cur);
maintain(parent);
splay(cur);
}
index_T rank(value_T key) {
index_T res = 0, cur = root;
while (key != data[cur].key) {
if (key < data[cur].key) {
cur = data[cur].child[left];
} else {
res += data[data[cur].child[left]].size + data[cur].count;
cur = data[cur].child[right];
}
}
res += data[data[cur].child[left]].size;
splay(cur);
return res + 1;
}
value_T kth(index_T rank) {
index_T cur = root;
while (true) {
if (data[cur].child[left] != not_exist &&
rank <= data[data[cur].child[left]].size) {
cur = data[cur].child[left];
} else if (rank >
data[data[cur].child[left]].size + data[cur].count) {
rank -= data[cur].count + data[data[cur].child[left]].size;
cur = data[cur].child[right];
} else {
splay(cur);
return data[cur].key;
}
}
}
private:
index_T prefix() {
index_T cur = data[root].child[left];
if (cur == not_exist) return cur;
while (data[cur].child[right] != not_exist)
cur = data[cur].child[right];
splay(cur);
return cur;
}
index_T suffix() {
index_T cur = data[root].child[right];
if (cur == not_exist) return cur;
while (data[cur].child[left]) cur = data[cur].child[left];
splay(cur);
return cur;
}
public:
void erase(int k) {
rank(k);
if (data[root].count > 1) {
--data[root].count;
maintain(root);
return;
}
if (data[root].child[left] == not_exist &&
data[root].child[right] == not_exist) {
clear(root);
root = not_exist;
return;
}
if (data[root].child[left] == not_exist ||
data[root].child[right] == not_exist) {
index_T cur = root;
root = data[root].child[right] + data[root].child[left];
data[root].parent = not_exist;
clear(cur);
return;
}
index_T cur = root, x = prefix();
data[data[cur].child[right]].parent = x;
data[x].child[right] = data[cur].child[right];
clear(cur);
maintain(root);
}
value_T prefix(value_T key) {
insert(key);
index_T index = prefix();
erase(key);
return data[index].key;
}
value_T suffix(value_T key) {
insert(key);
index_T index = suffix();
erase(key);
return data[index].key;
}
Splay() {
root = new_node(value_T()), data[root].size = data[root].count = 0;
}
};
template <typename index_T, typename value_T, index_T (*rand)()>
class FHQTreap {
private:
enum child_t { left = false, right = true };
struct Node {
Node* child[2];
value_T key;
index_T value;
index_T size, count;
Node(value_T key) : key(key), size(1), count(1) {
child[left] = child[right] = nullptr;
value = rand();
}
Node(Node* _node) {
child[left] = _node->child[left],
child[right] = _node->child[right];
key = _node->key, value = _node->value;
size = _node->size, count = _node->count;
}
void maintain() {
size = count;
if (child[left] != nullptr) size += child[left]->size;
if (child[right] != nullptr) size += child[right]->size;
}
};
public:
Node* root;
private:
std::pair<Node*, Node*> split_by_key(Node* cur, value_T key) {
if (cur == nullptr) return std::make_pair(nullptr, nullptr);
if (cur->key <= key) {
std::pair<Node*, Node*> res = split_by_key(cur->child[right], key);
cur->child[right] = res.first, cur->maintain();
return std::make_pair(cur, res.second);
} else {
std::pair<Node*, Node*> res = split_by_key(cur->child[left], key);
cur->child[left] = res.second, cur->maintain();
return std::make_pair(res.first, cur);
}
}
std::tuple<Node*, Node*, Node*> split_by_rank(Node* cur, index_T rank) {
if (cur == nullptr) return std::make_tuple(nullptr, nullptr, nullptr);
index_T left_size =
cur->child[left] == nullptr ? 0 : cur->child[left]->size;
if (rank <= left_size) {
Node *l, *mid, *r;
std::tie(l, mid, r) = split_by_rank(cur->child[left], rank);
cur->child[left] = r, cur->maintain();
return std::make_tuple(l, mid, cur);
} else if (rank <= left_size + cur->count) {
Node *l = cur->child[left], *r = cur->child[right];
cur->child[left] = cur->child[right] = nullptr;
return std::make_tuple(l, cur, r);
} else {
Node *l, *mid, *r;
std::tie(l, mid, r) =
split_by_rank(cur->child[right], rank - left_size - cur->count);
cur->child[right] = l, cur->maintain();
return std::make_tuple(cur, mid, r);
}
}
Node* merge(Node* u, Node* v) {
if (u == nullptr && v == nullptr) return nullptr;
if (u == nullptr || v == nullptr) return u == nullptr ? v : u;
if (u->value < v->value)
return u->child[right] = merge(u->child[right], v), u->maintain(),
u;
else
return v->child[left] = merge(u, v->child[left]), v->maintain(), v;
}
public:
void insert(const value_T key) {
std::pair<Node*, Node*> u = split_by_key(root, key);
std::pair<Node*, Node*> v = split_by_key(u.first, key - 1);
Node* cur;
if (v.second == nullptr)
cur = new Node(key);
else
++v.second->count, v.second->maintain();
root = merge(merge(v.first, v.second == nullptr ? cur : v.second),
u.second);
}
void erase(const value_T key) {
std::pair<Node*, Node*> u = split_by_key(root, key);
std::pair<Node*, Node*> v = split_by_key(u.first, key - 1);
if (v.second->count > 1)
--v.second->count, v.second->maintain(),
v.first = merge(v.first, v.second);
else {
if (u.first == v.second) u.first = nullptr;
delete v.second;
v.second = nullptr;
}
root = merge(v.first, u.second);
}
index_T rank(Node* cur, const value_T key) {
std::pair<Node*, Node*> res = split_by_key(cur, key - 1);
index_T rank = (res.first == nullptr ? 0 : res.first->size) + 1;
root = merge(res.first, res.second);
return rank;
}
value_T kth(Node* cur, const index_T rank) {
Node *l, *mid, *r;
std::tie(l, mid, r) = split_by_rank(cur, rank);
value_T key = mid->key;
root = merge(merge(l, mid), r);
return key;
}
value_T prefix(value_T key) {
std::pair<Node*, Node*> temp = split_by_key(root, key - 1);
value_T ret = kth(temp.first, temp.first->size);
root = merge(temp.first, temp.second);
return ret;
}
value_T suffix(value_T key) {
std::pair<Node*, Node*> temp = split_by_key(root, key);
value_T ret = kth(temp.second, 1);
root = merge(temp.first, temp.second);
return ret;
}
public:
FHQTreap() : root(nullptr){};
~FHQTreap() { delete root; }
};