2026 杭电春季联赛 4——1009-GCD（这种数论的题目，与其想办法批量处理多个询问，不如想办法加快单个查询的速率）

Posted on 2026-04-14 Edited on 2026-04-16

题目大意

题目描述
给定两个长度为 $n$ 的整数数组 $a$ 和 $b$ 。
有 $q$ 次询问，每次询问给定一个区间 $[l, r]$ ，提取出子数组 $a' = a[l \dots r]$ 和 $b' = b[l \dots r]$ ，设该子数组长度为 $m = r - l + 1$ 。
对于每次询问中的子数组，可以执行以下操作任意次：

选取一个下标 $i$ （ $1 \le i \le m$ ）。
计算子数组后缀的最大公约数 $g_i = \gcd(a'i, a'{i+1}, \dots, a'_m)$ 。
将 $b'$ 中下标从 $i$ 到 $m$ 的所有元素减去 $g_i$ （即对于所有 $i \le j \le m$ ，令 $b'_j \leftarrow b'_j - g_i$ ）。

每次操作的代价为 1。要求计算出使 $b'$ 中所有元素变为非正数（ $\le 0$ ）所需的最小总操作代价。

数据范围

测试组数 $T$ ： $1 \le T \le 10^5$
数组长度与询问次数 $n, q$ ： $1 \le n, q \le 2 \cdot 10^5$
数组元素范围： $1 \le a_i \le 10^9$ ， $0 \le b_i \le 10^9$
保证 $\sum n \le 10^6$ ， $\sum q \le 10^6$

样例数据

输入

1
10 10
6 12 18 40 50 60 105 120 135 150
10 20 30 40 50 60 70 80 90 100
5 8
1 3
7 10
6 6
4 7
1 6
2 10
2 4
4 4
5 6

输出

样例解释
以第 2 次询问 1 3 为例：
提取出的子数组为 $a' = [6, 12, 18]$ ， $b' = [10, 20, 30]$ 。
一种可能的最优操作序列如下（共需 5 次操作，代价为 5）：

选取 $i = 1$ 操作 2 次： $g_1 = \gcd(6, 12, 18) = 6$ ，每次操作使 $b'_1, b'_2, b'_3$ 减去 6。操作后 $b'$ 变为 $[-2, 8, 18]$ 。
选取 $i = 2$ 操作 2 次： $g_2 = \gcd(12, 18) = 6$ ，每次操作使 $b'_2, b'_3$ 减去 6。操作后 $b'$ 变为 $[-2, -4, 6]$ 。
选取 $i = 3$ 操作 1 次： $g_3 = \gcd(18) = 18$ ，每次操作使 $b'_3$ 减去 18。操作后 $b'$ 变为 $[-2, -4, -12]$ 。
此时 $b'$ 中所有元素均不大于 0，所需最小总代价为 $2 + 2 + 1 = 5$ ，与输出一致。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{tocloft} % 支持目录引导点
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning, decorations.pathreplacing}

% 与原先 listings 外观大致对齐；
\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

% --- 目录样式修改 ---
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}} % 让 section 也有点点
% ------------------

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref} % 添加超链接和PDF书签支持

\definecolor{gcdc}{RGB}{50,120,200}   % 蓝色 — GCD 块
\definecolor{maxc}{RGB}{220,80,60}    % 红色 — 最大值
\definecolor{accc}{RGB}{0,160,80}     % 绿色 — 累加器
\definecolor{blockbg}{RGB}{230,240,255} % 淡蓝色 — 块背景

\title{1009 GCD 题解}
\author{Gospel\_rock}
\date{}

\begin{document}
\maketitle

\section{题意}

给定两个长度为 $n$ 的整数数组 $a$ 和 $b$。$q$ 次询问，每次给出区间 $[l, r]$，取出子数组 $a' = a[l \dots r]$，$b' = b[l \dots r]$（长度 $m = r - l + 1$）。

每次操作可以选取下标 $i$（$1 \le i \le m$），计算后缀 GCD $g_i = \gcd(a'_i, a'_{i+1}, \ldots, a'_m)$，然后将 $b'_j$ 减去 $g_i$（对所有 $i \le j \le m$）。每次操作代价为 $1$。求使 $b'$ 所有元素 $\le 0$ 的最小总代价。

\section{贪心策略}

\subsection{关键观察：后缀 GCD 的单调性}

后缀 GCD 满足 $g_1 \mid g_2 \mid \cdots \mid g_m$，因此 $g_1 \le g_2 \le \cdots \le g_m$。这意味着越靠右的位置，单次操作的减法力度越大。

\subsection{贪心方案}

从左到右扫描位置 $k = 1, 2, \ldots, m$，维护一个累积减量 $S$（初始 $S = 0$）。$S$ 表示之前所有操作对位置 $k$ 产生的总减量。

\begin{quote}
若 $b'_k > S$，则在位置 $k$ 追加 $c = \left\lceil \dfrac{b'_k - S}{g_k} \right\rceil$ 次操作，随后更新 $S \leftarrow S + c \cdot g_k$。
\end{quote}

\subsection{为什么在当前位置操作？}

当扫到位置 $k$ 时，如果 $b'_k > S$，说明之前的操作不够用，必须追加。追加操作可以在 $1$ 到 $k$ 的任何位置执行。但由于 $g_k \ge g_j$（$\forall\, j \le k$），在位置 $k$ 执行单次操作的减量最大。

同时，位置 $1$ 到 $k - 1$ 已经在之前的步骤中被满足了，所以我们不需要利用"更早位置能覆盖更多左侧元素"这一优势——那些左侧元素早已被处理完毕。

综合来看：在位置 $k$ 追加操作，既享受了最大的单次减量 $g_k$，又不浪费在已满足的左侧位置上。而且这些操作也会对 $k$ 之后的所有位置产生减量，为后续处理提供帮助。

\subsection{样例验证}

以询问 $[1, 3]$ 为例：$a' = [6, 12, 18]$，$b' = [10, 20, 30]$。

后缀 GCD：$g_1 = \gcd(6, 12, 18) = 6$，$g_2 = \gcd(12, 18) = 6$，$g_3 = 18$。

\begin{itemize}
	\item $k = 1$：$S = 0 < b'_1 = 10$。追加 $\lceil 10 / 6 \rceil = 2$ 次。$S \leftarrow 12$。代价 $= 2$。
	\item $k = 2$：$S = 12 < b'_2 = 20$。追加 $\lceil 8 / 6 \rceil = 2$ 次。$S \leftarrow 24$。代价 $= 4$。
	\item $k = 3$：$S = 24 < b'_3 = 30$。追加 $\lceil 6 / 18 \rceil = 1$ 次。$S \leftarrow 42$。代价 $= 5$。
\end{itemize}

总代价为 $5$，与样例吻合。

