近期训练题目一句话总结

Posted on 2026-05-29 Edited on 2026-08-14

近期训练题目一句话总结

然后 “-”+“空格”可以得到无序列表

HDU 2026 春季联赛 10 D - 歪歪爱追剧：筛掉不含明星时刻的区间后做带权区间选择；坑点是没有前驱时也要允许当前区间单独成为答案。
CF 1100 E - Deconstruction Tree ：固定终点看前驱区间，非根转移是 need[y] < x < y；根转移只看第二大的根分支最大值。题解
CF Round 1101 Div2 C2 - Seating Arrangement：两个洞见串起来看：一是桌子从空到非空是单向状态变化，所以拆成开桌者 / 跟随者；二是 A 不能待定式分配，因为其具有中间过程价值，因为它只有先作为跟随者进入结构，才会拥有“以后改成开桌者时吐回旧槽位”的中间过程价值。
金马 5 校 - 奇点蜂测序：区间异或约束先转成前缀点关系 $s_l \oplus s_{r+1}=x$ ，再用带权并查集维护连通块内相对异或；查询时同块输出差值，不同块输出 -1。
CF Edu 170 D - Attribute Checks：INT 当 dp 下标、STR 靠「已得点数 − INT」反推，把两维属性压成一维；每条检定本质是给一段连续区间 +1，用差分做到 O(1)，只有遇到加点才把差分 partial_sum 摊开、做一次背包式分裂转移再压回；m=5000 这个小界就是在暗示 O(n+m²)。
CF Edu 170 E - Card Game：单花色按点数从大到小变成括号前缀余额，用 Catalan / ballot 数压出 dp1；再让花色 1 的多余资源做一维 DP，刚好补完所有非王牌缺口。
ABC-470-D - Inverse and Swap 把排列看成位置和值之间的对应关系。

ABC-470-C - Inc, Dec, Xor 增减异或（注意题目条件限制：初始时 $A$ 的所有元素均为 $0$ ，以及操作的摊还分析）其实是一个比较简单的摊还分析，那么比较需要注意的就是题目中的初始时A的所有元素均为0，然后操作 1 只能给一个元素加1，然后操作 2 是对所有值减1，而且是减到0以后就不减了，注意到，其实这样子的话，数组中的正数元素是非常少的，直接暴力维护即可啊。
ABC-468-F - Chmax 我们不难注意到，观察到每步操作我们都必须要做啊，然后就可以发现，有些数字，我们是必须会被迫选到的**，这个前缀最大值数组中出现的值，我们必须要选**啊，而且不仅仅是必须要选，我们的有一个 X / Y 的上升序列一定就是长这个样！否则就不是很优秀啊。
Voronezh State University - Sitronics contest II——J. Just a map editor（连通块拼图）
先用 bfs 黑白染色，每一行贡献这个 m 个联通块啊。
然后可以用这个操作补上零头啊。
2026牛客暑期多校 8——B-Deep Finesse（深算）一个东西，整体比。。。小，可以化为前缀+1，-1 模型啊，进而转化为这个走格子模型啊，使用 dp 进行计数求解啊。

2026牛客暑期多校 8——B-Deep Finesse（深算）

2026 杭电暑期多校 8——1007 用传送门来让网格连通吧

https://acm.hdu.edu.cn/contest/problem?cid=1236&pid=1007

注意到这个 k 很小，虽然传送门是单向的这个（不方便直接使用并查集），但是我们直接在这个上面搞就好了，直接在并查集祖宗有向图上跑 bfs 即可啊。

没有这个 is_run 啊，会一不小心跑了 N*M 次啊。

vector<char> is_run(N * M + M + 10);
ll tim = 0;
for (int x = 1; x <= N; ++x) {
	for (int y = 1; y <= M; ++y) {
		if (!checkXY(x, y)) {
			continue;
		}
		++tim;
		int src = getIdx(x, y);
		src = dsu.find(src);
		if (is_run[src]) {
			continue;
		}
		is_run[src] = true;
		queue<int> q;
		q.push(src);
		vis[src] = tim;
		while (!q.empty()) {
			ll u = q.front();
			q.pop();
			for (auto to: g[u]) {
				if (vis[to] >= tim) continue;
				vis[to] = tim;
				connect[src].insert(to);
				q.push(to);
			}
		}
	}
}

整体全部 AC 代码

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

// teamname: Gospel_rock
/**
 * Problem: 用传送门来让网格连通吧
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1236&pid=1007
 * Created: 2026-08-13 12:39:11
 * 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 fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

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;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

ll N, M, K, Q;


/**   并查集（DSU）+ DSU on next
 *    find(x) 表示 x 之后第一个没有被标记的数字。
 *    构造函数传入的 n 必须不多不少，否则 countFa 会出错。
 *    base = 0 / 1 切换 0-based 与 1-based，合法下标范围分别是 [0, n) 与 [1, n]，默认 1-based。
 */
