全网首个题解（AC）C++
2026-08-05 09:06:01
发布于：陕西
21阅读
0回复
0点赞
第一个公布题解的来了 【豆包】 (带注释）特别特别特别特别特别特别特别特别特别特别特别长 ！！！！！！
！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！
C++解题步骤
：
#include <bits/stdc++.h>
#define BUFSIZE 10000000
/**
* @brief 快读结构体：大内存缓冲区快速读入，替代cin，处理大量输入
* 使用fread整块读取，减少系统调用开销
*/
struct read {
char buf[BUFSIZE], *p1, *p2, c;
read(): p1(buf), p2(buf) {}
// 获取下一个字符，缓冲区耗尽则重新fread
char gc(void) {
return p1 == p2 && (p2 = buf + fread(p1 = buf, 1, BUFSIZE, stdin), p1 == p2) ? EOF : *p1++;
}
// 重载 >> 读取无符号整数
read &operator >>(unsigned &x) {
for (c = gc(), x = 0; c < '0' || c > '9'; c = gc());
for (; c >= '0' && c <= '9'; c = gc())
x = x * 10 + (c - '0');
return *this;
}
} cin;
/**
* @brief 快写结构体：缓冲区批量输出，析构时一次性fwrite刷出
*/
struct write {
char buf[BUFSIZE], *p1, *p2;
write(): p1(buf), p2(buf + BUFSIZE) {}
// 程序结束自动把缓冲区内容写stdout
~write() {
fwrite(buf, 1, p1 - buf, stdout);
}
// 输出单个字符，缓冲区满就刷新
void pc(char c) {
p1 == p2 &&(fwrite(buf, 1, p1 - buf, stdout), p1 = buf), *p1++ = c;
}
// 输出long long整数
write &operator <<(long long x) {
static unsigned stk[30], tp;
do stk[tp++] = '0' + x % 10, x /= 10;
while (x);
while (tp)
pc(stk[--tp]);
return *this;
}
// 输出单个字符
write &operator <<(char c) {
return pc(c), *this;
}
} cout;
// 全局变量
unsigned n; // Trie树节点总数
unsigned s[500010][2]; // Trie树，s[u][0/1] 子节点编号
unsigned fail[500010]; // AC自动机失配指针
unsigned val[500010]; // 每个节点权值
unsigned a[500010]; // 输入a数组，向上跳a[x]层找祖先
unsigned p[500010]; // p[x]：x对应的目标祖先节点，0代表不存在
/**
* @namespace TT
* @brief 重链剖分辅助模块：把原Trie树上节点映射为二维区间[A,B]
* 构建一棵辅助平衡二叉树，做括号序，给每个节点分配A,B,R时间戳
*/
namespace TT {
unsigned rt; // 辅助二叉树根
unsigned cnt; // 辅助二叉树节点计数
unsigned sz[1000010]; // 辅助树子树大小
unsigned csz[1000010]; // 辅助树有效元素计数
unsigned A[1000010]; // 辅助节点对应区间左端点
unsigned B[1000010]; // 辅助节点对应区间右端点
unsigned ls[500010]; // 辅助二叉树左孩子
unsigned rs[500010]; // 辅助二叉树右孩子
unsigned tp[500010]; // 类型标记：0=合并多条重链；1=单条重链内部节点
unsigned s[500010]; // 原Trie子树大小（重链dfs）
unsigned fa[500010]; // 原Trie父节点
unsigned son[500010]; // 原Trie重儿子
/**
* @brief 创建辅助二叉树叶子，对应原树上单点x
* 叶子编号偏移n，与内部节点区分开
*/
unsigned newnode(unsigned x) {
unsigned u = x + n;
csz[u] = sz[u] = 1, A[u] = B[u] = x;
return u;
}
/**
* @brief 构建辅助二叉树内部节点
* @param x 左子树
* @param y 右子树
* @param p tp标记 0/1
*/
unsigned bd(unsigned x, unsigned y, unsigned p) {
unsigned u = ++cnt;
ls[u] = x, rs[u] = y, sz[u] = sz[x] + sz[y], tp[u] = p;
if (p == 0) {
// tp=0：合并多条重链，区间拼接左右子树
csz[u] = csz[x] + csz[y], A[u] = A[x], B[u] = B[y];
} else {
// tp=1：同一条重链内部，区间继承左子树
csz[u] = csz[x], A[u] = A[x], B[u] = B[x];
}
return u;
}
unsigned c[500010], cs[500010], ccnt;
/**
* @brief 根据cs大小前缀数组，二分分割，递归构建平衡二叉树
* 类似笛卡尔树，保证树高logN
*/
unsigned cbuild(unsigned l, unsigned r, unsigned p) {
if (l == r)
return c[l];
unsigned u = std::lower_bound(cs + l, cs + r, cs[l - 1] + (cs[r] - cs[l - 1]) / 2) - cs;
if (u == r)
return bd(cbuild(l, r - 1, p), c[r], p);
else
return bd(cbuild(l, u, p), cbuild(u + 1, r, p), p);
}
/**
* @brief 重链分解后自底向上构建辅助二叉树
* x为重链顶端；先递归处理全部轻儿子，再组装整条重链
*/
unsigned build(unsigned x) {
unsigned u = x;
static unsigned tmp[500010];
// 沿着重链向下遍历
while (u) {
// 递归构建所有轻儿子
for (auto w : ::s[u])
if (w && w != son[u])
tmp[w] = build(w);
// 收集当前节点+所有轻儿子，构建本重链片段(tp=1)
ccnt = 0, c[++ccnt] = newnode(u), cs[ccnt] = 1;
for (auto w : ::s[u])
if (w && w != son[u])
c[++ccnt] = tmp[w], cs[ccnt] = cs[ccnt - 1] + sz[tmp[w]];
tmp[u] = cbuild(1, ccnt, 1), u = son[u];
}
// 将整条重链各个片段合并为上层树(tp=0)
u = x, ccnt = 0;
while (u)
c[++ccnt] = tmp[u], cs[ccnt] = cs[ccnt - 1] + sz[tmp[u]], u = son[u];
return cbuild(1, ccnt, 0);
}
unsigned R[1000010]; // 辅助节点管辖区间的右边界
unsigned ct; // 全局时间戳，分配括号序编号
/**
* @brief DFS遍历辅助二叉树，分配A,B,R括号序时间戳
*/
void ini(unsigned x) {
if (x > n) {
// 叶子节点分配时间戳
return A[x] = B[x] = R[x] = ++ct, void();
}
ini(ls[x]), ini(rs[x]);
A[x] = A[A[x] + n], B[x] = B[B[x] + n];
R[x] = ct;
}
/**
* @brief Trie树上DFS，求子树大小、重儿子son；维护栈f，计算p[x]祖先
*/
void dfs(unsigned x) {
static unsigned pt, f[500010];
f[pt++] = x, s[x] = 1, son[x] = 0;
// a[x] >= 当前栈深度，没有对应祖先，p[x]=0
if (a[x] >= pt)
p[x] = 0;
else
p[x] = f[a[x]];
for (unsigned u : ::s[x])
if (u) {
fa[u] = x;
dfs(u);
s[x] += s[u];
// 更新重儿子：子树最大的孩子
son[x] = (s[son[x]] > s[u] ? son[x] : u);
}
--pt;
}
/**
* @brief TT模块对外入口：初始化，重链剖分，构建辅助树，分配括号序
*/
void init() {
cnt = 0;
ct = 0;
dfs(1);
rt = build(1);
ini(rt);
}
}
std::vector<unsigned> vec[500010]; // fail树邻接表
unsigned sz[500010];
/**
* @brief fail树上dfs求子树大小，用于启发式合并排序
*/
void dfs(unsigned x) {
sz[x] = 1;
for (auto u : vec[x])
dfs(u), sz[x] += sz[u];
}
long long ans[500010]; // 存储每个节点答案
/**
* @brief Segment‑Tree‑Beats 动态节点线段树，支持区间取max，区间求和
* 内存池stk做节点回收复用
*/
#define MAXN 2100010
unsigned cct; // Beats动态节点编号
unsigned ls[MAXN]; // Beats左孩子
unsigned rs[MAXN]; // Beats右孩子
unsigned mn[MAXN]; // 区间最小值
unsigned lmn[MAXN]; // 区间次小值
unsigned cnt[MAXN]; // 等于mn的元素个数
unsigned tag[MAXN]; // 区间取max懒标记
long long sum[MAXN]; // 区间总和
long long stk[MAXN]; // 回收栈，废弃节点放回这里复用
unsigned tp; // 回收栈栈顶指针
/**
* @brief 创建Beats动态节点，pos对应TT辅助树上的节点
*/
inline unsigned newnode(unsigned pos) {
using TT::csz;
unsigned u = tp ? stk[--tp] : ++cct;
ls[u] = rs[u] = 0, tag[u] = sum[u] = mn[u] = 0, cnt[u] = csz[pos], lmn[u] = 2000000000u;
return u;
}
/**
* @brief Beats打懒标记：区间全部元素取max(v)
*/
inline void addtag(unsigned x, unsigned v) {
sum[x] += 1ll * (v - mn[x]) * cnt[x];
mn[x] = tag[x] = v;
}
/**
* @brief 懒标记下推，pos是TT辅助树节点，区分tp=0/tp=1
*/
inline void pushdown(unsigned x, unsigned pos) {
if (!tag[x])
return;
if (!ls[x])
ls[x] = newnode(TT::ls[pos]);
if (TT::tp[pos] == 0) {
// tp=0：合并重链，存在左右两个孩子
if (!rs[x])
rs[x] = newnode(TT::rs[pos]);
if (mn[ls[x]] == mn[rs[x]])
addtag(ls[x], tag[x]), addtag(rs[x], tag[x]);
else if (mn[ls[x]] < mn[rs[x]])
addtag(ls[x], tag[x]);
else
addtag(rs[x], tag[x]);
} else {
// tp=1：重链内部，只有左孩子
addtag(ls[x], tag[x]);
}
tag[x] = 0;
}
/**
* @brief 向上更新，由孩子信息更新当前节点sum/mn/lmn/cnt
*/
inline void pushup(unsigned x, unsigned pos) {
using TT::csz;
if (TT::tp[pos] == 0) {
if (!ls[x] && !rs[x]) {
sum[x] = mn[x] = 0, cnt[x] = csz[pos], lmn[x] = 2000000000u;
} else if (!ls[x]) {
sum[x] = sum[rs[x]], mn[x] = 0;
lmn[x] = (mn[rs[x]] == 0 ? lmn[rs[x]] : mn[rs[x]]);
cnt[x] = csz[TT::ls[pos]] + (mn[rs[x]] == 0 ? cnt[rs[x]] : 0);
} else if (!rs[x]) {
sum[x] = sum[ls[x]], mn[x] = 0;
lmn[x] = (mn[ls[x]] == 0 ? lmn[ls[x]] : mn[ls[x]]);
cnt[x] = csz[TT::rs[pos]] + (mn[ls[x]] == 0 ? cnt[ls[x]] : 0);
} else {
if (mn[ls[x]] == mn[rs[x]]) {
sum[x] = sum[ls[x]] + sum[rs[x]], mn[x] = mn[ls[x]];
lmn[x] = std::min(lmn[ls[x]], lmn[rs[x]]);
cnt[x] = cnt[ls[x]] + cnt[rs[x]];
} else if (mn[ls[x]] < mn[rs[x]]) {
sum[x] = sum[ls[x]] + sum[rs[x]], mn[x] = mn[ls[x]];
lmn[x] = std::min(lmn[ls[x]], mn[rs[x]]);
cnt[x] = cnt[ls[x]];
} else {
sum[x] = sum[ls[x]] + sum[rs[x]], mn[x] = mn[rs[x]];
lmn[x] = std::min(mn[ls[x]], lmn[rs[x]]);
cnt[x] = cnt[rs[x]];
}
}
} else if (!ls[x]) {
sum[x] = mn[x] = 0, cnt[x] = csz[pos], lmn[x] = 2000000000u;
} else {
sum[x] = sum[ls[x]], mn[x] = mn[ls[x]];
cnt[x] = cnt[ls[x]], lmn[x] = lmn[ls[x]];
}
}
/**
* @brief Beats核心：区间取max(v)
* v<=min直接返回；v<次小打懒标记；否则递归向下
*/
inline void beats(unsigned &rt, unsigned v, unsigned pos) {
if (!rt)
rt = newnode(pos);
if (v <= mn[rt])
return;
if (v < lmn[rt])
return addtag(rt, v);
tag[rt] = 0;
beats(ls[rt], v, TT::ls[pos]);
beats(rs[rt], v, TT::rs[pos]);
pushup(rt, pos);
}
/**
* @brief 二维更新：[*, b] 全部取max(v)
*/
inline void lupdate(unsigned b, unsigned v, unsigned &rt, unsigned pos = TT::rt) {
using TT::B, TT::R;
if (!rt)
rt = newnode(pos);
if (B[pos] == b)
return beats(rt, v, pos);
pushdown(rt, pos);
if (b <= R[TT::ls[pos]])
lupdate(b, v, ls[rt], TT::ls[pos]);
else {
beats(ls[rt], v, TT::ls[pos]);
lupdate(b, v, rs[rt], TT::rs[pos]);
}
pushup(rt, pos);
}
/**
* @brief 二维更新：[a, *] 全部取max(v)
*/
inline void rupdate(unsigned a, unsigned v, unsigned &rt, unsigned pos = TT::rt) {
using TT::A, TT::R;
if (!rt)
rt = newnode(pos);
if (A[pos] == a)
return beats(rt, v, pos);
pushdown(rt, pos);
if (a > R[TT::ls[pos]])
rupdate(a, v, rs[rt], TT::rs[pos]);
else {
rupdate(a, v, ls[rt], TT::ls[pos]);
beats(rs[rt], v, TT::rs[pos]);
}
pushup(rt, pos);
}
/**
* @brief 二维矩形更新：矩形 [a,b] 执行取max(v)
*/
inline void update(unsigned a, unsigned b, unsigned v, unsigned &rt, unsigned pos = TT::rt) {
using TT::A, TT::B, TT::R;
if (!rt)
rt = newnode(pos);
if (A[pos] == a && B[pos] == b)
return beats(rt, v, pos);
pushdown(rt, pos)null
这里空空如也
有帮助，赞一个