图~\ref{fig:greedy} 展示了上述过程。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Stealth, scale=1.1]
	% 位置标签
	\foreach \k/\gv/\bv in {1/6/10, 2/6/20, 3/18/30} {
		\node[font=\small, above] at (\k * 2.5, 2.7) {$k = \k$};
		\node[gcdc, font=\small] at (\k * 2.5, 2.2) {$g_{\k} = \gv$};
		\node[maxc, font=\small] at (\k * 2.5, 1.7) {$b'_{\k} = \bv$};
	}

	% S 的演变
	\draw[accc, very thick, -Stealth] (1.5, 0.8) -- (2.5, 0.8) node[midway, above, font=\scriptsize, accc] {$+2 \times 6$};
	\node[accc, font=\small] at (1.2, 0.8) {$S\!=\!0$};
	\draw[accc, very thick, -Stealth] (3.3, 0.8) -- (5.0, 0.8) node[midway, above, font=\scriptsize, accc] {$+2 \times 6$};
	\node[accc, font=\small] at (2.8, 0.4) {$S\!=\!12$};
	\draw[accc, very thick, -Stealth] (5.8, 0.8) -- (7.5, 0.8) node[midway, above, font=\scriptsize, accc] {$+1 \times 18$};
	\node[accc, font=\small] at (5.3, 0.4) {$S\!=\!24$};
	\node[accc, font=\small] at (7.8, 0.4) {$S\!=\!42$};

	% 代价
	\foreach \k/\c in {1/2, 2/2, 3/1} {
		\node[font=\small, fill=yellow!20, rounded corners, inner sep=2pt] at (\k * 2.5, 0) {代价 $+\c$};
	}
\end{tikzpicture}
\caption{询问 $[1, 3]$ 的贪心过程。$S$ 为累积减量（绿色），每一步在当前位置追加操作使 $S \ge b'_k$。}
\label{fig:greedy}
\end{figure}

\section{$O(nq)$ 暴力}

上述贪心直接实现即可得到 $O(nq)$ 的暴力解法。对每个查询 $[l, r]$，先从右向左计算后缀 GCD 数组，再从左到右扫描执行贪心：

\begin{minted}{cpp}
ll reply_to_query(ll l, ll r) {
	gcd_ls[r] = aGlo[r];
	for (int i = r - 1; i >= l; --i)
		gcd_ls[i] = __gcd(gcd_ls[i + 1], aGlo[i]);
	ll acc = 0, ans = 0;
	for (int i = l; i <= r; ++i) {
		if (acc >= bGlo[i]) continue;
		ll rem = bGlo[i] - acc;
		ll add = (rem + gcd_ls[i] - 1) / gcd_ls[i];
		acc += add * gcd_ls[i];
		ans += add;
	}
	return ans;
}
\end{minted}

这段代码的瓶颈在于：每次询问都要逐个扫描 $O(m)$ 个位置。能否加速单次查询？

\section{加速单次查询：后缀 GCD 分块}

暴力中，内层循环逐个扫描 $k = l, l+1, \ldots, r$，而每个位置的 $g_k$ 值可能不同。但仔细观察会发现，$g_k$ 的取值远没有 $O(m)$ 那么多——它最多只有 $O(\log V)$ 种。如果我们按 GCD 值相同的连续段（称为\textbf{块}）来处理，单次查询就只需遍历 $O(\log V)$ 个块，而非 $O(m)$ 个位置。

\subsection{为什么只有 $O(\log V)$ 个块？}

固定右端点 $r$，考虑后缀 GCD $g_k = \gcd(a_k, a_{k+1}, \ldots, a_r)$，其中 $k$ 从 $r$ 到 $1$。
\begin{itemize}
	\item $g_r = a_r$。
	\item $g_{k-1} = \gcd(a_{k-1}, g_k)$，因此 $g_{k-1} \mid g_k$。
	\item 若 $g_{k-1} \neq g_k$，则 $g_{k-1}$ 是 $g_k$ 的\textbf{真因子}，故 $g_{k-1} \le g_k / 2$。
\end{itemize}

从 $g_r \le V$ 出发，每次变化至少减半，最多减半 $\lfloor \log_2 V \rfloor$ 次就到 $1$。因此不同的 $g$ 值最多 $O(\log V)$ 个（$V = \max a_i$），它们构成连续的若干\textbf{块}。

注意这里的界来自"每次变化必须整除且至少减半"，与 $n$ 无关。即使所有 $a_i$ 互素，GCD 也会一步降到 $1$ 并不再变化，块数反而最少。

图~\ref{fig:blocks} 以 $a = [6, 12, 18, 40, 50]$（对应下标 $1 \sim 5$，右端点 $r = 5$）为例展示了分块结构。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Stealth, scale=1.0]
	% 位置
	\foreach \k in {1,...,5} {
		\node[font=\small, below] at (\k * 2.2, -0.3) {$k = \k$};
	}

	% 块的背景
	\fill[blockbg, rounded corners=3pt] (1*2.2 - 0.7, -0.1) rectangle (3*2.2 + 0.7, 0.7);
	\fill[blue!8, rounded corners=3pt] (4*2.2 - 0.7, -0.1) rectangle (4*2.2 + 0.7, 0.7);
	\fill[orange!12, rounded corners=3pt] (5*2.2 - 0.7, -0.1) rectangle (5*2.2 + 0.7, 0.7);

	% GCD 值
	\foreach \k/\gv in {1/2, 2/2, 3/2, 4/10, 5/50} {
		\node[font=\normalsize, gcdc, font=\bfseries] at (\k * 2.2, 0.3) {$\gv$};
	}

	% 块标注
	\draw[decorate, decoration={brace, amplitude=5pt, mirror}, thick]
		(1*2.2 - 0.6, -0.7) -- (3*2.2 + 0.6, -0.7)
		node[midway, below=6pt, font=\small] {块 1：$g = 2$};
	\draw[decorate, decoration={brace, amplitude=5pt, mirror}, thick]
		(4*2.2 - 0.6, -0.7) -- (4*2.2 + 0.6, -0.7)
		node[midway, below=6pt, font=\small] {块 2：$g = 10$};
	\draw[decorate, decoration={brace, amplitude=5pt, mirror}, thick]
		(5*2.2 - 0.6, -0.7) -- (5*2.2 + 0.6, -0.7)
		node[midway, below=6pt, font=\small] {块 3：$g = 50$};
\end{tikzpicture}
\caption{$a = [6, 12, 18, 40, 50]$，右端点 $r = 5$ 时后缀 GCD 的分块结构。5 个位置仅产生 3 个 GCD 块。}
\label{fig:blocks}
\end{figure}

\subsection{按块做贪心：单次查询 $O(\log V)$}

有了分块结构，我们重新审视暴力的内层循环。对同一个 GCD 块（值为 $g$，覆盖位置 $[lo, hi]$），$g$ 是定值，而累积减量 $S$ 单调递增。所以块内唯一能触发追加的是 $b'$ 的\textbf{最大值} $M$——追加 $\lceil (M - S) / g \rceil$ 次后 $S \ge M$，块内其余位置自然被满足。

因此，对一个块只需查询 $M = \max(b'_{lo}, \ldots, b'_{hi})$：若 $M \le S$ 则跳过；否则追加并更新 $S$。单次查询只遍历 $O(\log V)$ 个块，每个块 $O(1)$，总共 $O(\log V)$。

对比暴力代码，优化后的单次查询逻辑几乎一一对应：

\begin{minted}{cpp}
// 暴力：逐个位置扫描             // 优化：逐个 GCD 块扫描
for (int i = l; i <= r; ++i) {    for (auto &blk : blocks) {
                                      int lo = max(blk.lo, l);
                                      int hi = blk.hi;
                                      if (lo > hi) continue;
    if (acc >= bGlo[i]) continue;     ll mx = queryMax(lo, hi);
    ll rem = bGlo[i] - acc;           if (mx > acc) {
    ll add = (rem + gcd_ls[i] - 1)        ll c = (mx - acc + blk.g - 1)
             / gcd_ls[i];                         / blk.g;
    acc += add * gcd_ls[i];               acc += c * blk.g;
    ans += add;                           cost += c;
}                                     }
                                  }
\end{minted}

左边用 $b_k$ 判定，右边用块内 $\max b$ 判定；左边用 $g_k$，右边用块的统一 GCD 值。逻辑完全一致，只是粒度从单个位置变成了一整个块。

\subsection{$O(1)$ 区间最大值：ST 表}

按块做贪心需要快速查询任意区间 $[lo, hi]$ 内 $b$ 的最大值。对数组 $b$ 预处理一个 \textbf{ST 表}即可实现 $O(1)$ 查询：

\begin{minted}{cpp}
void buildST() {
	LOG = 1;
	while ((1 << LOG) <= N) LOG++;
	st.assign(LOG, vector<ll>(N + 1));
	for (int i = 1; i <= N; i++) st[0][i] = b[i];
	for (int j = 1; j < LOG; j++)
		for (int i = 1; i + (1 << j) - 1 <= N; i++)
			st[j][i] = max(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
}

ll queryMax(int l, int r) {
	int k = 31 - __builtin_clz(r - l + 1);
	return max(st[k][l], st[k][r - (1 << k) + 1]);
}
\end{minted}

\subsection{跨查询复用块列表}

至此，单次查询已经是 $O(\log V)$ 了，但还剩一个问题：对每个查询 $[l, r]$，我们需要拿到右端点为 $r$ 时的 GCD 块列表。如果每次都从头算，又退化回 $O(n)$。

注意到块列表中每个块的值是 $\gcd(a_k, \ldots, a_r)$。当右端点从 $r$ 扩展到 $r + 1$ 时，GCD 的结合律保证：
$$\gcd(a_k, \ldots, a_r, a_{r+1}) = \gcd(\underbrace{\gcd(a_k, \ldots, a_r)}_{\text{已有块的值}},\; a_{r+1})$$
每个已有块只需与 $a_{r+1}$ 做一次 $\gcd$，不用从头重算。而 $\gcd$ 操作只会让值不变或变小，块只会合并不会分裂，所以块数也不会增加（末尾追加的新块至多 $+1$）。

这意味着块列表对右端点具有\textbf{增量可维护性}：推进一步的代价仅为 $O(\log V)$。于是我们将所有询问离线，按右端点 $r$ 分组，从 $r = 1$ 到 $n$ 依次推进块列表，顺便回答所有以当前 $r$ 为右端点的查询。左端点 $l$ 的影响在查询时通过 \texttt{max(blk.lo, l)} 裁剪即可，无需块列表本身感知它。

\begin{minted}{cpp}
vector<Block> blocks;
for (int r = 1; r <= N; r++) {
	vector<Block> nb;
	for (auto &blk : blocks) {
		ll ng = __gcd(blk.g, a[r]);
		if (!nb.empty() && nb.back().g == ng)
			nb.back().hi = blk.hi;
		else
			nb.push_back({ng, blk.lo, blk.hi});
	}
	if (!nb.empty() && nb.back().g == a[r])
		nb.back().hi = r;
	else
		nb.push_back({a[r], r, r});
	blocks = move(nb);

	// 回答所有右端点为 r 的查询
	for (auto [l, id] : queries[r]) {
		ll acc = 0, cost = 0;
		for (auto &blk : blocks) {
			int lo = max(blk.lo, l);
			int hi = blk.hi;
			if (lo > hi) continue;
			ll mx = queryMax(lo, hi);
			if (mx > acc) {
				ll c = (mx - acc + blk.g - 1) / blk.g;
				cost += c;
				acc += c * blk.g;
			}
		}
		ans[id] = cost;
	}
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{ST 表预处理}：$O(n \log n)$。
	\item \textbf{扫描线维护 GCD 块}：每步更新 $O(\log V)$ 个块，总计 $O(n \log V)$。
	\item \textbf{回答查询}：每次查询遍历 $O(\log V)$ 个块，每块 $O(1)$ 查询区间最大值，总计 $O(q \log V)$。
	\item \textbf{总时间复杂度}：$O(n \log n + (n + q) \log V)$，其中 $V = \max a_i \le 10^9$，$\log V \approx 30$。
	\item \textbf{空间复杂度}：$O(n \log n)$（ST 表）。
\end{itemize}

\section{AC 代码}

\inputminted{cpp}{../src/1009_GCD.cpp}

\end{document}

PDF

我的错误思路（应该是加速单个查询速度，你想办法加速多个查询，其实是很难的，因为这种数论的东西，因为其下降速率很快，那么按照查询分块，就会产生非常多的块，非常不利于优化）

想出一个 $O(nq)$ 的做法是不难的，难的就是怎么样在 $O(n+q)$ 或者类似的时间复杂度内解决这个问题。
这个下面就是一个这样的做法：

struct Solve {
	ll N, Q;
	vector<ll> A_glo;
	vector<ll> B_glo;
	vector<ll> gcd_ls;

	ll reply_to_query(ll l, ll r) {
		gcd_ls[r] = A_glo[r];
		for (int i = r - 1; i >= l; --i) {
			gcd_ls[i] = __gcd(gcd_ls[i + 1], A_glo[i]);
		}
		ll acc = 0;
		ll ans = 0;
		for (int i = l; i <= r; ++i) {
			if (acc >= B_glo[i]) {
				continue;
			}
			ll rem = B_glo[i] - acc;
			ll add = (rem + gcd_ls[i] - 1) / gcd_ls[i];
			acc += add * gcd_ls[i];
			ans += add;
		}
		return ans;
	}

	Solve() {
		cin >> N >> Q;
		A_glo.resize(N + 2);
		B_glo.resize(N + 2);
		gcd_ls.resize(N + 2);
		for (int i = 1; i <= N; ++i) {
			cin >> A_glo[i];
		}
		for (int i = 1; i <= N; ++i) {
			cin >> B_glo[i];
		}
		for (int _ = 1; _ <= Q; _++) {
			ll l, r;
			cin >> l >> r;
			cout << reply_to_query(l, r) << "\n";
		}
	}
};

现在喜欢出这种题目，就是想个办法优化暴力方法，解决暴力的这个问题。
那么一般来说，解决一道题目，优化这个方法，一种思路就是继续深挖性质，不过并没有其他比较好的这个性质。
那么，另一种思路就是采用莫队式的方法，如何一次解决多个查询？如何一次遍历，批量解决一系列问题？

想出一个 $O(nq)$ 的做法是不难的，难的就是怎么样在 $O(n+q)$ 或者类似的时间复杂度内解决这个问题。

这个下面就是一个这样的做法：

struct Solve {
	ll N, Q;
	vector<ll> A_glo;
	vector<ll> B_glo;
	vector<ll> gcd_ls;

	ll reply_to_query(ll l, ll r) {
		gcd_ls[r] = A_glo[r];
		for (int i = r - 1; i >= l; --i) {
			gcd_ls[i] = __gcd(gcd_ls[i + 1], A_glo[i]);
		}
		ll acc = 0;
		ll ans = 0;
		for (int i = l; i <= r; ++i) {
			if (acc >= B_glo[i]) {
				continue;
			}
			ll rem = B_glo[i] - acc;
			ll add = (rem + gcd_ls[i] - 1) / gcd_ls[i];
			acc += add * gcd_ls[i];
			ans += add;
		}
		return ans;
	}

	Solve() {
		cin >> N >> Q;
		A_glo.resize(N + 2);
		B_glo.resize(N + 2);
		gcd_ls.resize(N + 2);
		for (int i = 1; i <= N; ++i) {
			cin >> A_glo[i];
		}
		for (int i = 1; i <= N; ++i) {
			cin >> B_glo[i];
		}
		for (int _ = 1; _ <= Q; _++) {
			ll l, r;
			cin >> l >> r;
			cout << reply_to_query(l, r) << "\n";
		}
	}
};

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1200&rid=15202

源代码

// teamname: Gospel_rock
/**
 * Problem: GCD
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1200&pid=1009
 * Created: 2026-04-14 11:18:13
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

/*
 *2025/12/10 AC https://codeforces.com/contest/2175/submission/352780861
 *2025/3/2 实现了这个 op 函数的传入（可以传入一个 lambda 函数）
 *AC https://codeforces.com/contest/2205/submission/365029208
 *
 */
template<class T, class F>
struct ST {
private:
	ll N;
	vector<vector<T> > dp;
	F op;
	// static T op(const T &a,const T &b) {
	//     return max(a,b);
	// }
public:
	ST(ll N, const vector<T> &a, F fun) : N(N), dp(__lg(N) + 1, vector<T>(N + 5)), op(fun) {
		for (int i = 1; i <= N; ++i) {
			dp[0][i] = a[i];
		}
		for (int lay = 1; lay <= __lg(N); ++lay) {
			for (int i = 1; i <= N - (1 << (lay - 1)); ++i) {
				dp[lay][i] = op(dp[lay - 1][i], dp[lay - 1][i + (1 << (lay - 1))]);
			}
		}
	}

	T query(ll l, ll r) {
		ll lay = __lg(r - l + 1);
		return op(dp[lay][l], dp[lay][r - (1 << lay) + 1]);
	}
};

struct MXop {
	ll operator()(ll a, ll b) const {
		return std::max(a, b);
	}
};

struct BlockInfo {
	ll l, r;
	ll gcd;
#ifdef LOCAL
	friend auto operator<<(ostream &os, const BlockInfo &o) {
		os << "{l:" << o.l << " r:" << o.r << " gcd:" << o.gcd << "}";
	}
#endif
};

struct LId {
	ll l, id;
};

struct Solve {
	ll N, Q;
	vector<ll> aGlo;
	vector<ll> bGlo;
	// vector<array<ll, 2> > queryLs;
	optional<ST<ll, MXop> > st_mx;
	vector<vector<LId> > rQuery;
	vector<BlockInfo> blocks;
	vector<BlockInfo> toBlocks;

	static bool cmp(const BlockInfo &a, ll v) {
		return a.r < v;
	}

	static bool check(const BlockInfo &a, const BlockInfo &b) {
		return a.gcd == b.gcd;
	}

	static BlockInfo merge(const BlockInfo &a, const BlockInfo &b) {
		BlockInfo res{a.l, b.r, __gcd(a.gcd, b.gcd)};
		return res;
	}

	void add_to_block(ll id, ll gcd) {
		toBlocks.clear();
		blocks.push_back({id, id, gcd});
		for (int i = 0; i < SZ(blocks); ++i) {
			blocks[i].gcd = __gcd(blocks[i].gcd, gcd);
			if (toBlocks.empty()) {
				toBlocks.push_back(blocks[i]);
			} else {
				if (check(toBlocks.back(), blocks[i])) {
					toBlocks.back() = merge(toBlocks.back(), blocks[i]);
				} else {
					toBlocks.push_back(blocks[i]);
				}
			}
		}
#ifdef LOCAL
		debug(id);
		debug(gcd);
		debug1d(blocks);
		debug1d(toBlocks)
#endif
		swap(toBlocks, blocks);
	}

	ll reply_query(ll lq, ll rq) {
		ll idxL = lower_bound(all(blocks), lq, cmp) - blocks.begin();
		ll idxR = lower_bound(all(blocks), rq, cmp) - blocks.begin();
#ifdef LOCAL
		debug(lq);
		debug(rq);
		debug(idxL);
		debug(idxR);
		debug1d(blocks);
#endif
		ll ans = 0;
		ll acc = 0;
		for (int i = idxL; i <= idxR; ++i) {
			auto [l,r,gcd] = blocks[i];
			l = max(l, lq);
			r = min(r, rq);
			ll mx = st_mx->query(l, r);
			if (acc >= mx) {
				continue;
			}
			ll rem = mx - acc;
			ll ceil = (rem + gcd - 1) / gcd;
			ans += ceil;
			ll add = ceil * gcd;
			acc += add;
		}
		return ans;
	}


	Solve() {
		cin >> N >> Q;
		aGlo.resize(N + 2);
		bGlo.resize(N + 2);
		rQuery.resize(N + 2);
		// queryLs.resize(Q);

		for (int i = 1; i <= N; ++i) {
			cin >> aGlo[i];
		}
		for (int i = 1; i <= N; ++i) {
			cin >> bGlo[i];
		}
		for (int i = 0; i < Q; ++i) {
			// cin >> queryLs[i][0] >> queryLs[i00][1];
			ll l, r;
			cin >> l >> r;
			rQuery[r].push_back({l, i});
		}
		st_mx.emplace(N, bGlo, MXop{});
		vector<ll> ans(Q);
		for (int r = 1; r <= N; ++r) {
			add_to_block(r, aGlo[r]);
			for (auto [l,id]: rQuery[r]) {
				ans[id] = reply_query(l, r);
			}
		}
		for (int i = 0; i < Q; ++i) {
			cout << ans[i] << "\n";
		}
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve solve;
	return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1200&rid=15202

*/

心路历程（WA，TLE，MLE……）

2026 杭电春季联赛 4——1002/1003-通行证（Easy Version/Hard Version）

Posted on 2026-04-14 Edited on 2026-04-15

题目大意

题目大意

给定一个 $n \times n$ 的方阵 $a$ ，其外围被一圈值为 $10^{100}$ 的元素包围，共同形成一个 $(n+2) \times (n+2)$ 的方阵。
每个元素代表一个人的识别码。对于给定的通行证 $card$ ，如果一个人的识别码 $x$ 满足 $x$ 按位或 $card \neq card$ （即 $x$ 的二进制表示中存在 $card$ 没有的 $1$ ），则该人被视为“坏蛋”。（由于外围一圈元素的值极大，它们一定会满足该条件被判定为坏蛋）。

每个人（包含坏蛋自身）的安全感定义为：从当前位置出发，沿上下左右四个直线方向寻找，距离其最近的坏蛋的距离。如果自身是坏蛋，则距离为 $0$ 。

现在有 $q$ 次询问，每次给定一个 $card$ ，求方阵 $a$ 中所有人的安全感之和。

数据范围

$1 \le T \le 10$
$1 \le n \le 300$
$1 \le q \le 5 \times 10^4$
$0 \le a_{i,j} < 2^{15}$
$0 \le card < 10^9$

样例输入

样例输出

样例解释

在样例中， $n=5$ ， $card = 1$ 。
由于坏蛋的条件是 $x$ 按位或 $1 \neq 1$ ，因此识别码为 $1$ 的是好人（用 G 表示），识别码为 $5$ 的是坏蛋（用 B 表示）。外围一圈全部是极大值，均为 B。方阵的状态如下：

B B B B B B B
B B B G B B B
B B B G B B B
B G G G G G B
B B B G B B B
B G B G B B B
B B B B B B B

我们可以计算每个好人位置上，在上下左右四个直线方向中，遇到最近的坏蛋的距离：

对于 $(1, 3)$ 的 G，向上一步即为外围的 B，距离为 $1$ 。
对于 $(2, 3)$ 的 G，向左一步为内部的 B，距离为 $1$ 。
对于第三行的四个 G（除了中心 $(3, 3)$ ）：
- $(3, 1)$ 向上一步为 B，距离为 $1$ 。
- $(3, 2)$ 向上一步为 B，距离为 $1$ 。
- $(3, 4)$ 向上一步为 B，距离为 $1$ 。
- $(3, 5)$ 向上一步为 B，距离为 $1$ 。
对于中心的 $(3, 3)$ ，它的上下左右连续两个位置都是 G，直到第三个位置才是外围或内部的 B，因此最近距离为 $3$ 。
对于 $(4, 3)$ 的 G，向左一步为内部的 B，距离为 $1$ 。
对于第五行的两个 G：
- $(5, 1)$ 向右一步为内部的 B，距离为 $1$ 。
- $(5, 3)$ 向左一步为内部的 B，距离为 $1$ 。

将所有好人的距离相加： $1 + 1 + 1 \times 4 + 3 + 1 + 1 \times 2 = 12$ 。坏蛋自身的最近距离为 $0$ ，因此安全感总和为 $12$ ，与样例输出一致。

思路讲解

AI 生成的 latex 题解代码

No content to show

AC代码

源代码

心路历程（WA，TLE，MLE……）

2026 杭电春季联赛 4——1005-列车停放站（倍增法+右端点贪心）

Posted on 2026-04-12 Edited on 2026-04-14

题目大意

题目描述
给定 $n$ 辆列车的停放区间 $[l, r]$ 。
有 $m$ 次询问，每次询问给出一个空区间 $[x, y]$ ，需要求出在该空区间内最多可以完整停放多少辆列车。
被选择停放的列车区间必须完全包含在询问区间 $[x, y]$ 内，且不同列车的停放区间在内部不能重叠，但端点可以相交（即列车之间可以紧贴，不留空隙）。

输入格式
第一行输入一个整数 $T$ （ $1 \le T \le 5$ ），表示测试数据组数。
对于每组数据：
第一行输入一个整数 $n$ （ $1 \le n \le 10^5$ ），表示列车数量。
接下来 $n$ 行，每行输入两个整数 $l, r$ （ $1 \le l < r \le 10^9$ ），表示一辆列车的停放区间为 $[l, r]$ 。
接下来一行输入一个整数 $m$ （ $1 \le m \le 10^5$ ），表示询问次数。
接下来 $m$ 行，每行输入两个整数 $x, y$ （ $1 \le x < y \le 10^9$ ），表示每次询问的空区间。

输出格式
对于每次询问，输出一行一个整数，表示最多可以在该区间内停放的列车数量。

样例数据

样例输入

样例输出

1
2

1
2

样例解释
在该样例中，共有 $3$ 辆列车，区间分别为 $[1, 3]$ 、 $[1, 4]$ 、 $[3, 4]$ 。

第一次询问区间 $[1, 3]$ ：只有第 $1$ 辆列车 $[1, 3]$ 能够完整停放在该区间内，因此最多停放 $1$ 辆列车。
第二次询问区间 $[1, 4]$ ：可以选择第 $1$ 辆列车 $[1, 3]$ 和第 $3$ 辆列车 $[3, 4]$ 。这两辆列车在端点 $3$ 处紧贴，且都完整包含在询问区间 $[1, 4]$ 内，不发生重叠，因此最多停放 $2$ 辆列车。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx} % Required for inserting images
\usepackage{amsmath} % bmatrix、cases、aligned 等数学环境
\usepackage{amssymb} % 数学符号宏包，支持 \mathbb 等
\usepackage{xeCJK} % 核心：添加这个宏包以支持中文
\usepackage{multicol} % 引入分栏宏包
\usepackage{tocloft} % 支持目录引导点
\usepackage{xcolor}   % 用于设置颜色；须先于 minted 以便 bgcolor 等生效
\usepackage[cachedir=_minted-main]{minted} % Pygments 高亮，需 -shell-escape + pygmentize
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}
\usepackage{tikz}
\usetikzlibrary{arrows.meta, positioning}

% 与原先 listings 外观大致对齐；
\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

% --- 目录样式修改 ---
\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}} % 让 section 也有点点
% ------------------

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref} % 添加超链接和PDF书签支持