struct DSU {
	vector<int> fa;
	ll n;
	int base = 1; // 0 或 1，决定合法下标的起点

	DSU() {
	}

	DSU(ll n, int base = 1) : n(n), base(base) { init(n); }

	void init(ll n) {
		fa.resize(n + base + 5);
		for (int i = 0; i < SZ(fa); ++i) fa[i] = i;
	}

	ll find(ll x) {
		ll root = x;
		while (root != fa[root]) {
			root = fa[root];
		}
		while (x != root) {
			tie(x, fa[x]) = make_tuple(fa[x], root);
		}
		return x;
	}

	bool same(ll x, ll y) { return find(x) == find(y); }

	bool merge(ll x, ll y) {
		// 注意方向：fa[x] = y，配合 dsu on next
		x = find(x);
		y = find(y);
		if (x == y) return false;
		fa[x] = y;
		return true;
	}

	// 把 [l, r] 这段区间整段标记，标记后这段区间内任意点 find 都会越过去
	void taglr(ll l, ll r) {
		l = max((ll)base, l);
		r = min((ll)SZ(fa) - 2, r);
		l = find(l);
		while (l <= r) {
			merge(l, l + 1);
			l = find(l + 1);
		}
	}

	ll countFa() {
		// 当前还有多少个独立的根
		ll res = 0;
		for (ll i = base; i < base + n; ++i) if (fa[i] == i) ++res;
		return res;
	}
};

/* -> (Right, Down, Left, Up)
  |  |
   <-
*/


// 来自wida github仓库 https://github.com/hh2048/XCPC/tree/main 加了一些新功能
//46 ms https://acm.hdu.edu.cn/contest/view-code?cid=1179&rid=14912 读入字符getc(a) 的AC记录
// AC https://vjudge.net/solution/63197697 一道测试读写的codechef题目
namespace QuickRead {
	// 快读
	char buf[1 << 21], *p1 = buf, *p2 = buf;

	inline int getc() {
		return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
	}

	template<typename T>
	void Cin(T &a) {
		T ans = 0;
		bool f = 0;
		char c = getc();
		for (; c < '0' || c > '9'; c = getc()) {
			if (c == '-') f = 1;
		}
		for (; c >= '0' && c <= '9'; c = getc()) {
			ans = ans * 10 + c - '0';
		}
		a = f ? -ans : ans;
	}

	void getc(char &a) {
		char c = getc();
		while (isspace(c)) {
			c = getc();
		}
		a = c;
	}

	template<typename T, typename... Args>
	void Cin(T &a, Args &... args) {
		Cin(a), Cin(args...);
	}

	// ===== 输出 =====
	static constexpr size_t OUT_CAP = 1 << 21; // 大概是2MB
	char obuf[OUT_CAP];
	size_t op = 0;

	inline void flush() {
		if (op) {
			fwrite(obuf, 1, op, stdout);
			op = 0;
		}
	}

	inline void putc(char c) {
		if (op == OUT_CAP) flush();
		obuf[op++] = c;
	}

	template<typename T>
	void write(T x) {
		// 注意，这里输出不带换行
		if (x < 0) putc('-'), x = -x;
		if (x > 9) write(x / 10);
		putc(x % 10 + '0');
	}

	struct Flusher {
		// 析构时自动刷新
		~Flusher() { flush(); }
	} flusher;
} // namespace QuickRead
using namespace QuickRead;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};


ll getIdx(ll x, ll y) {
	return x * M + y;
}

