A 但
知识点：构造、连通性、贪心
两种颜色都连通，且每列恰好选 $1$ 或 $2$ 个格子时，选中的格子只能整体贴着第 $1$ 行或第 $3$ 行延伸；如果在中途从上侧切到下侧，未选中的格子会被割断。
因此合法方案等价于：全选第 $1$ 行或全选第 $3$ 行，再从第 $2$ 行额外选 $k-n$ 个格子。若 $k2n$ 无解；否则取上下两行较大者，再加上中间行最大的 $k-n$ 个数即可。
时间复杂度 $\mathcal{O}(n\log n)$。
void solve() {
int n, k;
cin >> n >> k;
vector<int> a;
int s1 = 0, s3 = 0;
for (int i = 0, x; i < n; ++i) cin >> x, s1 += x;
for (int i = 0, x; i < n; ++i) cin >> x, a.push_back(x);
for (int i = 0, x; i < n; ++i) cin >> x, s3 += x;
if (k < n || k > 2 * n) return cout << -1 << endl, void();
sort(a.rbegin(), a.rend());
cout << max(s1, s3) + accumulate(a.begin(), a.begin() + k - n, 0LL) << endl;
}B 鱼
知识点：搜索、命中集、剪枝
先把完全相同的集合去重，因为相同集合允许同时保留，且删除元素对它们的影响一致。
若当前未被删除的集合中存在两个不同集合相交，则这两个集合不能同时保留，所以任意可行删除集必须至少删除它们并集中的一个元素。于是每次找到一对冲突集合，在至多 $8$ 个候选元素中分支删除一个，搜索深度不超过 $3$。每找到一个合法方案，就按先删除数量、再字典序更新答案。
时间复杂度 $\mathcal{O}(n\log n+8^3n)$。
void solve() {
int n, k;
cin >> n >> k;
vector<array<int, 4>> a(n);
for (auto &v : a) {
for (auto &x : v) cin >> x;
sort(v.begin(), v.end());
}
sort(a.begin(), a.end());
a.erase(unique(a.begin(), a.end()), a.end());
n = a.size();
vector<int> ans;
int best = 4;
unordered_map<int, int> mp;
auto killed = [&](const array<int, 4> &v, const vector<int> &del) {
for (auto x : v) {
for (auto y : del) {
if (x == y) return true;
}
}
return false;
};
auto find = [&](const vector<int> &del) -> pii {
mp.clear();
for (int i = 0; i < n; ++i) {
if (killed(a[i], del)) continue;
for (auto x : a[i]) {
if (mp.count(x)) {
return {i, mp[x]};
}
}
for (auto x : a[i]) {
mp[x] = i;
}
}
return {-1, -1};
};
auto dfs = [&](auto self, vector<int> &del) -> void {
if (del.size() > 3 || del.size() > best) return;
auto [u, v] = find(del);
if (u == -1) {
auto cur = del;
sort(cur.begin(), cur.end());
if (cur.size() < best || (cur.size() == best && cur < ans)) {
best = cur.size();
ans = cur;
}
return;
}
if (del.size() == 3) return;
vector<int> cand;
for (auto x : a[u]) cand.push_back(x);
for (auto x : a[v]) cand.push_back(x);
sort(cand.begin(), cand.end());
cand.erase(unique(cand.begin(), cand.end()), cand.end());
for (auto x : cand) {
del.push_back(x);
self(self, del);
del.pop_back();
}
};
vector<int> del;
dfs(dfs, del);
if (best > 3) {
cout << "NO" << endl;
} else {
cout << "YES " << best;
for (auto x : ans) cout << " " << x;
cout << endl;
}
}C 玩具
知识点：区间闭包、倍增 ST 表、贪心合并
把所有排列中的元素都转成它们在 $p_1$ 中的位置。一个最终段在所有排列中合法，等价于：它在每个排列中的位置集合都是连续区间。
对当前区间 $[L,R]$，不断做闭包：必须包含完整的初始段；在每个排列中，先求 $[L,R]$ 的元素出现位置范围 $[mn,mx]$，这个范围内出现的所有 $p_1$ 位置也必须被纳入新区间。用 ST 表维护区间最大最小值，即可快速扩展。
扫描 $p_1$，每次取最小闭包作为一段；若扩展后与前一段相交，则它们必须合并，用栈弹出即可。这样得到的段数最多。
注意全开 $\texttt{long long}$ 会超空间。
时间复杂度 $\mathcal{O}(kn\log n)$。
template <class T> struct ST {...};
using i32 = int32_t;
void solve() {
int n, k;
cin >> n >> k;
vector<int> id(n + 1);
for (int i = 1, x; i <= n; i++) cin >> x, id[x] = i;
vector<ST<i32>> pos, val;
for (int r = 2; r <= k; r++) {
vector<i32> a(n + 1), b(n + 1);
for (int i = 1, x; i <= n; i++) cin >> x, a[i] = id[x], b[a[i]] = i;
val.emplace_back(n);
pos.emplace_back(n);
val.back().init(a);
pos.back().init(b);
}
int s;
cin >> s;
vector<i32> L0(n + 1), R0(n + 1);
int cur = 0;
for (int i = 1, x; i <= s; i++) {
cin >> x;
int l = cur + 1, r = cur + x;
for (int j = l; j <= r; j++) L0[j] = l, R0[j] = r;
cur = r;
}
vector<array<i32, 2>> ans;
for (int i = 1; i <= n; i++) {
if (!ans.empty() && i <= ans.back()[1]) continue;
i32 L = i, R = i;
while (true) {
i32 nL = L0[L], nR = R0[R];
for (int r = 2; r <= k; r++) {
i32 mn = pos[r - 2].getMin(L, R), mx = pos[r - 2].getMax(L, R);
nL = min(nL, val[r - 2].getMin(mn, mx));
nR = max(nR, val[r - 2].getMax(mn, mx));
}
while (!ans.empty() && nL <= ans.back()[1]) {
nL = min(nL, ans.back()[0]);
nR = max(nR, ans.back()[1]);
ans.pop_back();
}
if (nL == L && nR == R) break;
L = nL, R = nR;
}
ans.push_back({L, R});
}
cout << ans.size() << endl;
for (auto [l, r] : ans) {
cout << r - l + 1 << " ";
}
cout << endl;
}D 走失
知识点：按位独立、Fibonacci、异或变换
对每一位单独看，合法游走就是长度为 $K$、没有相邻两个 $1$ 的 01 串。设起始位为 $b$，特征位为 $x$，需要统计满足条件且异或为 $x$ 的串数，作为这一位上的转移系数。
若起始位为 $0$，总数为 $F_{K+1}$；若起始位为 $1$，总数为 $F_K$。再按异或奇偶拆开：
$$
\text{偶数个 }1=\frac{\text{总数}+\sum(-1)^{xor}}2,\qquad
\text{奇数个 }1=\frac{\text{总数}-\sum(-1)^{xor}}2
$$
其中 $\sum(-1)^{xor}$ 对 $K$ 呈周期 $6$。得到每一位上的 $2\times 2$ 转移后，对数组做类似 $\texttt{FWT}$ 的逐位变换即可。
为了美观，这里使用矩阵快速幂求斐波那契数列，倍增求亦可。
时间复杂度 $\mathcal{O}(n2^n+\log K)$。
int _1[] = {1, 0, -1, -1, 0, 1}, _2[] = {-1, -1, 0, 1, 1, 0};
void solve() {
int n, k;
cin >> n >> k;
int siz = 1LL << n;
vector<Z> a(siz);
for (auto &v : a) cin >> v;
Matrix<Z> F(2, 2, 1);
F[1][1] = 0;
F = F.ksm(k);
Z s1 = _1[(k - 1) % 6], s2 = _2[(k - 1) % 6];
Z q00 = (F[0][0] + s1) / 2, q01 = (F[0][1] + s2) / 2, q10 = (F[0][0] - s1) / 2, q11 = (F[0][1] - s2) / 2;
for (int len = 1; len < siz; len <<= 1) {
for (int i = 0; i < siz; i += 2 * len) {
for (int j = 0; j < len; ++j) {
Z u = a[i + j], v = a[i + len + j];
a[i + j] = q00 * u + q01 * v;
a[i + len + j] = q10 * u + q11 * v;
}
}
}
int ans = 0;
for (int i = 0; i < siz; ++i) ans ^= (a[i] * (i + 1)).val();
cout << ans << endl;
}倍增求斐波那契数列：
auto fib = [&](auto &&self, int n) -> array<Z, 2> {
if (n == 0) return {0, 1};
auto [a, b] = self(self, n >> 1);
Z c = a * (2 * b - a), d = a * a + b * b;
if (n & 1) return {d, c + d};
return {c, d};
};
auto [fk, fk1] = fib(fib, k);
Z s1 = _1[(k - 1) % 6], s2 = _2[(k - 1) % 6];
Z q00 = (fk1 + s1) / 2, q01 = (fk + s2) / 2, q10 = (fk1 - s1) / 2, q11 = (fk - s2) / 2;E 芳草地
知识点：后缀自动机、贡献转换、根号分治、离线并查集
把贡献按 $B$ 的每次出现来数。若某个出现的右端点为 $j$，取后缀长度 $l$ 作为 $A$，则可作为 $B$ 的长度有 $l,2l,3l,\ldots\le j$，数量为 $\left\lfloor j/l\right\rfloor$。所以答案等价于：
$$
\sum_{j=1}^n\sum_{l=1}^j occ(S[j-l+1..j])\left\lfloor\frac jl\right\rfloor
$$
用 $\texttt{SAM}$ 求任意子串出现次数。短长度 $l\le B$ 直接枚举所有出现。长长度部分设
$$
G_j(x)=\sum_{l=1}^{x}occ(S[j-l+1..j])
$$
令 $m=\left\lfloor\dfrac{j}{B+1}\right\rfloor$，则所有 $l>B$ 的贡献可以写成：
$$
G_j(j)-mG_j(B)+\sum_{q=2}^{m}G_j\left(\left\lfloor\frac{j}{q}\right\rfloor\right)
$$
因为每个 $l>B$ 的系数正好是 $1+#{q\ge2:q\le\lfloor j/l\rfloor}=\lfloor j/l\rfloor$，而 $l\le B$ 的系数会被 $-mG_j(B)$ 抵消。
接下来只需要快速回答 $G_j(x)$。将询问按 $x$ 分组，按长度从大到小在 $\texttt{SAM}$ 后缀树上激活状态并用并查集合并，查询时就能找到表示长度 $x$ 后缀的状态，从而用后缀链前缀和计算 $G_j(x)$。
时间复杂度 $\mathcal{O}(nB+\frac{n^2}{B}\alpha(n))$。
template <int ALPHABET_SIZE = 26> struct SAM {...};
void solve() {
string s;
cin >> s;
int n = s.size();
SAM sam;
int last = 1;
vector<int> pos(n + 1), cnt(2 * n + 5);
for (int i = 1; i <= n; ++i) {
last = sam.extend(last, s[i - 1]);
++cnt[last];
pos[i] = last;
}
int sz = sam.size();
cnt.resize(sz);
vector<int> ord(sz);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) { return sam.len(a) < sam.len(b); });
for (int i = sz - 1; i >= 0; --i) {
int v = ord[i];
if (v > 1) cnt[sam.link(v)] += cnt[v];
}
vector<Z> pre(sz);
for (auto v : ord) {
if (v <= 1) continue;
int f = sam.link(v);
pre[v] = pre[f] + Z(cnt[v]) * (sam.len(v) - sam.len(f));
}
int B = min(700LL, n);
Z ans = 0;
for (int i = 0; i < n; ++i) {
int v = 1;
for (int d = 1; d <= B && i + d <= n; ++d) {
v = sam.next(v, s[i + d - 1]);
ans += Z(cnt[v]) * ((i + d) / d);
}
}
vector<int> num(n + 1), off(n + 2), cur(n + 1);
for (int j = B + 1; j <= n; ++j) {
int m = j / (B + 1);
++num[B];
for (int q = 2; q <= m; ++q) {
++num[j / q];
}
}
for (int i = 0; i <= n; ++i) {
off[i + 1] = off[i] + num[i];
}
vector<array<int, 2>> qs(off[n + 1]);
cur = off;
for (int j = B + 1; j <= n; ++j) {
int m = j / (B + 1);
ans += pre[pos[j]];
qs[cur[B]++] = {pos[j], -m};
for (int q = 2; q <= m; ++q) {
qs[cur[j / q]++] = {pos[j], 1LL};
}
}
vector<int> hl(n + 1, -1), nl(sz, -1);
vector<int> hs(sz, -1), ns(sz, -1);
for (int v = 2; v < sz; ++v) {
nl[v] = hl[sam.len(v)];
hl[sam.len(v)] = v;
int f = sam.link(v);
ns[v] = hs[f];
hs[f] = v;
}
vector<int> fa(sz);
vector<bool> vis(sz);
auto find = [&](int x) {
int r = x;
while (fa[r] != r) r = fa[r];
while (fa[x] != x) {
int y = fa[x];
fa[x] = r;
x = y;
}
return r;
};
for (int x = n; x >= 1; --x) {
for (int u = hl[x]; u != -1; u = nl[u]) {
vis[u] = 1;
fa[u] = u;
for (int e = hs[u]; e != -1; e = ns[e]) {
if (vis[e]) fa[find(e)] = u;
}
}
for (int id = off[x]; id < off[x + 1]; ++id) {
int u = find(qs[id][0]);
int f = sam.link(u);
ans += Z(qs[id][1]) * (pre[f] + Z(cnt[u]) * (x - sam.len(f)));
}
}
cout << ans << endl;
}F 莉莉安
知识点：树上匹配、凸函数、Slope Trick、左偏树
固定边长后，黑白叶子的最小匹配代价可以按边贡献计算。设一条边下方黑白叶数量差为 $bal$，则这条边必然被跨过 $|bal|$ 次，因此匹配代价贡献为：
$$
|bal|\cdot x_e
$$
于是目标变为：
$$
\sum_e |x_e-a_e|+|bal_e|x_e
$$
并要求所有叶子到根距离相等。
对每个点 $u$ 维护函数 $f_u(d)$：使 $u$ 子树内所有叶子到 $u$ 的距离都为 $d$ 的最小代价。多个儿子合并时就是函数相加；向父亲转移时，要加上父边的代价并做一次凸函数变换。
这些函数都是分段线性凸函数，可以用 $\texttt{slope trick}$ 维护：$base$ 表示当前值，$L$ 表示初始斜率，左偏树维护斜率变化的断点。子树合并就是合并堆，经过一条边时根据 $a_e$ 和 $|bal|$ 调整断点。最后根节点没有父边，只需在 $d\ge0$ 上取 $f_1(d)$ 的最小值。
时间复杂度 $\mathcal{O}(n\log n)$。
template <class T, class Cmp = less<T>> struct LeftistHeap {...};
void solve() {
int n;
cin >> n;
vector<vector<pii>> g(n + 1);
for (int i = 1; i < n; ++i) {
int u, v, a;
cin >> u >> v >> a;
g[u].push_back({v, a});
g[v].push_back({u, a});
}
vector<int> col(n + 1);
for (int i = 1; i <= n; ++i) cin >> col[i];
vector<int> fa(n + 1), w(n + 1), ord;
fa[1] = -1;
ord.push_back(1);
for (int i = 0; i < ord.size(); ++i) {
int u = ord[i];
for (auto [v, a] : g[u]) {
if (v == fa[u]) continue;
fa[v] = u;
w[v] = a;
ord.push_back(v);
}
}
vector<int> bal(n + 1), base(n + 1), L(n + 1);
LeftistHeap<int> q(2 * n + 5);
auto trans = [&](int u, int a, int b) {
int l = b - 1, r = b + 1, l0 = L[u];
base[u] += a;
if (a == 0) {
if (l0 < r) {
int k = r - l0;
while (q[u].size() > k) q[u].pop();
} else {
q[u].clear();
L[u] = r;
}
return;
}
if (l0 <= l) {
int k = r - l0;
while (q[u].size() > k) q[u].pop();
int x = q[u].pop(), y = q[u].pop();
q[u] << x + a << y + a;
} else {
if (l0 == l + 1) {
while (q[u].size() > 1) q[u].pop();
int x = q[u].pop();
q[u].clear();
q[u] << a << x + a;
} else {
q[u].clear();
q[u] << a << a;
}
L[u] = l;
}
};
for (int i = n - 1; i >= 0; --i) {
int u = ord[i];
bool leaf = true;
for (auto [v, a] : g[u]) {
if (fa[v] != u) continue;
leaf = false;
bal[u] += bal[v];
base[u] += base[v];
L[u] += L[v];
q[u] += q[v];
}
if (leaf) {
bal[u] = col[u];
if (u != 1) {
base[u] = w[u];
L[u] = 0;
q[u] << w[u] << w[u];
}
} else if (u != 1) {
trans(u, w[u], abs(bal[u]));
}
}
vector<int> p;
while (!q[1].empty()) p.push_back(q[1].pop());
reverse(p.begin(), p.end());
int ans = base[1], lst = 0;
for (int i = 0; i < p.size(); ++i) {
int s = L[1] + i;
int len = p[i] - lst;
if (s < 0) ans += s * len;
lst = p[i];
}
cout << ans << endl;
}约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
cout << fixed << setprecision(20);
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}ST表
template <class T> struct ST {
int n, k;
vector<vector<T>> Max;
vector<vector<T>> Min;
ST(int n) : n(n), k(__lg(n)) {
Max.resize(k + 1, vector<T>(n + 1));
Min.resize(k + 1, vector<T>(n + 1));
}
template <class Array> void init(const Array &a) {
for (int i = 1; i <= n; i++) {
Max[0][i] = a[i];
Min[0][i] = a[i];
}
for (int i = 0, t = 1; i < k; i++, t <<= 1) {
const int lim = n - (t << 1) + 1;
for (int j = 1; j <= lim; j++) {
Max[i + 1][j] = max(Max[i][j], Max[i][j + t]);
Min[i + 1][j] = min(Min[i][j], Min[i][j + t]);
}
}
}
T getMax(int l, int r) {
if (l > r) swap(l, r);
int k = __lg(r - l + 1);
return max(Max[k][l], Max[k][r - (1LL << k) + 1]);
}
T getMin(int l, int r) {
if (l > r) swap(l, r);
int k = __lg(r - l + 1);
return min(Min[k][l], Min[k][r - (1LL << k) + 1]);
}
};矩阵
template <class T> struct Matrix {
int n, m;
vector<vector<T>> a;
Matrix(int n = 0, int m = 0, T val = T()) : n(n), m(m), a(n, vector<T>(m, val)) {}
static Matrix identity(int n) {
Matrix I(n, n);
for (int i = 0; i < n; i++) I.a[i][i] = T(1);
return I;
}
vector<T> &operator[](int i) {
return a[i];
}
const vector<T> &operator[](int i) const {
return a[i];
}
Matrix operator+(const Matrix &other) const {
assert(n == other.n && m == other.m);
Matrix res(n, m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) res[i][j] = a[i][j] + other[i][j];
return res;
}
Matrix operator-(const Matrix &other) const {
assert(n == other.n && m == other.m);
Matrix res(n, m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) res[i][j] = a[i][j] - other[i][j];
return res;
}
Matrix operator*(const Matrix &other) const {
assert(m == other.n);
Matrix res(n, other.m, T(0));
for (int i = 0; i < n; i++)
for (int k = 0; k < m; k++)
for (int j = 0; j < other.m; j++) res[i][j] = res[i][j] + a[i][k] * other[k][j];
return res;
}
Matrix operator*(const T &k) const {
Matrix res(n, m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) res[i][j] = a[i][j] * k;
return res;
}
Matrix transpose() const {
Matrix res(m, n);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) res[j][i] = a[i][j];
return res;
}
Matrix ksm(int exp) const {
assert(n == m);
Matrix base = *this;
Matrix res = identity(n);
while (exp > 0) {
if (exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}
};
template <class T> T determinant(int n, Matrix<T> &mat) {
T det = T(1);
int sign = 1;
for (int i = 0; i < n; i++) {
int pivot = i;
while (pivot < n && mat[pivot][i].isZero()) pivot++;
if (pivot == n) return T();
if (pivot != i) {
swap(mat[i], mat[pivot]);
sign = -sign;
}
det *= mat[i][i];
for (int j = i + 1; j < n; j++) {
if (!mat[j][i].isZero()) {
T factor = mat[j][i] / mat[i][i];
for (int k = i; k < n; k++) {
mat[j][k] -= factor * mat[i][k];
}
}
}
}
if (sign == -1) {
det = T() - det;
}
return det;
}自动取模
constexpr int MOD = 998244353;
template <class T> constexpr T mypow(T a, int b) {
T res = 1;
while (b) {
if (b & 1) res *= a;
b >>= 1;
a *= a;
}
return res;
}
template <int P> struct MInt {
int x;
constexpr MInt() : x() {}
constexpr MInt(int x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return mypow(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1ll * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr istream &operator>>(istream &is, MInt &a) {
int v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template <> int MInt<0>::Mod = 998244353;
template <int V, int P> constexpr MInt<P> CInv = MInt<P>(V).inv();
using Z = MInt<MOD>;后缀自动机
template <int ALPHABET_SIZE = 26> struct SAM {
struct Node {
int len;
int link;
array<int, ALPHABET_SIZE> next;
Node() : len{}, link{}, next{} {}
};
vector<Node> t;
SAM() {
init();
}
void init() {
t.assign(2, Node());
t[0].next.fill(1);
t[0].len = -1;
}
int newNode() {
t.emplace_back();
return t.size() - 1;
}
int extend(int p, int c) {
if (t[p].next[c]) {
int q = t[p].next[c];
if (t[q].len == t[p].len + 1) {
return q;
}
int r = newNode();
t[r].len = t[p].len + 1;
t[r].link = t[q].link;
t[r].next = t[q].next;
t[q].link = r;
while (t[p].next[c] == q) {
t[p].next[c] = r;
p = t[p].link;
}
return r;
}
int cur = newNode();
t[cur].len = t[p].len + 1;
while (!t[p].next[c]) {
t[p].next[c] = cur;
p = t[p].link;
}
t[cur].link = extend(p, c);
return cur;
}
int extend(int p, char c, char offset = 'a') {
return extend(p, c - offset);
}
int next(int p, int x) {
return t[p].next[x];
}
int next(int p, char c, char offset = 'a') {
return next(p, c - offset);
}
int link(int p) {
return t[p].link;
}
int len(int p) {
return t[p].len;
}
int size() {
return t.size();
}
};左偏堆
template <class T, class Cmp = less<T>> struct LeftistHeap {
struct Node {
T v;
int l, r, d;
};
vector<Node> tr;
vector<int> rt, siz;
Cmp cmp;
int tot;
LeftistHeap() {}
LeftistHeap(int n) {
init(n);
}
void init(int n) {
tr.assign(1, {});
rt.assign(n + 1, 0);
siz.assign(n + 1, 0);
tot = 0;
}
int mergeRoot(int x, int y) {
if (!x || !y) return x | y;
if (cmp(tr[x].v, tr[y].v)) swap(x, y);
tr[x].r = mergeRoot(tr[x].r, y);
if (tr[tr[x].l].d < tr[tr[x].r].d) swap(tr[x].l, tr[x].r);
tr[x].d = tr[tr[x].r].d + 1;
return x;
}
void merge(int x, int y) {
if (x == y) return;
rt[x] = mergeRoot(rt[x], rt[y]);
siz[x] += siz[y];
rt[y] = siz[y] = 0;
}
void push(int x, const T &v) {
tr.push_back({v, 0, 0, 1});
rt[x] = mergeRoot(rt[x], ++tot);
++siz[x];
}
T top(int x) {
return tr[rt[x]].v;
}
T pop(int x) {
int u = rt[x];
T res = tr[u].v;
rt[x] = mergeRoot(tr[u].l, tr[u].r);
--siz[x];
return res;
}
void clear(int x) {
rt[x] = siz[x] = 0;
}
bool empty(int x) {
return siz[x] == 0;
}
int size(int x) {
return siz[x];
}
struct Ref {
LeftistHeap *h;
int x;
Ref &operator+=(Ref y) {
h->merge(x, y.x);
return *this;
}
Ref &operator<<(const T &v) {
h->push(x, v);
return *this;
}
T top() {
return h->top(x);
}
T pop() {
return h->pop(x);
}
void clear() {
h->clear(x);
}
bool empty() {
return h->empty(x);
}
int size() {
return h->size(x);
}
};
Ref operator[](int x) {
return {this, x};
}
};