\definecolor{selc}{RGB}{0,160,80}      % 绿色 — 选中的列车
\definecolor{rejc}{RGB}{180,180,180}   % 灰色 — 未选中的列车
\definecolor{queryc}{RGB}{50,120,200}  % 蓝色 — 查询区间
\definecolor{jumpc}{RGB}{220,80,60}    % 红色 — 跳跃箭头

\title{1005 列车停放站 题解}
\author{Gospel\_rock}
\date{}

\begin{document}
\maketitle

\section{题意}

给定 $n$ 辆列车的停放区间 $[l_i, r_i]$。$m$ 次询问，每次给出区间 $[x, y]$，求在 $[x, y]$ 内最多能停放多少辆列车。选中的列车区间必须完全包含在 $[x, y]$ 内，且互不重叠（端点可以相切）。

\section{贪心策略}

忽略多次询问，先考虑单次查询 $[x, y]$：从所有满足 $x \le l_i$ 且 $r_i \le y$ 的列车中，选出最多的互不重叠列车。这是经典的\textbf{区间调度最大化}问题，贪心策略为：

\begin{quote}
维护一个指针 $p$（初始 $p = x$）。每次从所有 $l_i \ge p$ 且 $r_i \le y$ 的列车中，选择\textbf{右端点 $r_i$ 最小}的那辆，然后令 $p \leftarrow r_i$，重复此过程直到无法再选。
\end{quote}