void Solve() {
	// cin >> N >> M >> K >> Q;
	Cin(N, M, K, Q);
	vector<vector<char> > maze(N + 2, vector<char>(M + 2));
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			// cin >> maze[i][j];
			getc(maze[i][j]);
		}
	}
	DSU dsu(N * M + M + 10);
	auto checkXY = [&](ll x, ll y) {
		if (x < 1 || x > N) return false;
		if (y < 1 || y > M) return false;
		if (maze[x][y] == '#') {
			return false;
		}
		return true;
	};
	for (int x = 1; x <= N; ++x) {
		for (int y = 1; y <= M; ++y) {
			if (!checkXY(x, y)) {
				continue;
			}
			for (int i = 0; i < 4; ++i) {
				auto [tox,toy] = make_tuple(x + dx[i], y + dy[i]);
				if (checkXY(tox, toy)) {
					dsu.merge(getIdx(tox, toy), getIdx(x, y));
				}
			}
		}
	}
	vector<vector<int> > g(N * M + M + 10);
	for (int i = 1; i <= K; ++i) {
		ll x1, y1, x2, y2;
		Cin(x1, y1, x2, y2);
		if (dsu.same(getIdx(x1, y1), getIdx(x2, y2))) {
			continue;
		}
		ll fa1 = dsu.find(getIdx(x1, y1)), fa2 = dsu.find(getIdx(x2, y2));
		g[fa1].push_back(fa2);
	}
	vector<int> vis(N * M + M + 10);
	vector<set<int> > connect(N * M + M + 10);
	vector<char> is_run(N * M + M + 10);
	ll tim = 0;
	for (int x = 1; x <= N; ++x) {
		for (int y = 1; y <= M; ++y) {
			if (!checkXY(x, y)) {
				continue;
			}
			++tim;
			int src = getIdx(x, y);
			src = dsu.find(src);
			if (is_run[src]) {
				continue;
			}
			is_run[src] = true;
			queue<int> q;
			q.push(src);
			vis[src] = tim;
			while (!q.empty()) {
				ll u = q.front();
				q.pop();
				for (auto to: g[u]) {
					if (vis[to] >= tim) continue;
					vis[to] = tim;
					connect[src].insert(to);
					q.push(to);
				}
			}
		}
	}
	for (int i = 1; i <= Q; ++i) {
		ll x1, y1, x2, y2;
		// cin >> x1 >> y1 >> x2 >> y2;
		Cin(x1, y1, x2, y2);
		if (dsu.same(getIdx(x1, y1), getIdx(x2, y2))) {
			putc('1');
			putc('\n');
			continue;
		}
		ll fa1 = dsu.find(getIdx(x1, y1)), fa2 = dsu.find(getIdx(x2, y2));
		if (connect[fa1].contains(fa2)) {
			putc('1');
			putc('\n');
		} else {
			putc('0');
			putc('\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();
	return 0;
}

/*

TLE
https://acm.hdu.edu.cn/contest/view-code?cid=1236&rid=2789

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

*/

首选排除我们管不了的，我们管的了的东西，两两配对，绝对值之差要最大，显然是划分为两个集合，大的集合中的数字减去小的集合中的数字。这种较为简单，而且限制一看就比较宽松的计数题目，一般都和这个阶乘，集合划分后乱排有关系。然后两两配对计数的话，一开始可以不用关心这个两两是谁在前，谁在后，先关注哪两个数被分配到了同一集合，或者说是这个分配的顺序。

2026 杭电暑期多校 8-1002-会自动求和的序列

那么，如果我们发现一个操作每一轮都会做，或者操作的时间非常有规律，即便这个操作有一些不规律的增量啊，那么往往来说，其肯定是有办法通过基底值加上这个一个我们维护的增量值得到答案的。

2026 杭电暑期多校 8-1008-分数越小还是越大越好

这种让你构造这个最大最小的，可以先手玩一下样例，自己画一画，看看最大最小的构造策略是什么。

Mex 的题目，我们肯定要利用好 Mex 的性质。Mex 要求在 $<mex$ 的全部一一出现啊，一个都不能落下啊。

可以利用 mex 要求的这个连续属性，定义 dp 状态。设 $DP(u, v)$ 表示：将标签 $0, 1, \dots, \operatorname{dist}(u, v)$ 分配给路径 $u \dots v$ 上的所有节点，所能获得的最大累计贡献分数。（比如这道题目，他就利用了这个性质）

你也可以反过来这么想，如果说你的DP状态定义要比较的暴力的话，那么其实你将会需要考虑每一个点它到底要放什么值，这个其实我们完全不能够去考虑的，因为你每个点都要考虑的话，你这个DP就是一个N维的DP，完全没有任何效率可言，反正基本上就和暴力差不多。

2026 杭电暑期多校 8-1008-分数越小还是越大越好

Posted on 2026-08-13 Edited on 2026-08-14

题目大意

分数越小还是越大越好

给定一棵包含 $N$ 个顶点的树，顶点编号为 $1,2,\ldots,N$ 。

你需要选择一个 $0$ 到 $N-1$ 的排列 $P$ ，并将 $P_i$ 作为顶点 $i$ 的标签。

对于一个整数集合 $S$ ，定义 $\operatorname{MEX}(S)$ 为没有出现在 $S$ 中的最小非负整数。

对于两个顶点 $u,v$ ，设它们之间简单路径上的顶点集合为 $V(u,v)$ （当 $u=v$ 时 $V(u,v)=\{u\}$ ），定义

f(u,v)=\operatorname{MEX}\bigl(\{P_x \mid x\in V(u,v)\}\bigr).

树的分数定义为

\operatorname{score}(P)=\sum_{u=1}^{N}\sum_{v=u}^{N} f(u,v).

求在所有标签排列 $P$ 中，树的最小可能分数与最大可能分数。

第一行一个整数 $T$ ，表示测试数据组数。

每组测试数据格式如下：

第一行一个整数 $N$ ，表示树的顶点数；
接下来 $N-1$ 行，每行两个整数 $u,v$ ，表示树中存在一条连接顶点 $u$ 与顶点 $v$ 的无向边。

数据范围：

$3\le N\le 2000$ ；
$1\le u,v\le N$ ；
保证给出的边构成一棵树。

OJ 中只有一个正式测试点，该测试点满足：

$T=1000$ ；
$\sum N^2=2\times 10^{7}$ 。

对于每组测试数据输出一行两个整数，分别表示树的最小可能分数与最大可能分数。

1
2
3

5 7
5 11
6 16

第一组数据：树是一条链 $1-2-3$ ，需要把 $\{0,1,2\}$ 分配给三个顶点。

取 $P=(0,2,1)$ ，即 $P_1=0,\;P_2=2,\;P_3=1$ ：

$(u,v)$	路径上的标签集合	$f(u,v)$
$(1,1)$	$\{0\}$	$1$
$(1,2)$	$\{0,2\}$	$1$
$(1,3)$	$\{0,2,1\}$	$3$
$(2,2)$	$\{2\}$	$0$
$(2,3)$	$\{2,1\}$	$0$
$(3,3)$	$\{1\}$	$0$

总和为 $5$ ，这是该树能取到的最小分数。

取 $P=(1,0,2)$ ：

$(u,v)$	路径上的标签集合	$f(u,v)$
$(1,1)$	$\{1\}$	$0$
$(1,2)$	$\{1,0\}$	$2$
$(1,3)$	$\{1,0,2\}$	$3$
$(2,2)$	$\{0\}$	$1$
$(2,3)$	$\{0,2\}$	$1$
$(3,3)$	$\{2\}$	$0$

总和为 $7$ ，这是该树能取到的最大分数。

第二组数据：树是以顶点 $1$ 为中心、含 $3$ 片叶子的菊花图，枚举全部 $4!=24$ 种标签排列可知分数的取值范围为 $[5,11]$ 。

第三组数据：树是以顶点 $1$ 为中心、含 $4$ 片叶子的菊花图，枚举全部 $5!=120$ 种标签排列可知分数的取值范围为 $[6,16]$ 。

思路讲解

最小化的情况比较简单：

是链的话，那么就是 $2*N-1$ 。

不是链的话就是 N+1 啊。

cin >> N;
vector<vector<int> > g(N + 2);
for (int i = 1; i <= N - 1; ++i) {
	ll u, v;
	cin >> u >> v;
	g[u].push_back(v);
	g[v].push_back(u);
}
ll leaf_ct = 0;
for (int i = 1; i <= N; ++i) {
	if (SZ(g[i]) == 1) {
		leaf_ct++;
	}
}
if (leaf_ct <= 2) {
	// 一条链的情况
	cout << 2 * N - 1 << " ";
} else {
	cout << N + 1 << " ";
}

求解最大值

状态定义
设 $DP(u, v)$ 表示：将标签 $0, 1, \dots, \operatorname{dist}(u, v)$ 分配给路径 $u \dots v$ 上的所有节点，所能获得的最大累计贡献分数。

那么这个DP状态是如何定义出来的？我们在近期训练题目一句话总结里面写了。

AC代码

源代码

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

2026 杭电暑期多校 8-1010-合并之后字典序就变小了

Posted on 2026-08-13 Edited on 2026-08-14

题目大意

合并之后字典序就变小了

时间限制：2000 / 1000 MS（Java / 其他）
内存限制：524288 / 524288 KB

给定一个长度为 $N$ 的数组 $A$ ，其中每个元素均属于 $\{0,1,2\}$ 。

你可以执行任意多次以下操作：

选择两个相邻元素 $A_i, A_{i+1}$ ，将它们删除，并在原位置插入 $(A_i + A_{i+1}) \bmod 3$ 。

每次操作会使数组长度减少 $1$ 。

定义 $f(A)$ 为通过若干次（可以是 $0$ 次）操作能够得到的字典序最小的数组。

对于数组 $B$ ，定义

\operatorname{val}(B)=\sum_{i=1}^{|B|} B_i \cdot 3^{\,i-1}

给定数组 $A$ ，求

\sum_{L=1}^{N}\sum_{R=L}^{N}\operatorname{val}\bigl(f(A[L,R])\bigr)

对 $998244353$ 取模后的结果。其中 $A[L,R]$ 表示子数组 $[A_L, A_{L+1}, \ldots, A_R]$ 。

对于两个不同的数组 $P, Q$ ，若满足以下任意一条，则称 $P$ 的字典序小于 $Q$ ：

$P$ 是 $Q$ 的前缀；
存在位置 $i$ ，满足 $P_i < Q_i$ ，且对所有 $j < i$ 都有 $P_j = Q_j$ 。

第一行一个整数 $T$ ，表示测试数据组数。

对于每组测试数据：

第一行一个整数 $N$ ；
第二行 $N$ 个整数 $A_1, A_2, \ldots, A_N$ 。

数据范围：

$1 \le N \le 2 \times 10^5$ ；
$0 \le A_i \le 2$ 。

OJ 中只有一个正式测试点，该测试点满足 $T = 10000$ ， $\sum N = 2 \times 10^6$ 。

对于每组测试数据输出一行，表示所有子数组对应的 $\operatorname{val}(f(A[L,R]))$ 之和对 $998244353$ 取模后的结果。

1
2
3

3
9
30

第一组数据： $A = [2, 1]$ ，共 $3$ 个子数组。

子数组	$f$	$\operatorname{val}$
$[2]$	$[2]$	$2$
$[1]$	$[1]$	$1$
$[2,1]$	$[0]$	$0$

其中 $[2,1]$ 合并后得到 $[(2+1)\bmod 3] = [0]$ ，字典序小于 $[2,1]$ 。总和为 $2+1+0=3$ 。

第二组数据： $A = [1,1,2]$ ，共 $6$ 个子数组。

子数组	$f$	$\operatorname{val}$
$[1]$	$[1]$	$1$
$[1]$	$[1]$	$1$
$[2]$	$[2]$	$2$
$[1,1]$	$[1,1]$	$4$
$[1,2]$	$[0]$	$0$
$[1,1,2]$	$[1]$	$1$

其中 $[1,1]$ 若合并会得到 $[2]$ ，字典序反而更大，故不操作； $[1,1,2]$ 可以一路合并为 $[1]$ ，它是所有可达数组中字典序最小的。总和为 $1+1+2+4+0+1=9$ 。

第三组数据： $A = [2,1,0,2]$ ，共 $10$ 个子数组， $\operatorname{val}$ 依次为

2,\;1,\;0,\;2,\;0,\;1,\;6,\;0,\;0,\;18

总和为 $30$ 。例如整个数组 $[2,1,0,2]$ 的字典序最小结果为 $[0,0,2]$ ，其 $\operatorname{val} = 0 + 0\cdot 3 + 2\cdot 9 = 18$ 。

思路讲解

队友赛时过了，我就不看了。

AC代码

源代码

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

2026 杭电暑期多校 8-1002-会自动求和的序列

Posted on 2026-08-13 Edited on 2026-08-14

题目大意

会自动求和的序列

有两个长度为 $n$ 的序列 $a$ 和 $b$ 。

接下来依次经过 $m$ 天。每天开始时，对于所有 $1\le i\le n$ ，先执行 $a_i\leftarrow a_i+b_i$ ，然后执行当天的一次操作。

操作共有以下两种：

1 l r x：对于所有 $l\le i\le r$ ，执行 $b_i\leftarrow b_i+x$ 。
2 l r：求当前的区间和 $\sum_{i=l}^{r}a_i$ 对 $2^{64}$ 取模后的结果。

第一行包含一个整数 $T$ ，表示测试用例的组数。

对于每组测试用例：

第一行包含两个整数 $n,m$ ，分别表示序列长度和天数；
接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$ ，表示两个序列的初始值；
接下来 $m$ 行，每行包含一次操作，格式为 1 l r x 或 2 l r。

对于 OJ 中唯一一组正式测试数据，保证：

$T=10^4$ ；
$2\le n\le 5\times 10^5$ ；
$1\le m\le 5\times 10^5$ ；
$1\le a_i,b_i\le 10^9$ ；
$1\le l<r\le n$ ；
$1\le x\le 10^9$ ；
$\sum n=10^6$ ；
$\sum m=10^6$ 。

对于每次第二类操作，输出一行一个整数，表示询问结果对 $2^{64}$ 取模后的值。

结果应表示为 $0$ 到 $2^{64}-1$ 之间的十进制整数。

输入

输出

1
2
3

12
18
23

初始时 $a=[1,2,1,2]$ ， $b=[2,1,1,2]$ 。

第 $1$ 天：先令 $a_i\leftarrow a_i+b_i$ ，得到 $a=[3,3,2,4]$ 。操作为 2 1 4，输出 $3+3+2+4=12$ 。
第 $2$ 天：先令 $a_i\leftarrow a_i+b_i$ ，得到 $a=[5,4,3,6]$ 。操作为 1 1 2 1，将 $b_1,b_2$ 各加 $1$ ，得到 $b=[3,2,1,2]$ ，无输出。
第 $3$ 天：先令 $a_i\leftarrow a_i+b_i$ ，得到 $a=[8,6,4,8]$ 。操作为 2 1 3，输出 $8+6+4=18$ 。
第 $4$ 天：先令 $a_i\leftarrow a_i+b_i$ ，得到 $a=[11,8,5,10]$ 。操作为 2 2 4，输出 $8+5+10=23$ 。

思路讲解

其实只需要维护2个线段树，一个维护这个 $x$ 的和，一个维护一下 $x \times p$ 的和就可以了。

rep(i, 1, m)
{
    int op, l, r;
    cin >> op >> l >> r;
    if (op == 1)
    {
        ull x;
        cin >> x;
        treeX.rangeAdd(l, r, x);
        treeXP.rangeAdd(l, r, x * i);
    }
    else
    {
        ull base = (sa[r] - sa[l - 1]) + (sb[r] - sb[l - 1]) * i;
        //         这个就是上面公式中的 x*t，这个就是上面公式中的 x*p
        ull update = treeX.query(l, r) * i - treeXP.query(l, r);
        cout << base + update << '\n';
    }
}

AC代码

猫尾草的 AC 代码

// teamname:猫尾草
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <climits>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <set>
#include <map>
#define rep(i, a, n) for(int (i) = (a); (i) <= (n); (i) ++)
#define per(i, a, n) for(int (i) = (n); (i) >= (a); (i) --)
#define vi vector<int>
#define vvi vector<vector<int>>
#define vb vector<bool>
#define vll vector<ll>
#define vull vector<ull>
#define vvll vector<vector<ll>>
#define vpll vector<pair<ll, ll>>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ull = unsigned long long;
const char* sep[2] = {"", "\n"};
const ll N = 1e9 + 7, MOD = 998244353;

template<typename T>
struct SegmentTree
{
	#define mid ((l + r) >> 1)
	#define lp (p << 1)
	#define rp (p << 1 | 1)
	
	int n;
	vector<T> d, add;
	
    SegmentTree(int n_) : n(n_), d(4 * n), add(4 * n, 0) {}

	SegmentTree(int n_, const vector<T>& a) : n(n_), d(4 * n), add(4 * n, 0)
	{
		build(1, 1, n, a);
	}
	
	void build(int p, int l, int r, const vector<T>& a)
	{
		if (l == r)
		{
			d[p] = a[l];
			return;
		}
		build(lp, l, mid, a);
		build(rp, mid + 1, r, a);
		pull(p);
	}
	
	void pull(int p)
	{
		d[p] = d[lp] + d[rp];
	}

	void push(int p, int l, int r) 
	{
		if (add[p] != 0 && l != r) 
		{
			_add(lp, l, mid, add[p]);
			_add(rp, mid + 1, r, add[p]);
			add[p] = 0;
		}
	}
	
	void _add(int p, int l, int r, T v)
	{
		d[p] += v * (r - l + 1);
		add[p] += v;
	}
	
	void rangeAdd(int p, int l, int r, int ql, int qr, T v)
	{
		if (ql > r || l > qr) return;
		if (ql <= l && r <= qr) return _add(p, l, r, v);
		push(p, l, r);
		rangeAdd(lp, l, mid, ql, qr, v);
		rangeAdd(rp, mid + 1, r, ql, qr, v);
		pull(p);
	}
	
	T query(int p, int l, int r, int ql, int qr)
	{
		if (ql > r || l > qr) return {};
		if (ql <= l && r <= qr) return d[p];
		push(p, l, r);
		return query(lp, l, mid, ql, qr) + query(rp, mid + 1, r, ql, qr);
	}
	
	void rangeAdd(int l, int r, T v) { rangeAdd(1, 1, n, l, r, v); }
	
	T query(int l, int r) { return query(1, 1, n, l, r); }
};

void solve()
{
	int n, m;
	cin >> n >> m;

	vull a(n + 1), b(n + 1), sa(n + 1, 0), sb(n + 1, 0);
	rep(i, 1, n)
    {
        cin >> a[i] >> b[i];
        sa[i] = sa[i - 1] + a[i];
        sb[i] = sb[i - 1] + b[i];
    }
	
    SegmentTree<ull> treeX(n), treeXP(n);

    rep(i, 1, m)
    {
        int op, l, r;
        cin >> op >> l >> r;
        if (op == 1)
        {
            ull x;
            cin >> x;
            treeX.rangeAdd(l, r, x);
            treeXP.rangeAdd(l, r, x * i);
        }
        else
        {
            ull base = (sa[r] - sa[l - 1]) + (sb[r] - sb[l - 1]) * i;
            ull update = treeX.query(l, r) * i - treeXP.query(l, r);
            cout << base + update << '\n';
        }
    }
    
    return;
}

int main()
{
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);

	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T = 1;
    cin >> T; cin.ignore();
    while (T --)
        solve();
	
	return 0;
}

源代码

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

2026 杭电暑期多校 8-1009-价值总是越大越好

Posted on 2026-08-13 Edited on 2026-08-14

题目大意

价值总是越大越好

时间限制：2000 ms (Java) / 1000 ms (其他)　　空间限制：524288 KB

给定一个长度为 $2N$ 的数组 $P$ 。数组中的非零元素互不相同，取值范围为 $1$ 到 $2N$ ；缺失的元素用 $0$ 表示。

你需要把所有的 $0$ 替换为尚未出现过的整数，使得最终的 $P$ 恰好是 $1$ 到 $2N$ 的一个排列。

定义一个排列的价值为

|P_1-P_2|+|P_3-P_4|+\cdots+|P_{2N-1}-P_{2N}|

请求出有多少种补全方式能使该价值取到最大值。答案对 $998244353$ 取模。

两种补全方式只要存在至少一个位置上的数不同，就视为不同的方式。

第一行输入一个整数 $T$ ，表示测试数据组数。

每组测试数据包含两行：

第一行输入一个整数 $N$ ，表示数组长度为 $2N$ ；
第二行输入 $2N$ 个整数 $P_1,P_2,\dots,P_{2N}$ ，其中 $0$ 表示该位置尚未填入数字。

对于每组测试数据，保证：

$1\le N\le 2\times 10^5$ ；
$0\le P_i\le 2N$ ；
所有非零的 $P_i$ 互不相同。

OJ 中只有一个正式测试点，该测试点满足： $T=10000$ ， $\sum N=10^6$ 。

对于每组测试数据输出一行，表示使排列价值最大的补全方式数量对 $998244353$ 取模后的结果。

3
4
3 0 0 5 6 8 0 4
2
0 0 0 0
3
4 6 1 5 3 2

1
2
3

2
16
1

第一组数据： 已出现的数为 $\{3,4,5,6,8\}$ ，需要把 $1,2,7$ 填入第 $2,3,7$ 个位置。枚举全部 $6$ 种填法，可得到的价值分别为 $10,8,10,8,12,12$ ，最大价值为 $12$ ，共有 $2$ 种方式达到：

$[3,7,1,5,6,8,2,4]$ ，价值为 $|3-7|+|1-5|+|6-8|+|2-4|=4+4+2+2=12$ ；
$[3,7,2,5,6,8,1,4]$ ，价值为 $|3-7|+|2-5|+|6-8|+|1-4|=4+3+2+3=12$ 。

第二组数据： 所有位置均为空，需要用 $1,2,3,4$ 填满，共 $24$ 种排列。其中最大价值为 $4$ ，例如 $[1,4,2,3]$ 的价值为 $3+1=4$ ， $[3,1,2,4]$ 的价值为 $2+2=4$ ；而如 $[1,2,3,4]$ 的价值仅为 $1+1=2$ 。统计后恰有 $16$ 种排列的价值等于 $4$ 。

第三组数据： 数组中没有 $0$ ，本身已经是一个排列，因此只存在唯一一种"补全方式"（即不作任何改动），答案为 $1$ 。

思路讲解

我们的目标是想让这个和最大，所以说我们不想要浪费我们所有能够控制的集合，就是U，我们肯定想让U中大的数字去减小的数字。

数组中共有三种数对：

两个数字都已知（类型 1）：它们之间谁大谁小已经固定，因此它们的 $+1$ 和 $-1$ 符号也已经固定，我们无法改变。
一个已知，一个缺失（为 $0$ ）（类型 2）：假设已知的数字构成集合 $F_2$ 。
两个数字都缺失（均为 $0$ ）（类型 3）：设有 $c_3$ 对这样的数对。

令缺失的数字集合为 $M$ 。我们能自由分配符号的数字集合恰好为 $U = F_2 \cup M$ 。集合 $U$ 的大小为 $2(c_2 + c_3)$ 。
为了使得价值最大，我们将集合 $U$ 中的数字排序，将较大的一半分配符号 $+1$ ，将较小的一半分配符号 $-1$ 。由于 $U$ 中的数字各不相同，较大的一半中的任意数字都严格大于较小一半中的任意数字，因此这种最优的符号分配是绝对合法且唯一的。
现在问题转化为，在保证集合 $U$ 最优符号分配的前提下，有多少种合法的填数（配对）方式：
• 设集合 $M$ 中被分配为 $+1$ 的数字个数为 $m_+$ 。
• 设集合 $M$ 中被分配为 $-1$ 的数字个数为 $m_-$ 。
• 每一个“双 $0$ ”的数对（类型 3）需要消耗一个 $M$ 中的 $+1$ 和一个 $M$ 中的 $-1$ 。这两个数字在这两个 $0$ 的位置上有两种排列方式，因此 $c_3$ 个这样的数对会产生 $2^{c_3}$ 种内部排列。
• 确定了所有符号位置后， $m_+$ 个 $+1$ 数字可以任意填入需要 $+1$ 的空位，共有 $m_+!$ 种填法；同理， $m_-$ 个 $-1$ 数字共有 $m_-!$ 种填法。
因此最大价值的补全方式数量即为： $\displaystyle 2^{c_3} \times m_+! \times m_-! \pmod{998244353}$

#include <iostream>
#include <vector>

using namespace std;

// 定义题目要求的取模常数
const int MOD = 998244353;

// 预处理阶乘数组，以便在 O(1) 时间内获取 m_+! 和 m_-!
// N 最大为 2*10^5，所以最大阶乘需要计算到 200000
const int MAX_N = 200005;
long long fact[MAX_N];

// 预计算阶乘函数
void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX_N; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
}

