C. Reindeer and Sleigh 2
记 \(S\) 为乘坐雪橇的驯鹿集合
由题意可知，\(\displaystyle \sum_{i \in S} W_i \leqslant \sum_{i \notin S} P_i\)
不不等式做一下变形：
而 \(\displaystyle \sum_{i \notin S} P_i = \left(\sum_i P_i\right) - \left(\sum_{i \in S} P_i\right)\)
于是得到，
考虑贪心，应该让尽可能多的 \(W_i+P_i\) 小的驯鹿坐在雪橇上，于是我们应该先将序列 \(\{W_i+P_i\}\) 做升序排序
一开始没有驯鹿坐在雪橇上，然后按 \(\{W_i+P_i\}\) 递增的顺序依次将当前拉雪橇的驯鹿拉到雪橇上，并检查不等式是否仍然成立
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;int solve() {int n;cin >> n;vector<int> w(n), p(n);rep(i, n) cin >> w[i] >> p[i];vector<int> wp(n);rep(i, n) wp[i] = w[i]+p[i];sort(wp.begin(), wp.end());ll remain = 0;rep(i, n) remain += p[i];rep(i, n) {remain -= wp[i];if (remain < 0) return i;}return n;
}int main() {int t;cin >> t;while (t--) cout << solve() << '\n';return 0;
}
D. Sum of Differences
\( |A_i - B_j| = \begin{cases} B_j - A_i\ , &A_i \leqslant B_j\\ A_i - B_j\ , &A_i \geqslant B_j \end{cases} \)
考虑将这两个序列都放在数轴上，分别标记为 \(0\) 和 \(1\)
仅分析第一种情况，第二种同理
\(
\displaystyle
\sum (B_j - A_i) = \sum B_j - \sum A_i
\)
其中，\(
\displaystyle
\sum B_j = B_j \sum 1
\)
代码实现
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using P = pair<int, int>;
using mint = modint998244353;int main() {int n, m;cin >> n >> m;vector<int> a(n), b(m);rep(i, n) cin >> a[i];rep(i, m) cin >> b[i];vector<P> ps;rep(i, n) ps.emplace_back(a[i], 0);rep(i, m) ps.emplace_back(b[i], 1);sort(ps.begin(), ps.end());mint ans;rep(ri, 2) {mint sum = 0, cnt = 0;for (auto [x, type] : ps) {if (type == 0) {sum += x;cnt += 1;}else {ans += cnt*x - sum;}}for (auto& p : ps) p.first *= -1;reverse(ps.begin(), ps.end());}cout << ans.val() << '\n';return 0;
}
E. Sort Arrays
建 \(\text{Trie}\) 树，在树上做前序遍历
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;int main() {int n;cin >> n;vector<int> vid(1);vector<map<int, int>> to(1);for (int i = 1; i <= n; ++i) {int x, y;cin >> x >> y;int v = vid[x], u;if (!to[v].count(y)) {u = to.size();to.emplace_back();to[v][y] = u;}else u = to[v][y];vid.push_back(u);}vector<vector<int>> is(to.size());for (int i = 1; i <= n; ++i) is[vid[i]].push_back(i);vector<int> ans;auto f = [&](auto& f, int v) -> void {for (int i : is[v]) ans.push_back(i);for (auto p : to[v]) {f(f, p.second);}};f(f, 0);rep(i, n) cout << ans[i] << ' ';return 0;
}
F. Manhattan Christmas Tree 2
\( \max\limits_{i} (|x_i - X| + |y_i - Y|) \)
\(
|x_i - X| = \max(x_i-X, X-x_i)
\)
\(
|y_i - Y| = \max(y_i-Y, Y-y_i)
\)
\( \max\limits_{i} (|x_i - X| + |y_i - Y|) = \max\limits_{i}\left((x_i-X)+(y_i-Y), (x_i-X)+(Y-y_i), (X-x_i)+(y_i-Y), (X-x_i)+(Y-y_i)\right) \)
仅分析第一项，后面三项同理
\( \max\limits_{i=L}^R \left((x_i-X)+(y_i-Y)\right) = \max\limits_{i=L}^R (x_i+y_i) - X - Y \)
对于 \(\max\limits_{i=L}^R (x_i+y_i)\)，只需要开一颗线段树来求 \(\text{RMQ}\) 即可
代码实现
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace atcoder;
#define rep(i, n) for (int i = 0; i < (n); ++i)using namespace std;
using ll = long long;ll op(ll a, ll b) { return max(a, b); }
ll e() { return -1e18; }int main() {int n, q;cin >> n >> q;vector t(4, segtree<ll, op, e>(n));auto upd = [&](int i, int x, int y) {rep(j, 4) {ll val = 0;if (j&1) val += x; else val -= x;if (j&2) val += y; else val -= y;t[j].set(i, val);}};rep(i, n) {int x, y;cin >> x >> y;upd(i, x, y);}rep(qi, q) {int type;cin >> type;if (type == 1) {int i, x, y;cin >> i >> x >> y;--i;upd(i, x, y);}else {int l, r, x, y;cin >> l >> r >> x >> y;--l;ll ans = 0;rep(j, 4) {ll val = 0;if (j&1) val += x; else val -= x;if (j&2) val += y; else val -= y;ans = max(ans, t[j].prod(l, r) - val);}cout << ans << '\n';}}return 0;
}