\textbf{为什么总是选右端点最小的？}
设有两辆可选列车 $A = [l_A, r_A]$ 和 $B = [l_B, r_B]$，其中 $r_A < r_B$。
选完 $A$ 后，剩余可用空间为 $[r_A, y]$；选完 $B$ 后，剩余空间为 $[r_B, y]$。
因为 $r_A < r_B$，前者严格包含后者，所以任何在 $[r_B, y]$ 中可行的后续方案，在 $[r_A, y]$ 中同样可行，反之不然。因此选 $A$ 一定不比选 $B$ 差。

图~\ref{fig:greedy} 以样例数据（查询 $[1, 4]$）演示了这一过程。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Stealth, scale=1.3]
	% 数轴
	\draw[->, thick] (0.5,0) -- (4.8,0) node[right, font=\small] {坐标};
	\foreach \x in {1,2,3,4} {
		\draw (\x, -0.08) -- (\x, 0.08);
		\node[below, font=\small] at (\x, -0.12) {$\x$};
	}

	% 查询区间
	\draw[queryc, line width=2pt] (1, -0.45) -- (4, -0.45);
	\fill[queryc] (1, -0.45) circle (2pt);
	\fill[queryc] (4, -0.45) circle (2pt);
	\node[queryc, font=\small] at (2.5, -0.8) {查询区间 $[1, 4]$};

	% 列车 [1,4] — 未选中
	\draw[rejc, line width=3.5pt, opacity=0.5] (1, 0.7) -- (4, 0.7);
	\node[rejc, font=\small, right] at (4.15, 0.7) {$[1,4]$};

	% 列车 [1,3] — 第 1 辆选中
	\draw[selc, line width=3.5pt] (1, 1.3) -- (3, 1.3);
	\fill[selc] (1, 1.3) circle (2pt);
	\fill[selc] (3, 1.3) circle (2pt);
	\node[selc, font=\small, right] at (4.15, 1.3) {$[1,3]$ \textbf{选}};

	% 列车 [3,4] — 第 2 辆选中
	\draw[selc, line width=3.5pt] (3, 1.9) -- (4, 1.9);
	\fill[selc] (3, 1.9) circle (2pt);
	\fill[selc] (4, 1.9) circle (2pt);
	\node[selc, font=\small, right] at (4.15, 1.9) {$[3,4]$ \textbf{选}};

	% 更新 p 的箭头
	\draw[->, jumpc, thick, dashed] (3, 1.1) -- (3, 1.7);
	\node[jumpc, font=\scriptsize, left] at (2.9, 1.4) {$p \leftarrow 3$};
\end{tikzpicture}
\caption{样例查询 $[1, 4]$ 的贪心过程。初始 $p=1$，先选右端点最小的 $[1,3]$，更新 $p=3$；再选 $[3,4]$，答案为 $2$。$[1,4]$ 因右端点更大而被 $[1,3]$ 取代。}
\label{fig:greedy}
\end{figure}

\section{从暴力到倍增}

\subsection{朴素贪心的瓶颈}

对单次查询，贪心过程需逐个选取列车，最多选 $O(n)$ 辆。面对 $m$ 次查询，总时间 $O(nm)$，在 $n, m \le 10^5$ 下不可接受。瓶颈在于：每次查询都要"一步步跳"。能否预处理后一次跳很多步？

\subsection{确定性的"下一步"与倍增}

贪心过程有一个关键性质：\textbf{下一步选哪辆列车，只取决于当前指针 $p$ 的位置}。$y$ 只决定何时停止跳跃，不影响每一步的选择方向。

因此我们可以把这个"下一步"预处理出来，进而用\textbf{倍增}加速。定义二维数组 $\texttt{nxt}[i][k]$：

\begin{quote}
$\texttt{nxt}[i][k]$：从离散化位置 $i$ 出发，贪心放入 $2^k$ 辆列车后，到达的右端点位置。
\end{quote}