void solve() {
    int n;
    cin >> n;
    
    // 数组长度为 2N
    int total_len = 2 * n;
    vector<int> p(total_len);
    
    // present[i] 标记数字 i 是否已经在数组中出现过
    vector<bool> present(total_len + 1, false);
    
    for (int i = 0; i < total_len; ++i) {
        cin >> p[i];
        if (p[i] != 0) {
            present[p[i]] = true;
        }
    }
    
    // 1. 收集缺失的数字集合 M (Missing elements)
    vector<int> missing_elements;
    for (int i = 1; i <= total_len; ++i) {
        if (!present[i]) {
            missing_elements.push_back(i);
        }
    }
    
    // 2. 统计两种特殊情况：
    // double_zero_pairs 对应理论中的 c3：表示两个数字都缺失的数对数量 (0, 0)
    int double_zero_pairs = 0; 
    
    // in_F2[i] 标记数字 i 是否属于集合 F2
    // F2 是指：在 (已知的非零数字, 0) 这种包含且仅包含一个 0 的数对中，那个已知的数字
    vector<bool> in_F2(total_len + 1, false);
    
    for (int i = 0; i < n; ++i) {
        int a = p[2 * i];
        int b = p[2 * i + 1];
        
        if (a == 0 && b == 0) {
            double_zero_pairs++;
        } else if (a == 0 && b != 0) {
            in_F2[b] = true;
        } else if (a != 0 && b == 0) {
            in_F2[a] = true;
        }
    }
    
    // 3. 构造可以自由分配符号的集合 U = F2 U M
    vector<int> free_elements;
    for (int i = 1; i <= total_len; ++i) {
        // 如果一个数字是缺失的 (M) 或者属于与 0 配对的已知数字 (F2)，就加入集合 U
        if (!present[i] || in_F2[i]) {
            free_elements.push_back(i);
        }
    }
    
    // 4. 找到中位数阈值，划分大数（+1）和小数（-1）
    // 因为 free_elements 是按 1 到 2N 的顺序扫描生成的，所以天生就是从小到大排好序的
    int half = free_elements.size() / 2;
    
    // 如果没有空位需要填补（或者说没有 0），直接输出 1 种方式（原样）
    if (half == 0) {
        cout << 1 << "\n";
        return;
    }
    
    // threshold 为大数集合的最小值，所有 >= threshold 的数字将被分配符号 +1，小于的分配 -1
    int threshold = free_elements[half];
    
    // 5. 将缺失的数字集合 M 划分为需要充当大数的 m_plus 和需要充当小数的 m_minus
    int missing_plus = 0;  // 理论中的 m_+
    int missing_minus = 0; // 理论中的 m_-
    
    for (int x : missing_elements) {
        if (x >= threshold) {
            missing_plus++;
        } else {
            missing_minus++;
        }
    }
    
    // 6. 计算最终的排列组合方案数： 2^(c3) * (m_+)! * (m_-)!
    long long ans = 1;
    
    // 乘上 2 的 c3 次方 (每一个 (0,0) 对内部有两种数字排列方式)
    for (int i = 0; i < double_zero_pairs; ++i) {
        ans = (ans * 2) % MOD;
    }
    
    // 乘上大数的任意填入排列数 (m_+)!
    ans = (ans * fact[missing_plus]) % MOD;
    
    // 乘上小数的任意填入排列数 (m_-)!
    ans = (ans * fact[missing_minus]) % MOD;
    
    // 输出最终答案
    cout << ans << "\n";
}

int main() {
    // 优化输入输出流速度，防止大数据超时
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 程序开始前先预计算阶乘
    precompute();
    
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

AC代码

源代码