2026“钉耙编程”中国大学生算法设计春季联赛（10）
闲话
这场我竟然没有被期望题打败（根本没开到期望题），我看错了一整场 T8 题面，这启示我们一定要手玩一下样例。
H 星际贸易市场
在一个星际贸易市场中，有 $ n $ 个摊位排成一排，每个摊位的库存量为 $ a_i $。市场管理者会进行以下操作 $ q $ 次（每次选择一个）：
补货：对第 \(l\) 到第 \(r\) 个摊位每个补充 \(d\) 件商品。
评估市场热度：计算第 \(l\) 到第 \(r\) 个摊位之间所有可能交易的“潜在交易量”。任意两个不同摊位 \(i\) 和 \(j\)（\(i < j\)）可以产生交易量，交易量等于两个摊位库存的乘积 \(a_i \times a_j\)。总潜在交易量就是所有这些两两乘积之和，需要求 \(998244353\) 取模（因为宇宙贸易法规要求）。
第一行输入一个整数 \(t\)，代表 \(t\) 组数据。
每组数据：
第 1 行包含两个整数 \(n\) 和 \(q\)（\(1 \leq n, q \leq 10^5\)），分别代表摊位的数量和操作的数量。
第 2 行包含 \(n\) 个整数 \(a_1, a_2, \dots, a_n\)，代表每个摊位的初始库存量（\(0 \leq a_i \leq 10^7\)）。
接下来 \(q\) 行，每行描述一个操作，格式如下：
操作类型 1：
1 l r d，表示一次补货操作，将区间 \([l, r]\) 内的每个摊位库存增加 \(d\)（\(0 \leq d \leq 10^7\)）。操作类型 2：
2 l r，表示一次评估操作，需要输出区间 \([l, r]\) 内所有摊位的潜在交易量对 \(998244353\) 取模的结果。保证：$1 \leq l \leq r \leq n $，且 $ \sum n, \sum q \leq 2 \times 10^6$。
我们先观察到 \((a_i + d) \times (a_j + d) = a_i \times a_j + (a_i + a_j) \times d + d \times d\)，然后可以推得区间加的式子为：
上面的式子中 \(\text{sum} \times d \times (\text{len} - 1)\) 表示对于每个 \(a_i\)，计算他会被计算多少次，\(\binom{\text{len}}{2} \times d \times d\) 则表示 \(d \times d\) 会被区间内所有点对计算到，贡献为 \(\binom{\text{len}}{2} \times d \times d\)。
那么只需要对这个东西拍一个线段树上去就行了（先计算 \(\text{ans}\) 再计算 \(\text{sum}\)）。
至于为啥这玩意我赛时没做出来，我非常诚恳的告诉你：我读错题了。
点击查看代码
#include <bits/stdc++.h>
using namespace std;typedef long long ll;const int N = 1e5 + 5, mod = 998244353;int n, m, a[N];
ll sum[N << 2], ans[N << 2], lt[N << 2];void PushUp(int k) {ans[k] = (sum[k << 1] * sum[k << 1 | 1] + ans[k << 1] + ans[k << 1 | 1]) % mod;sum[k] = (sum[k << 1] + sum[k << 1 | 1]) % mod;return;
}void BuildTree(int k, int l, int r) {sum[k] = ans[k] = lt[k] = 0;if (l == r) {sum[k] = a[l];return;}int mid = (l + r) >> 1;BuildTree(k << 1, l, mid);BuildTree(k << 1 | 1, mid + 1, r);PushUp(k);return;
}void PushDown(int k, int l, int r) {if (lt[k] == 0) return;int mid = (l + r) >> 1;ans[k << 1] = (ans[k << 1] + sum[k << 1] * lt[k] % mod * (mid - l) + lt[k] * lt[k] % mod * (1ll * (mid - l + 1) * (mid - l) / 2 % mod)) % mod;sum[k << 1] = (sum[k << 1] + lt[k] * (mid - l + 1)) % mod;lt[k << 1] = (lt[k << 1] + lt[k]) % mod;ans[k << 1 | 1] = (ans[k << 1 | 1] + sum[k << 1 | 1] * lt[k] % mod * (r - mid - 1) + lt[k] * lt[k] % mod * (1ll * (r - mid) * (r - mid - 1) / 2 % mod)) % mod;sum[k << 1 | 1] = (sum[k << 1 | 1] + lt[k] * (r - mid)) % mod;lt[k << 1 | 1] = (lt[k << 1 | 1] + lt[k]) % mod;lt[k] = 0;return;
}void Change(int k, int l, int r, int ql, int qr, ll val) {if (ql <= l && r <= qr) {ans[k] = (ans[k] + sum[k] * val % mod * (r - l) + val * val % mod * (1ll * (r - l + 1) * (r - l) / 2 % mod)) % mod;sum[k] = (sum[k] + val * (r - l + 1)) % mod;lt[k] = (lt[k] + val) % mod;return;}PushDown(k, l, r);int mid = (l + r) >> 1;if (ql <= mid) Change(k << 1, l, mid, ql, qr, val);if (mid < qr) Change(k << 1 | 1, mid + 1, r, ql, qr, val);PushUp(k);return;
}pair <ll, ll> Union(pair <ll, ll> x, pair <ll, ll> y) {return make_pair((x.first + y.first) % mod, (x.second + y.second + x.first * y.first) % mod);
}pair <ll, ll> Query(int k, int l, int r, int ql, int qr) {if (ql <= l && r <= qr) return make_pair(sum[k], ans[k]);PushDown(k, l, r);int mid = (l + r) >> 1;pair <ll, ll> res = make_pair(0, 0);if (ql <= mid) res = Union(res, Query(k << 1, l, mid, ql, qr));if (mid < qr) res = Union(res, Query(k << 1 | 1, mid + 1, r, ql, qr));PushUp(k);return res;
}void Solve() {cin >> n >> m;for (int i = 1; i <= n; i++) cin >> a[i];BuildTree(1, 1, n);while (m--) {int opt, l, r, d;cin >> opt;if (opt == 1) {cin >> l >> r >> d;Change(1, 1, n, l, r, d);} else {cin >> l >> r;cout << Query(1, 1, n, l, r).second << '\n';}}return;
}int main() {ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);int T;cin >> T;while (T--) Solve();return 0;
}
小结
赛时一定要记得手玩一下样例，不然你读错题了你都不知道。