基础层 $\texttt{nxt}[i][0]$ 即"从位置 $i$ 出发放 $1$ 辆列车到达的最小右端点"，递推层则将两个半步合并：
$$\texttt{nxt}[i][k] = \texttt{nxt}[\texttt{nxt}[i][k\!-\!1]][k\!-\!1]$$

含义直观：先跳 $2^{k-1}$ 辆到达中间位置，再从中间位置跳 $2^{k-1}$ 辆，合计 $2^k$ 辆。

图~\ref{fig:lifting} 以样例展示了倍增跳跃如何将两步合并为一步。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[>=Stealth]
	% 节点：离散化后的坐标值
	\node[circle, draw, thick, fill=white, minimum size=1cm] (n0) at (0, 0) {$1$};
	\node[circle, draw, thick, fill=white, minimum size=1cm] (n1) at (3.5, 0) {$3$};
	\node[circle, draw, thick, fill=white, minimum size=1cm] (n2) at (7, 0) {$4$};
	\node[circle, draw, thick, dashed, fill=gray!10, minimum size=1cm] (nV) at (10.5, 0) {$\infty$};

	\node[below=0.25cm, font=\scriptsize] at (n0.south) {idx $0$};
	\node[below=0.25cm, font=\scriptsize] at (n1.south) {idx $1$};
	\node[below=0.25cm, font=\scriptsize] at (n2.south) {idx $2$};
	\node[below=0.25cm, font=\scriptsize] at (nV.south) {idx $V$（哨兵）};

	% k=0 跳跃（实线绿色）
	\draw[->, thick, selc] (n0) to[bend left=25]
		node[above, font=\scriptsize] {$k\!=\!0$：选 $[1,3]$} (n1);
	\draw[->, thick, selc] (n1) to[bend left=25]
		node[above, font=\scriptsize] {$k\!=\!0$：选 $[3,4]$} (n2);
	\draw[->, thick, rejc] (n2) to[bend left=25]
		node[above, font=\scriptsize] {$k\!=\!0$：无列车} (nV);

	% k=1 跳跃（虚线红色）
	\draw[->, very thick, jumpc, dashed] (n0) to[bend left=50]
		node[above, font=\small] {$k\!=\!1$：\textbf{一步跳 $2$ 辆}} (n2);
\end{tikzpicture}
\caption{样例的倍增表。$k=0$ 层（绿色实线）为单步贪心跳跃；$k=1$ 层（红色虚线）将两步合并为一步。查询 $[1,4]$ 时直接用 $k=1$ 一步到位，得到答案 $2$。}
\label{fig:lifting}
\end{figure}

\section{实现}

\subsection{坐标离散化}

列车端点坐标范围高达 $10^9$，但不同端点值至多 $2n$ 个。代码中使用 \texttt{Compress\_} 模板完成离散化：收集所有列车的 $l_i, r_i$，排序去重后映射为连续索引。

\textbf{查询坐标不参与离散化}——通过 \texttt{projectLr} 方法将原始查询区间 $[x, y]$ 投影到离散化空间。\texttt{lower\_bound} 找到第一个 $\ge x$ 的位置，\texttt{upper\_bound} $- 1$ 找到最后一个 $\le y$ 的位置；若投影为空（\texttt{ok = false}），直接返回 $0$：

\begin{minted}{cpp}
ProjectResult projectLr(T l, T r) {
	int li = (int)(lower_bound(liLs.begin(), liLs.end(), l) - liLs.begin()) + shift;
	int ri = (int)(upper_bound(liLs.begin(), liLs.end(), r) - liLs.begin()) - 1 + shift;
	return {li <= ri, li, ri};
}
\end{minted}

\subsection{构建基础层 \texttt{dp\_mn\_r}}

$\texttt{dp\_mn\_r}[i]$ 表示所有左端点索引 $\ge i$ 的列车中，右端点索引的最小值。这就是贪心的"下一步"——从位置 $i$ 出发放 $1$ 辆列车能到达的最优位置。

构建方式：将离散化后的列车按左端点排序，对每个位置 $i$ 用二分查找定位该位置的所有列车，取右端点最小值，并从右向左维护后缀最小值：

\begin{minted}{cpp}
void gen_dp_l_mn_r() {
	dp_mn_r.resize(liSZ + 1, INF);
	auto lr = liLr;
	sort(all(lr));
	for (int i = liSZ - 1; i >= 0; --i) {
		ll bg = lower_bound(all(lr), array<int, 2>{i, 0}) - lr.begin();
		ll ed = lower_bound(all(lr), array<int, 2>{i, INF}) - lr.begin();
		dp_mn_r[i] = dp_mn_r[i + 1];
		for (int j = bg; j < ed; ++j) {
			dp_mn_r[i] = min(dp_mn_r[i], lr[j][1]);
		}
	}
}
\end{minted}

\subsection{构建倍增表 \texttt{nxt}}

基础层直接来自 \texttt{dp\_mn\_r}，递推层将两个半步合并：

\begin{minted}{cpp}
void gen_nxt() {
	nxt.resize(liSZ, vector<int>(lgSZ + 1, INF));
	for (int lay = 0; lay <= lgSZ; ++lay) {
		for (int i = 0; i < liSZ; ++i) {
			if (lay == 0) {
				nxt[i][lay] = dp_mn_r[i];
			} else {
				if (nxt[i][lay - 1] == INF) continue;
				nxt[i][lay] = nxt[nxt[i][lay - 1]][lay - 1];
			}
		}
	}
}
\end{minted}

\subsection{回答查询}

对每个查询 $[x, y]$，先用 \texttt{projectLr} 投影到离散化空间 $[l, r]$，然后从大到小枚举层级 $k$：若跳 $2^k$ 辆后不超过 $r$，则执行跳跃并累加答案：

