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

题目大意

题目描述
给定 $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
3
1 3
1 4
3 4
2
1 3
1 4

样例输出

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……）