\begin{minted}{cpp}
int reply_query(int bg, int ed) {
	auto [ok, l, r] = compress.projectLr(bg, ed);
	if (!ok) return 0;
	int cur = l;
	int res = 0;
	for (int lay = lgSZ; lay >= 0; --lay) {
		if (nxt[cur][lay] <= r) {
			cur = nxt[cur][lay];
			res += (1 << lay);
		}
	}
	return res;
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：离散化 $O(n \log n)$；\texttt{gen\_dp\_l\_mn\_r} 中排序 $O(n \log n)$，每个位置二分查找后遍历，均摊 $O(n \log n)$；倍增表构建 $O(V \cdot \log V)$（$V \le 2n$ 个位置）；每次查询 $O(\log V)$。单组数据总计 $O((n + m) \log n)$。
	\item \textbf{空间复杂度}：倍增表 $O(V \cdot \log V)$。
\end{itemize}

\section{AC 代码}

\inputminted{cpp}{../src/1005_upsolve_train.cpp}

\end{document}

PDF

2025 United Kingdom and Ireland Programming Contest (UKIEPC 2025) 2025 英国 ICPC——B. Brickwork（判断砖块是否重叠）（扫描线的本质就是遍历一个出一个）（维护一个当前生效的集合）（把二维的问题变为一维的问题来做）

这道题目只要维护一个不相交集合，判断相交即可，而我们这道题目还需整一个这个选择哪些列车摆进来的决策，还是有点难度的。

哈哈，其实这道题目反其道而行之，这道题目的做法是倍增！

说白了，就是我一次性不放一辆车，改为放好多辆车。

倍增表使用如下方法生成：

void gen_nxt() {
	nxt.resize(liSZ, vector<int>(lgSZ + 1, INF));
	// 我们可不可以，就是对于每一个位置，我们都能知道，他跳 1<<i 辆列车，可以跳到的 r 点
	for (int lay = 0; lay <= lgSZ; ++lay) {
		for (int i = 0; i < liSZ; ++i) {
			if (lay == 0) {
				nxt[i][lay] = dp_mn_r[i];
			} else {
				if (nxt[i][lay - 1] == INF) continue;
				nxt[i][lay] = nxt[nxt[i][lay - 1]][lay - 1];
			}
		}
	}
}

回答也使用这个倍增方法，直接搞出来：

int reply_query(int bg, int ed) {
	auto [ok,l,r] = compress.projectLr(bg, ed);
	if (!ok) return 0;
	int cur = l;
	int res = 0;
	for (int lay = lgSZ; lay >= 0; --lay) {
		if (nxt[cur][lay] <= r) {
			cur = nxt[cur][lay];
			res += (1 << lay);
		}
	}
	return res;
}

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1200&rid=14607

源代码

// teamname: Gospel_rock
/**
 * Problem: 列车停放站
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1200&pid=1005
 * Created: 2026-04-12 15:26:47
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10;
const int INF = (ll) 1e9 + 7;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

/* 参考了 https://github.com/hh2048/XCPC/blob/484e9e0e6e4f127f187eb3df5bc419e9ec863795/02%20-%20%E6%89%93%E5%8D%B0%E7%A8%BF%E6%A8%A1%E6%9D%BF%E6%B1%87%E6%80%BB/08%20-%20%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84.md#L737
 *
 */
template<typename T>
struct Compress_ {
	// shift=0 就是采用 0-based 下标
	// shift=1 就是采用 1-based 下标
	int n, shift = 0;
	vector<T> liLs;

	Compress_() {
	}

	// 预估大小
	Compress_(ll n_) {
		liLs.reserve(n_);
	}

	Compress_(vector<T> in) : liLs(in) {
		init();
	}

	void add(T x) {
		liLs.emplace_back(x);
	}

	template<typename... Args>
	void add(T x, Args... args) {
		add(x), add(args...);
	}

	void init() {
		liLs.emplace_back(numeric_limits<T>::max());
		sort(liLs.begin(), liLs.end());
		liLs.resize(unique(liLs.begin(), liLs.end()) - liLs.begin());
		this->n = liLs.size();
	}

	int size() {
		return n;
	}

	int get_i(T x) {
		// 返回 x 元素的新下标
		return lower_bound(liLs.begin(), liLs.end(), x) - liLs.begin() + shift;
	}

	struct ProjectResult {
		bool ok;
		int l, r;
	};

	ProjectResult projectLr(T l, T r) {
		// 将区间 [l, r] 投影到离散化空间
		// li: 第一个 >= l 的离散化位置
		// ri: 最后一个 <= r 的离散化位置
		int li = (int) (lower_bound(liLs.begin(), liLs.end(), l) - liLs.begin()) + shift;
		int ri = (int) (upper_bound(liLs.begin(), liLs.end(), r) - liLs.begin()) - 1 + shift;
		return {li <= ri, li, ri};
	}

	T operator[](int idx) {
		// 根据新下标返回原来元素
		assert(idx - shift < n);
		return idx - shift < n ? liLs[idx - shift] : -1;
	}

	bool contains(T x) {
		// 查找元素 x 是否存在
		return binary_search(liLs.begin(), liLs.end(), x);
	}

	void reserve(ll n_) {
		liLs.reserve(n_);
	}

	friend auto &operator<<(ostream &o, const auto &j) {
		cout << "{";
		for (auto it: j.alls) {
			o << it << " ";
		}
		return o << "}";
	}
};

bool cmp(const array<ll, 2> &a, const array<ll, 2> &b) {
	if (a[1] != b[1]) return a[1] < b[1];
	return a[0] < b[0];
}

struct Solve {
	int N;
	int M;
	vector<array<int, 2> > lrLs;
	vector<array<int, 2> > liLr;
	vector<array<int, 2> > queryLs;
	Compress_<int> compress;
	vector<vector<int> > nxt;
	vector<int> dp_mn_r;
	int liSZ, lgSZ;


	void gen_dp_l_mn_r() {
		// 我们这里是要求每个 l 所能搞到的最小 r
		dp_mn_r.resize(liSZ + 1, INF);
		auto lr = liLr;
		sort(all(lr));
		for (int i = liSZ - 1; i >= 0; --i) {
			ll bg = lower_bound(all(lr), array<int, 2>{i, 0}) - lr.begin();
			ll ed = lower_bound(all(lr), array<int, 2>{i, INF}) - lr.begin();
			dp_mn_r[i] = dp_mn_r[i + 1];
			for (int j = bg; j < ed; ++j) {
				dp_mn_r[i] = min(dp_mn_r[i], lr[j][1]);
			}
		}
#ifdef LOCAL
		debug1d(dp_mn_r);
#endif
	}

	void gen_nxt() {
		nxt.resize(liSZ, vector<int>(lgSZ + 1, INF));
		// 我们可不可以，就是对于每一个位置，我们都能知道，他跳 1<<i 辆列车，可以跳到的 r 点
		for (int lay = 0; lay <= lgSZ; ++lay) {
			for (int i = 0; i < liSZ; ++i) {
				if (lay == 0) {
					nxt[i][lay] = dp_mn_r[i];
				} else {
					if (nxt[i][lay - 1] == INF) continue;
					nxt[i][lay] = nxt[nxt[i][lay - 1]][lay - 1];
#ifdef LOCAL
					if (i == 0 || i == 1) {
						debug(i);
						debug(nxt[i][lay - 1]);
						cend;
					}
#endif
				}
			}
		}
#ifdef LOCAL
		debug2d(nxt);
#endif
	}

	int reply_query(int bg, int ed) {
		auto [ok,l,r] = compress.projectLr(bg, ed);
		if (!ok) return 0;
		int cur = l;
		int res = 0;
		for (int lay = lgSZ; lay >= 0; --lay) {
			if (nxt[cur][lay] <= r) {
				cur = nxt[cur][lay];
				res += (1 << lay);
			}
		}
		return res;
	}

	Solve() {
		cin >> N;
		lrLs.resize(N);
		compress.reserve(2 * (N + M));

		for (int i = 0; i < N; ++i) {
			cin >> lrLs[i][0] >> lrLs[i][1];
			compress.add(lrLs[i][0], lrLs[i][1]);
		}
		cin >> M;
		queryLs.resize(M);
		for (int i = 0; i < M; ++i) {
			cin >> queryLs[i][0] >> queryLs[i][1];
			// compress.add(queryLs[i][0], queryLs[i][1]);
		}
		compress.init();
		liSZ = compress.size(), lgSZ = __lg(compress.size());
		liLr.reserve(N);
		for (auto [l,r]: lrLs) {
			// auto [ok,bg,ed] = compress.projectLr(l, r);
			// if (ok) liLr.push_back({bg, ed});
			liLr.push_back({compress.get_i(l), compress.get_i(r)});
		}
		gen_dp_l_mn_r();
		gen_nxt();
		for (auto [l,r]: queryLs) {
			cout << reply_query(l, r) << "\n";
		}
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve solve;
	return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1200&rid=14607

*/

心路历程（WA，TLE，MLE……）

P16231 [蓝桥杯 2026 省 A] 基因研究

Posted on 2026-04-12

题目大意

P16231 [蓝桥杯 2026 省 A] 基因研究

题目描述

DNA 分子的四种碱基分别记为 A、T、G、C。每个人的基因序列都可以认为是一个由 A、T、G、C 四种字符组成的长度为 $n$ 的字符串。

小蓝正在研究一种疾病。他观察到，这种疾病存在一个固定的易感序列（也可认为是一个由 A、T、G、C 构成的字符串）。若某人的基因序列中存在一个子串恰好等于这个易感序列，则称此人“易感”；若基因序列的任意子串都不等于这个易感序列，则称此人“不易感”。

小蓝希望根据这座城市中人们的基因序列情况，估计出城里“易感”人群所占的比例。

然而，直接获取整座城市中每个人完整的基因序列非常困难。为此，小蓝采用了抽样统计的方法：通过大量采样，他估计出了在这座城市中，每一个位置上碱基为 A、T、G、C 的人数占比。我们可以将其理解为：在所有人的基因序列中，第 $i$ 个位置为 A、T、G、C 的人数占比分别是多少。

为了简化模型，小蓝作出如下假设：对于任意一个人，其基因序列在每个位置上的碱基分布与采样结果完全一致，且不同位置之间的碱基相互独立。也就是说，即使已经确定了若干个位置上的碱基，剩余位置上的碱基仍然按照对应位置的分布独立生成。

现在，小蓝决定将这些概率以模 $998244353$ 的形式算出：如果“易感”人群所占比例为 $\frac{p}{q}$ ，则小蓝希望得到一个整数 $x$ ，满足 $x \times q \equiv p \pmod{998244353}$ 。请你根据给定的易感序列，以及每个位置上四种碱基的概率分布，帮小蓝计算并输出这个整数 $x$ 。

输入格式

第一行包含两个正整数 $n, m$ ，分别表示基因序列长度和易感序列长度。

第二行包含一个长度为 $m$ 的字符串 $s$ ，仅由 A、T、G、C 构成，表示疾病对应的易感序列。

接下来 $n$ 行，每行包含四个非负整数 $a_i, t_i, g_i, c_i$ 。其中：

$a_i$ 表示第 $i$ 个位置碱基为 A 的概率（模 $998244353$ 意义下）；
$t_i$ 表示第 $i$ 个位置碱基为 T 的概率（模 $998244353$ 意义下）；
$g_i$ 表示第 $i$ 个位置碱基为 G 的概率（模 $998244353$ 意义下）；
$c_i$ 表示第 $i$ 个位置碱基为 C 的概率（模 $998244353$ 意义下）。

保证对任意 $i$ ，均有 $(a_i + t_i + g_i + c_i) \bmod 998244353 = 1$ 。

输出格式

输出一行，包含一个非负整数，表示“基因序列中包含易感序列作为子串”的人群占比在模 $998244353$ 意义下的结果。

输入输出样例 #1

输入 #1

3 2
AA
499122177 499122177 0 0
499122177 0 499122177 0
499122177 0 0 499122177

输出 #1

623902721

说明/提示

【样例说明】

基因序列共有 $3$ 个位置：

第 $1$ 位有 $\frac{1}{2}$ 的概率是 $A$ ，有 $\frac{1}{2}$ 的概率是 $T$ ；
第 $2$ 位有 $\frac{1}{2}$ 的概率是 $A$ ，有 $\frac{1}{2}$ 的概率是 $G$ ；
第 $3$ 位有 $\frac{1}{2}$ 的概率是 $A$ ，有 $\frac{1}{2}$ 的概率是 $C$ 。

易感序列为 $AA$ 。因此，一个人被视为“易感”，当且仅当其基因序列中包含子串 $AA$ 。

所有可能产生的基因序列中，满足条件的共有 3 种，分别是 $AAC$ 、 $TAA$ 和 $AAA$ 。这 3 种序列出现的概率均为 $\frac{1}{8}$ ，因此“易感”人群所占的总比例为 $\frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{3}{8}$ ，其在模 $998244353$ 意义下的结果为 $623902721$ 。

【评测用例规模与约定】

对于 $30\%$ 的数据， $1 \le m \le n \le 5$ ；

另存在 $20\%$ 的数据， $a_i = t_i = g_i = c_i$ ；

对于 $100\%$ 的数据， $1 \le m \le n \le 3000, 0 \le a_i, t_i, g_i, c_i < 998244353$ 。

思路讲解

AI 生成的 latex 题解代码

No content to show

AC代码

源代码

心路历程（WA，TLE，MLE……）

P16230 [蓝桥杯 2026 省 A] 综合应变指标（把绝对值变为分类讨论，去掉绝对值，然后我们会发现好处理很多）

Posted on 2026-04-12

题目大意

P16230 [蓝桥杯 2026 省 A] 综合应变指标

题目描述

航空引擎涡轮叶片是确保国家空天安全的核心装备，其制造工艺代表了工业技术的巅峰。

这天，在精密检测实验室的中央，首席结构分析师小蓝正利用高精度传感器，沿涡轮叶片的中轴线进行连续扫描。扫描产生的反馈数据被转化为一条包含 $N$ 个元素的序列 $A = (A_1, A_2, \dots, A_N)$ 。

为了评估叶片在极限运行负载下的稳定性，小蓝需要针对这组序列计算出一个综合应变指标。计算该指标的第一步是选定三个分割点 $i, j, k$ （满足 $1 \le i < j < k < N$ ），将整条序列划分为以下四个连续且非空的子段：

第一段： $A_1, \dots, A_i$ ；
第二段： $A_{i+1}, \dots, A_j$ ；
第三段： $A_{j+1}, \dots, A_k$ ；
第四段： $A_{k+1}, \dots, A_N$ 。

第二步，需要计算每一个子段内所有数值的总和，并取其绝对值。这四个绝对值的累加总和被定义为该划分方案下的综合应变指标：

|A_1 + \cdots + A_i| + |A_{i+1} + \cdots + A_j| + |A_{j+1} + \cdots + A_k| + |A_{k+1} + \cdots + A_N|

分割点的选择有多种可能，不同的方案会导致不同的指标结果。

现在，请你帮助小蓝找出一种划分方案，使得得到的综合应变指标的数值最大。

输入格式

第一行包含一个正整数 $N$ ，表示扫描序列采集到的反馈节点总数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ，表示序列的元素。

输出格式

输出一行一个整数，表示序列所能达到的最大综合应变指标。

输入输出样例 #1

输入 #1

1 2	5 1 -1 -2 3 5

输出 #1

说明/提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $4 \le N \le 100$ ；

对于 $60\%$ 的评测用例， $4 \le N \le 400$ ；

对于所有评测用例， $4 \le N \le 10^5$ ， $-10^9 \le A_i \le 10^9$ 。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing, arrows.meta}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

% --- TikZ 颜色定义 ---
\definecolor{seg1}{RGB}{50,120,200}     % 蓝色 — 第一段
\definecolor{seg2}{RGB}{220,80,60}      % 红色 — 第二段
\definecolor{seg3}{RGB}{0,160,80}       % 绿色 — 第三段
\definecolor{seg4}{RGB}{140,80,200}     % 紫色 — 第四段
\definecolor{highlight}{RGB}{255,160,0} % 橙色 — 高亮

\title{\textbf{P16230 [蓝桥杯 2026 省 A] 综合应变指标} \\ 题解}
\author{}
\date{}

\begin{document}
\maketitle

\section{题意概述}

给定长度为 $N$ 的整数序列 $A$，选取三个分割点 $i, j, k$（满足 $1 \le i < j < k < N$）将序列划分为四个非空连续子段，最大化四段元素和的绝对值之和：
$$|A_1 + \cdots + A_i| + |A_{i+1} + \cdots + A_j| + |A_{j+1} + \cdots + A_k| + |A_{k+1} + \cdots + A_N|$$

\section{第一层思考：前缀和改写目标函数}

定义前缀和 $P_m = \sum_{t=1}^{m} A_t$（$P_0 = 0$）。四段的元素和分别为 $P_i$、$P_j - P_i$、$P_k - P_j$、$P_N - P_k$。目标函数改写为：
$$f(i, j, k) = |P_i| + |P_j - P_i| + |P_k - P_j| + |P_N - P_k|$$

这一步把"子段求和"全部消解成了前缀和之差的绝对值，后续只需操作 $P$ 数组。

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.75, every node/.style={font=\small}]
	% 序列格子
	\foreach \idx in {1,...,10} {
		\fill[gray!12] (\idx-0.45, -0.4) rectangle (\idx+0.45, 0.4);
		\draw[gray!50] (\idx-0.45, -0.4) rectangle (\idx+0.45, 0.4);
		\node at (\idx, 0) {$A_{\idx}$};
	}

	% 四段着色（底部色条）
	\draw[seg1, line width=3pt] (0.45, -0.65) -- (3.55, -0.65);
	\node[seg1, font=\bfseries] at (2, -1.15) {第 1 段};
	\node[seg1] at (2, -1.65) {和 $= P_i$};

	\draw[seg2, line width=3pt] (3.55, -0.65) -- (6.55, -0.65);
	\node[seg2, font=\bfseries] at (5, -1.15) {第 2 段};
	\node[seg2] at (5, -1.65) {和 $= P_j - P_i$};

	\draw[seg3, line width=3pt] (6.55, -0.65) -- (8.55, -0.65);
	\node[seg3, font=\bfseries] at (7.5, -1.15) {第 3 段};
	\node[seg3] at (7.5, -1.65) {和 $= P_k - P_j$};

	\draw[seg4, line width=3pt] (8.55, -0.65) -- (10.55, -0.65);
	\node[seg4, font=\bfseries] at (9.5, -1.15) {第 4 段};
	\node[seg4] at (9.5, -1.65) {和 $= P_N - P_k$};

	% 分割点标注
	\draw[thick, dashed] (3.55, 0.6) -- (3.55, -0.55);
	\node[above] at (3.55, 0.6) {$i$};
	\draw[thick, dashed] (6.55, 0.6) -- (6.55, -0.55);
	\node[above] at (6.55, 0.6) {$j$};
	\draw[thick, dashed] (8.55, 0.6) -- (8.55, -0.55);
	\node[above] at (8.55, 0.6) {$k$};
\end{tikzpicture}
\caption{%
	将序列 $A$ 在分割点 $i, j, k$ 处划分为四段。每段的元素和均可用前缀和 $P$ 简洁表示。%
}
\label{fig:partition}
\end{figure}

直接枚举三个分割点的时间复杂度为 $O(N^3)$，对 $N = 10^5$ 不可接受。能否把三重循环逐层拆解，每层都只做线性扫描？

\section{第二层思考：$O(N^2)$ 的朴素代码}

问题本身就是分段的，自然地逐段转移。定义四层 DP：\texttt{dp1[i]} 表示只切出第一段、该段以位置 $i$ 结尾时的最大贡献；\texttt{dp2[i]} 表示前两段的最大贡献，第二段以 $i$ 结尾；\texttt{dp3}、\texttt{dp4} 同理。答案为 \texttt{dp4[N]}。

第一层直接算：

\begin{minted}{cpp}
dp1[i] = abs(preA[i]);
\end{minted}

从 \texttt{dp1} 到 \texttt{dp2}、从 \texttt{dp2} 到 \texttt{dp3}、从 \texttt{dp3} 到 \texttt{dp4}，转移结构完全一样，写成一个通用函数：

\begin{minted}{cpp}
void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {                   // ← 内层循环
			dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
		}
	}
}
\end{minted}

调用三次 \texttt{excute\_dp}，每次 $O(N^2)$。瓶颈就在内层 \texttt{for(j)} 循环——能不能干掉它？

\section{第三层思考：干掉内层循环}

盯着内层循环体看：

\begin{minted}{cpp}
dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
\end{minted}

\texttt{abs} 只有两种展开。代入后，把只跟 \texttt{j} 有关的项括起来：

\begin{minted}{cpp}
dp1[j] + preA[i] - preA[j]  =  (dp1[j] - preA[j]) + preA[i]
//                               ^^^^^^^^^^^^^^^^^^    ^^^^^^^^
//                               只跟 j 有关            只跟 i 有关

dp1[j] + preA[j] - preA[i]  =  (dp1[j] + preA[j]) - preA[i]
//                               ^^^^^^^^^^^^^^^^^^    ^^^^^^^^
//                               只跟 j 有关            只跟 i 有关
\end{minted}

所以内层循环等价于：

\begin{minted}{cpp}
dp2[i] = max(
	max_over_j(dp1[j] - preA[j]) + preA[i],
	max_over_j(dp1[j] + preA[j]) - preA[i]
);
\end{minted}

\texttt{max\_over\_j(dp1[j] - preA[j])} 和 \texttt{max\_over\_j(dp1[j] + preA[j])} 不依赖 \texttt{i}！而且随着 \texttt{i} 递增，\texttt{j} 的候选范围只增不减（$j \le i$）。用两个变量滚动维护前缀最大值就行了，内层循环彻底消失：

\begin{minted}{cpp}
void excute_dp(const vector<ll> &from, vector<ll> &to) {
	ll Mplus = -INF, Mminus = -INF;
	for (int i = 1; i <= N; ++i) {
		Mplus  = max(Mplus,  from[i] + preA[i]);   // 维护 max(dp1[j]+preA[j])
		Mminus = max(Mminus, from[i] - preA[i]);   // 维护 max(dp1[j]-preA[j])
		to[i]  = max(Mminus + preA[i], Mplus - preA[i]);
	}
}
\end{minted}

双重循环 $\to$ 单层循环，$O(N^2) \to O(N)$。调用三次，总计 $O(N)$。

\subsection{图像理解}

上面的优化可以用图~\ref{fig:v-shape} 直观看懂。

对每个候选 \texttt{j}，\texttt{dp1[j] + abs(preA[i] - preA[j])} 是关于 \texttt{preA[i]} 的一条 V 形曲线——谷底在 \texttt{preA[j]}，谷底高 \texttt{dp1[j]}，两臂斜率 $\pm 1$。内层循环就是对所有 V 形取最大值（上包络）。

关键：所有 V 形的斜率全一样（$\pm 1$），不同的只是截距。同斜率的平行线取最大值，只有截距最大的一条存活。所以上包络只由两条直线决定——截距就是代码里的 \texttt{Mminus} 和 \texttt{Mplus}。

\texttt{i} 每递增一步，候选集多出一条新 V 形。新 V 形的截距和当前 \texttt{Mminus}、\texttt{Mplus} 取一次 \texttt{max} 就完成更新——这就是循环体里那两行 \texttt{max} 在干的事。

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.85, every node/.style={font=\small}]
	\begin{scope}
	\clip (-0.5, -0.5) rectangle (8.2, 7.5);

	% 被淘汰的臂（灰色虚线）
	\draw[gray!40, line width=0.5pt, densely dashed] (0, 4) -- (2, 2);
	\draw[gray!40, line width=0.5pt, densely dashed] (0, 5.5) -- (4, 1.5) -- (7.5, 5);
	\draw[gray!40, line width=0.5pt, densely dashed] (6, 1) -- (8, 3);

	% 存活的冠军臂（粗实线）
	\draw[seg1, line width=2.5pt] (2, 2) -- (7.5, 7.5);
	\draw[seg3, line width=2.5pt] (0, 7) -- (6, 1);

	% 上包络（橙色）
	\draw[highlight, line width=3.5pt, opacity=0.45] (0, 7) -- (3.5, 3.5) -- (7.5, 7.5);
	\end{scope}

	% V 形谷底
	\fill[seg1] (2, 2) circle (3pt);
	\fill[seg2] (4, 1.5) circle (3pt);
	\fill[seg3] (6, 1) circle (3pt);
	\fill[highlight!80!black] (3.5, 3.5) circle (3pt);

	% 谷底到 y 轴的水平虚线
	\draw[seg1!40, densely dotted, thin] (0, 2) -- (2, 2);
	\draw[seg2!40, densely dotted, thin] (0, 1.5) -- (4, 1.5);
	\draw[seg3!40, densely dotted, thin] (0, 1) -- (6, 1);

	% 坐标轴
	\draw[-stealth, thick] (-0.5, 0) -- (8.2, 0) node[right] {\texttt{preA[i]}};
	\draw[-stealth, thick] (0, -0.5) -- (0, 7.8);

	% preA[j] 刻度
	\foreach \x/\col/\lab in {2/seg1/1, 4/seg2/2, 6/seg3/3} {
		\draw[\col] (\x, -0.08) -- (\x, 0.08);
		\node[\col, below, font=\footnotesize] at (\x, -0.2) {\texttt{preA[$j_\lab$]}};
	}

	% y 轴谷底值标注
	\node[seg1, left, font=\footnotesize] at (-0.15, 2) {\texttt{dp1[$j_1$]}};
	\node[seg2, left, font=\footnotesize] at (-0.15, 1.5) {\texttt{dp1[$j_2$]}};
	\node[seg3, left, font=\footnotesize] at (-0.15, 1) {\texttt{dp1[$j_3$]}};

	% 冠军臂箭头标注
	\draw[-stealth, seg1!80!black, thick] (7.2, 5.5) -- (6.2, 6.2);
	\node[seg1!80!black, font=\footnotesize, align=left, right] at (7.2, 5.0)
		{斜率 $+1$ 冠军\\[-1pt] 截距 $=$ \texttt{Mminus}};

	\draw[-stealth, seg3!80!black, thick] (0.6, 7.5) -- (1.2, 5.8);
	\node[seg3!80!black, font=\footnotesize, align=left, right] at (0.6, 7.7)
		{斜率 $-1$ 冠军，截距 $=$ \texttt{Mplus}};

	% 图例
	\draw[gray!40, line width=0.5pt, densely dashed] (4.5, -1.2) -- (5.3, -1.2);
	\node[gray!60, font=\footnotesize, right] at (5.4, -1.2) {被淘汰的臂};
	\draw[highlight, line width=3pt, opacity=0.45] (4.5, -1.7) -- (5.3, -1.7);
	\node[highlight!80!black, font=\footnotesize, right] at (5.4, -1.7) {上包络 $=$ \texttt{dp2[i]}};
\end{tikzpicture}
\caption{%
	每个候选 \texttt{j} 产生一条 V 形（谷底高 \texttt{dp1[j]}，位于 \texttt{preA[j]}）。所有 V 形斜率一样（$\pm 1$），上包络只由截距最大的两条臂决定——截距就是代码里的 \texttt{Mminus} 和 \texttt{Mplus}。其余臂（灰色虚线）全被淘汰。%
}
\label{fig:v-shape}
\end{figure}

\section{代码实现}

\begin{minted}{cpp}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = (1ll << 61) - 1;

struct Solve {
	ll N;
	vector<ll> A, preA;
	vector<ll> dp1, dp2, dp3, dp4;

	// 核心：优化后的转移，O(N)
	void excute_dp(const vector<ll> &from, vector<ll> &to) {
		ll Mplus = -INF, Mminus = -INF;
		for (int i = 1; i <= N; ++i) {
			Mplus  = max(Mplus,  from[i] + preA[i]);
			Mminus = max(Mminus, from[i] - preA[i]);
			to[i]  = max(Mminus + preA[i], Mplus - preA[i]);
		}
	}

	Solve() {
		cin >> N;
		A.resize(N + 2);
		for (int i = 1; i <= N; ++i)
			cin >> A[i];
		preA.resize(N + 2);
		partial_sum(A.begin(), A.end(), preA.begin());

		dp1.resize(N + 2, -INF);
		for (int i = 1; i <= N; ++i)
			dp1[i] = abs(preA[i]);

		dp2.resize(N + 2, -INF);
		dp3.resize(N + 2, -INF);
		dp4.resize(N + 2, -INF);
		excute_dp(dp1, dp2);
		excute_dp(dp2, dp3);
		excute_dp(dp3, dp4);
		cout << dp4[N] << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Solve solve;
	return 0;
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：$O(N)$。\texttt{excute\_dp} 单次 $O(N)$，调用三次，总计 $O(N)$。
	\item \textbf{空间复杂度}：$O(N)$。四个 DP 数组加前缀和数组。
\end{itemize}

\end{document}

PDF

写出一个 $O(n^2)$ 的 dp 代码没有那么难。

void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {
			dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
		}
	}
}

现在最关键的就是如何把这个内层的 for 循环给优化掉。

有绝对值？那就要把绝对值去掉，用分类讨论。

说白了，其实就是这样子，因为我们有 max 函数，甚至可以不需要分类讨论。

void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {
			dp2[i] = max(dp2[i], dp1[j] + preA[i] - preA[j]);
			dp2[i] = max(dp2[i], dp1[j] - (preA[i] - preA[j]));
		}
	}
}

AC代码

O（n*n）的这个源代码

// teamname: Gospel_rock
/**
 * Problem: P16230 [蓝桥杯 2026 省 A] 综合应变指标
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16230
 * Created: 2026-04-12 12:29:30
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
	ll N;
	vector<ll> A;
	vector<ll> preA;
	vector<ll> dp1;
	vector<ll> dp2;
	vector<ll> dp3;
	vector<ll> dp4;

	void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= i; ++j) {
				dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
			}
		}
	}

	Solve() {
		cin >> N;
		A.resize(N + 2);
		for (int i = 1; i <= N; ++i) {
			cin >> A[i];
		}
		preA.resize(N + 2);
		partial_sum(all(A), preA.begin());
		dp1.resize(N + 2, -INF);
		for (int i = 1; i <= N; ++i) {
			dp1[i] = abs(preA[i]);
		}
		dp2.resize(N + 2, -INF);
		dp3.resize(N + 2, -INF);
		dp4.resize(N + 2, -INF);
		excute_dp(dp1,dp2);
		excute_dp(dp2,dp3);
		excute_dp(dp3,dp4);
#ifdef LOCAL
		debug1d(dp1);
		debug1d(dp2);
		debug1d(dp3);
		debug1d(dp4);
#endif
		cout<<dp4[N]<<"\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase=1;testcase<=lT;++testcase)
	Solve solve;
	return 0;
}

/*

*/

AC
https://www.luogu.com.cn/record/273684075

源代码

// teamname: Gospel_rock
/**
 * Problem: P16230 [蓝桥杯 2026 省 A] 综合应变指标
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16230
 * Created: 2026-04-12 12:29:30
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
	ll N;
	vector<ll> A;
	vector<ll> preA;
	vector<ll> dp1;
	vector<ll> dp2;
	vector<ll> dp3;
	vector<ll> dp4;
	vector<array<ll, 2> > dp_1_preA;

	void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
		for (int j = 1; j <= N; ++j) {
			dp_1_preA[j][0] = dp1[j] - preA[j];
			dp_1_preA[j][1] = dp1[j] + preA[j];
			dp_1_preA[j][0] = max(dp_1_preA[j - 1][0], dp_1_preA[j][0]);
			dp_1_preA[j][1] = max(dp_1_preA[j - 1][1], dp_1_preA[j][1]);
		}
		for (int i = 1; i <= N; ++i) {
			// for (int j = 1; j <= i; ++j) {
			// 	dp2[i] = max(dp2[i], dp1[j] + preA[i] - preA[j]);
			// 	dp2[i] = max(dp2[i], dp1[j] - (preA[i] - preA[j]));
			// }
			dp2[i] = max(dp2[i],dp_1_preA[i][0] + preA[i]);
			dp2[i] = max(dp2[i],dp_1_preA[i][1] - preA[i]);
		}
	}

	Solve() {
		cin >> N;
		A.resize(N + 2);
		for (int i = 1; i <= N; ++i) {
			cin >> A[i];
		}
		preA.resize(N + 2);
		partial_sum(all(A), preA.begin());
		dp1.resize(N + 2, -INF);
		for (int i = 1; i <= N; ++i) {
			dp1[i] = abs(preA[i]);
		}
		dp2.resize(N + 2, -INF);
		dp3.resize(N + 2, -INF);
		dp4.resize(N + 2, -INF);
		dp_1_preA.resize(N + 2, {-INF, -INF});
		excute_dp(dp1, dp2);
		excute_dp(dp2, dp3);
		excute_dp(dp3, dp4);
#ifdef LOCAL
		debug1d(dp1);
		debug1d(dp2);
		debug1d(dp3);
		debug1d(dp4);
#endif
		cout << dp4[N] << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase=1;testcase<=lT;++testcase)
	Solve solve;
	return 0;
}

/*
AC
https://www.luogu.com.cn/record/273684075

*/