JOISC 2019 题解
Visits: 507
Contents
hide
Day1
試験 (Examination)
裸的三维偏序模板题，$\mathcal O(n \log^2 n)$ 的 CDQ 分治即可。
const int N = 6e5 + 7;
int n, m, a[N], c[N], t, ans[N];
struct P {
int x, y, z, o;
inline bool operator < (const P p) const {
return x == p.x ? o < p.o : x < p.x;
}
} p[N], q[N];
inline void add(int x, int k) {
while (x <= t) c[x] += k, x += x & -x;
}
inline int ask(int x) {
int k = 0;
while (x) k += c[x], x -= x & -x;
return k;
}
void cdq(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1;
cdq(l, mid), cdq(mid + 1, r);
for (int i = l, j = mid + 1, k = l; k <= r; k++)
if (j == r + 1 || (i != mid + 1 && p[i].y <= p[j].y)) {
if (!p[i].o) add(p[i].z, 1);
q[k] = p[i++];
} else {
if (p[j].o) ans[p[j].o] += ask(p[j].z);
q[k] = p[j++];
}
for (int i = l; i <= mid; i++)
if (!p[i].o) add(p[i].z, -1);
for (int i = l; i <= r; i++) p[i] = q[i];
}
int main() {
rd(n, m);
for (int i = 1; i <= n; i++)
rd(p[i].x, p[i].y), p[i].z = p[i].x + p[i].y;
for (int i = 1; i <= m; i++)
rd(p[i+n].x, p[i+n].y, p[i+n].z), p[i+n].o = i;
n += m;
for (int i = 1; i <= n; i++)
a[++t] = p[i].x, a[++t] = p[i].y, a[++t] = p[i].z;
sort(a + 1, a + t + 1);
t = unique(a + 1, a + t + 1) - (a + 1);
for (int i = 1; i <= n; i++)
p[i].x = t + 1 - (lower_bound(a + 1, a + t + 1, p[i].x) - a),
p[i].y = t + 1 - (lower_bound(a + 1, a + t + 1, p[i].y) - a),
p[i].z = t + 1 - (lower_bound(a + 1, a + t + 1, p[i].z) - a);
sort(p + 1, p + n + 1);
cdq(1, n);
for (int i = 1; i <= m; i++) print(ans[i]);
return 0;
}
ビーバーの会合 (Meetings)
有意思的交互题。
考虑到 $\text{Query}(x,y,z)$ 有以下两种情况：
- 若 $x,y,z$ 在一条链上，则返回中间的那个点。
- 若 $x,y,z$ 不在一条链上，则返回以 $x$ 为根时的 $\text{LCA}(y, z)$。
考虑每次对于一个点集随机其中的一条链 $(x,y)$，然后询问其他点与 $x,y$ 的答案。
答案相同的一定在一个子树内，是一个规模更小的子问题，可以递归分治。
同时被返回的所有值构成链上的所有点，同样是一个规模更小的子问题。
这个做法在菊花图的时候询问次数约为 $n^2$，但本题中最大度数为 $18$，因此询问次数约为 $18n$。
const int N = 2e3;
void work(vi a) {
if (a.size() == 1u) return;
if (a.size() == 2u) return Bridge(min(a[0], a[1]), max(a[0], a[1]));
random_shuffle(a.begin(), a.end());
vi b(a.size()), p(a.size());
b[0] = a[0], b[1] = a[1];
for (ui i = 2; i < a.size(); i++) b[i] = Query(a[0], a[1], a[i]);
for (ui i = 0; i < a.size(); i++) p[i] = i;
sort(p.begin(), p.end(), [&](int i, int j) { return b[i] < b[j]; });
vi d;
for (ui l = 0, r = 0; l < a.size(); l = ++r) {
d.pb(b[p[l]]);
vi c(1, a[p[l]]);
while (r + 1 < a.size() && b[p[r+1]] == b[p[l]]) c.pb(a[p[++r]]);
work(c);
}
work(d);
}
void Solve(int n) {
srand(time(0) ^ n);
vi a(n);
for (int i = 0; i < n; i++) a[i] = i;
work(a);
}
ナン (Naan)
贪心。
对于每个人，求出其划分为 $n$ 等份的切割点。
对于第 $i$ 次切割，在还未选中的人中选择第 $i$ 份切割点最小的人。
时间复杂度 $\mathcal O(n(n+L))$。
#define pl pair<ll, ll>
const int N = 2e3 + 7;
int n, m, ans2[N];
ll a[N];
pl p[N][N], ans1[N];
bool v[N];
inline bool operator < (pl a, pl b) {
return (__int128)a.fi * b.se < (__int128)b.fi * a.se;
}
int main() {
rd(n, m);
for (int i = 1; i <= n; i++) {
rda(a, m);
ll s = 0, o = 0;
for (int j = 1; j <= m; j++) s += a[j];
for (int j = 1, k = 1; j <= n; j++) {
while (k < m && (o + a[k]) * n < s * j) o += a[k++];
ll A = 1ll * n * a[k] * (k - 1) + s * j - o * n;
ll B = 1ll * n * a[k];
ll D = __gcd(A, B);
p[i][j] = mp(A / D, B / D);
}
}
for (int i = 1; i <= n; i++) {
int k = 0;
p[k][i] = mp(1, 0);
for (int j = 1; j <= n; j++)
if (!v[j]) k = p[j][i] < p[k][i] ? j : k;
v[k] = 1, ans1[i] = p[k][i], ans2[i] = k;
}
for (int i = 1; i < n; i++) print(ans1[i].fi, ans1[i].se);
for (int i = 1; i <= n; i++) print(ans2[i], " \n"[i==n]);
return 0;
}
Day2
ふたつのアンテナ (Two Antennas)
对于 $i$，我们可以将其拆成在 $i+a_i$ 处出现，$i+b_i+1$ 处消失的两个事件。
考虑从小到大枚举 $j$，同时维护 $d_i$ 表示 $i$ 的最大成本。
则每新加入一个 $j$，我们要把当前存在的 $i$ 中 $\in [j-b_j,j-a_j]$ 的 $i$，将 $d_i$ 对 $|h_i-h_j|$ 取 $\max$。
对于询问 $l,r$，答案就是枚举到 $j=r$ 时的 $\max_{i=l}^{r} d_i$。
接下来考虑如何维护这个过程。
首先那个绝对值可以去掉，正反做两次就可以了，不妨设此时要求 $h_i \ge h_j$。
然后对于每个 $i$ 再维护一个 $c_i$，当其存在时 $c_i = h_i$，否则 $c_i = -\infty$。
那么加入一个 $j$ 时，我们就是要把 $[j-b_j,j-a_j]$ 中的 $d$ 对 $c_i – h_j$ 取 $\max$。
这些都可以线段树实现，时间复杂度 $\mathcal O(n \log n)$。
const int N = 2e5 + 7, inf = 1e9 + 1;
int n, m, h[N], a[N], b[N], ans[N];
vector<pi> q[N];
struct SGT {
struct T {
int l, r;
int c, d, h;
} t[N<<2|1];
inline void update(int p) {
t[p].c = max(t[ls].c, t[rs].c);
t[p].d = max(t[p].d, max(t[ls].d, t[rs].d));
}
inline void work(int p, int x) {
t[p].h = min(t[p].h, x);
t[p].d = max(t[p].d, t[p].c - t[p].h);
}
inline void spread(int p) {
work(ls, t[p].h), work(rs, t[p].h), t[p].h = inf;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
t[p].c = t[p].d = -inf, t[p].h = inf;
if (l == r) return;
build(ls, l, md), build(rs, md + 1, r);
update(p);
}
void setc(int p, int x, int k) {
if (t[p].l == t[p].r) return t[p].c = k, t[p].h = inf, void();
spread(p);
if (x <= md) setc(ls, x, k);
else setc(rs, x, k);
update(p);
}
void add(int p, int l, int r, int x) {
if (t[p].l >= l && t[p].r <= r) return work(p, x);
spread(p);
if (l <= md) add(ls, l, r, x);
if (r > md) add(rs, l, r, x);
update(p);
}
int ask(int p, int l, int r) {
if (t[p].l >= l && t[p].r <= r) return t[p].d;
spread(p);
int ret = -inf;
if (l <= md) ret = max(ret, ask(ls, l, r));
if (r > md) ret = max(ret, ask(rs, l, r));
return ret;
}
} t;
vi p[N];
inline void solve() {
t.build(1, 1, n);
for (int j = 1; j <= n; j++) {
for (int i : p[j]) t.setc(1, abs(i), i > 0 ? h[i] : -inf);
if (max(1, j - b[j]) <= max(0, j - a[j]))
t.add(1, max(1, j - b[j]), max(0, j - a[j]), h[j]);
for (pi o : q[j]) ans[o.se] = max(ans[o.se], t.ask(1, o.fi, j));
}
}
int main() {
rd(n);
for (int i = 1; i <= n; i++) rd(h[i], a[i], b[i]);
rd(m);
for (int i = 1, l, r; i <= m; i++)
rd(l, r), q[r].pb(mp(l, i)), ans[i] = -1;
for (int i = 1; i <= n; i++) {
if (i + a[i] <= n) p[i+a[i]].pb(i);
if (i + b[i] + 1 <= n) p[i+b[i]+1].pb(-i);
}
solve();
for (int i = 1; i <= n; i++) h[i] = inf - h[i];
solve();
for (int i = 1; i <= m; i++) print(ans[i]);
return 0;
}
ふたつの料理 (Two Dishes)
首先有一个 $\mathcal O(nm)$ 的 DP。
设 $f_{i,j}$ 表示完成了 $I$ 的 $i$ 个步骤 $J$ 的 $j$ 个步骤时的最高得分，有转移
$$
f_{i,j} = \max(f_{i-1,j} + [sa_i + sb_j \le s_i]p_i, f_{i,j-1} + [sa_i+sb_j \le t_j]q_j)
$$
其中 $sa,sb$ 分别是 $a,b$ 的前缀和。
考虑优化这个 DP。
将第一维看成时间轴，即从小到大枚举 $i$，同时维护 $f_j$。
那么当枚举到 $i$ 时：
- 将满足 $sa_i + sb_j \le s_i$ 的 $j$，$f_j$ 加上 $p_i$。
显然满足条件的 $j$ 是一个前缀。 - 设 $v_j = [sa_i+sb_j \le t_j]q_j$，将 $f_j$ 与 $f_{j-1} + v_j$ 取 $\max$。
注意 $v_j$ 一定是先为 $q_j$ 后为 $0$。
考虑维护 $f$ 的差分 $g$，则两种操作分别改为：
- 单点加。
- 将 $g_j$ 与 $v_j$ 取 $\max$。
注意 $g$ 是差分数组，所以 $g_{j+1}$ 还要减去 $g_j$ 取 $\max$ 前后的差值。
再考虑所有的 $w_j = g_j – v_j$，则两种操作再改为：
- 单点加。
- 如果 $v_j$ 要从 $q_j$ 变为 $0$，则将 $w_j$ 加上 $q_j$。
如果 $w_j < 0$，则 $w_{j+1}$ 加上 $w_j$，$w_j$ 赋值为 $0$。
发现所有的操作都神奇地变成了是单点操作！
注意到 $w_j = 0$ 的 $j$ 实际上并没有什么用，考虑用一个 set 维护所有 $w_j \ne 0$ 的 $j$。
每次暴力修改涉及到的所有 $g_j$ 即可，时间复杂度 $\mathcal O(n \log n)$。
const int N = 1e6 + 7;
int n, m;
ll a[N], s[N], p[N], b[N], t[N], q[N];
ll sa[N], sb[N], g[N], ans;
int pa[N], pb[N];
vi E[N], P;
set<int> S;
int main() {
rd(n, m);
for (int i = 1; i <= n; i++) rd(a[i], s[i], p[i]);
for (int j = 1; j <= m; j++) rd(b[j], t[j], q[j]);
for (int i = 1; i <= n; i++) sa[i] = sa[i-1] + a[i];
for (int j = 1; j <= m; j++) sb[j] = sb[j-1] + b[j];
for (int i = 1; i <= n; i++)
pa[i] = upper_bound(sb, sb + m + 1, s[i] - sa[i]) - sb - 1;
for (int j = 1; j <= m; j++)
pb[j] = upper_bound(sa, sa + n + 1, t[j] - sb[j]) - sa - 1;
for (int j = 1; j <= m; j++)
if (pb[j] >= 0) {
if (pb[j] + 1 <= n) E[pb[j]+1].pb(j);
else ans += q[j];
}
for (int i = 1; i <= n; i++) {
P.clear();
if (pa[i] >= 0) {
ans += p[i];
if (pa[i] + 1 <= m)
g[pa[i]+1] -= p[i], S.insert(pa[i] + 1), P.pb(pa[i] + 1);
}
for (int j : E[i]) g[j] += q[j], S.insert(j), P.pb(j);
sort(P.begin(), P.end());
for (int j : P) {
auto l = S.lower_bound(j), r = l;
ll o = 0;
while (r != S.end()) {
g[*r] += o;
if (g[*r] >= 0) break;
o = g[*r], g[*r++] = 0;
}
S.erase(l, r);
}
}
for (int j = 1; j <= m; j++) ans += g[j];
print(ans);
return 0;
}
ふたつの交通機関 (Two Transportations)
通信题不做。
Day3
指定都市 (Designated Cities)
$1/2$ 的答案 DP 求，后面的贪心往点集里加叶子，线段树/长链剖分维护。
const int N = 2e5 + 7;
int n, m, rt;
vector<pi> e[N];
ll f[N], g[N], ans[N];
void dfs1(int x, int fa) {
for (pi o : e[x]) {
int y = o.fi;
if (y == fa) continue;
dfs1(y, x), f[x] += f[y] + o.se;
}
}
void dfs2(int x, int fa) {
for (pi o : e[x]) {
int y = o.fi;
if (y == fa) {
g[x] += o.se;
break;
}
}
for (pi o : e[x]) {
int y = o.fi;
if (y == fa) continue;
g[y] = g[x] + f[x] - f[y] - o.se;
dfs2(y, x);
}
}
int l[N], r[N], s[N], p[N], t, fa[N], hh[N];
ll ga[N], h[N][2];
void dfs3(int x, int fa) {
hh[x] = x;
for (pi o : e[x]) {
int y = o.fi;
if (y == fa) continue;
dfs3(y, x);
if (h[x][1] < h[y][0] + o.se) h[x][1] = h[y][0] + o.se;
if (h[x][0] < h[x][1]) swap(h[x][0], h[x][1]), hh[x] = hh[y];
}
}
void dfs4(int x, int fa) {
::fa[x] = fa;
l[x] = t + 1;
if (e[x].size() == 1u) s[++t] = x, p[t] = x;
for (pi o : e[x]) {
int y = o.fi;
if (y == fa) continue;
ga[y] = o.se, h[y][0] = h[x][0] + o.se, dfs4(y, x);
}
r[x] = t;
}
struct SGT {
struct T {
int l, r;
int o;
ll x, z;
} t[N<<2|1];
inline void update(int p) {
if (t[ls].x >= t[rs].x) t[p].x = t[ls].x, t[p].o = t[ls].o;
else t[p].x = t[rs].x, t[p].o = t[rs].o;
}
inline void work(int p, ll x) {
t[p].x += x, t[p].z += x;
}
inline void spread(int p) {
if (t[p].z) work(ls, t[p].z), work(rs, t[p].z), t[p].z = 0;
}
void build(int p, int l, int r) {
t[p].l = l, t[p].r = r;
if (l == r) return t[p].x = h[::p[l]][0], t[p].o = l, void();
build(ls, l, md), build(rs, md + 1, r);
update(p);
}
void add(int p, int l, int r, ll x) {
if (t[p].l >= l && t[p].r <= r) return work(p, x);
spread(p);
if (l <= md) add(ls, l, r, x);
if (r > md) add(rs, l, r, x);
update(p);
}
} sgt;
bool v[N];
ll now;
int main() {
rd(n);
for (int i = 1, a, b, c, d; i < n; i++)
rd(a, b), rd(c, d), e[a].pb(mp(b, c)), e[b].pb(mp(a, d));
dfs1(1, 0);
dfs2(1, 0);
ans[1] = f[1] + g[1];
for (int i = 1; i <= n; i++)
ans[1] = min(ans[1], f[i] + g[i]);
dfs3(1, 0);
rt = hh[1], ans[2] = f[1] + g[1] - h[1][0] - h[1][1];
for (int i = 1; i <= n; i++)
if (f[i] + g[i] - h[i][0] - h[i][1] < ans[2])
rt = hh[i], ans[2] = f[i] + g[i] - h[i][0] - h[i][1];
h[rt][0] = 0, dfs4(rt, 0);
sgt.build(1, 1, t);
v[rt] = 1, now = f[rt] + g[rt];
for (int i = 1 + (e[rt].size() == 1u); i <= t; i++) {
int x = s[sgt.t[1].o];
now -= sgt.t[1].x;
while (!v[x]) sgt.add(1, l[x], r[x], -ga[x]), v[x] = 1, x = fa[x];
if (i != 1) ans[i] = now;
}
rd(m);
for (int i = 1, x; i <= m; i++) rd(x), print(ans[min(x,t)]);
return 0;
}
ランプ (Lamps)
存在一种最优策略为，赋值操作的区间两两不交，取反操作的区间两两不交，所有赋值操作在取反操作之前。
设 $f_{i,0/1/2}$ 表示第 $i$ 位赋值为 $0/1$ 或不赋值的情况下操作区间端点的最小个数，则最后答案除以 $2$ 即可。
const int N = 1e6 + 7, inf = 1e9;
const int c[3][3] = {{0,2,1},{2,0,1},{1,1,0}};
int n, f[N][3];
char s[N], t[N];
bool a[N], b[N];
int main() {
rd(n), rds(s, n), rds(t, n);
for (int i = 1; i <= n; i++) a[i] = s[i] & 15, b[i] = t[i] & 15;
++n;
f[1][0] = (0 ^ b[1]) + 1;
f[1][1] = (1 ^ b[1]) + 1;
f[1][2] = a[1] ^ b[1];
for (int i = 2; i <= n; i++) {
f[i][0] = f[i][1] = f[i][2] = inf;
for (int j = 0; j < 3; j++)
for (int k = 0; k < 3; k++) {
int x = (j == 2 ? a[i-1] : j) ^ b[i-1];
int y = (k == 2 ? a[i] : k) ^ b[i];
f[i][k] = min(f[i][k], f[i-1][j] + c[j][k] + (x ^ y));
}
}
print(f[n][2] >> 1);
return 0;
}
時をかけるビ太郎 (Bitaro, who Leaps through Time)
首先把 $i$ 的时间减去 $i$，则所有斜线移动都变成了横线。
把每个区间 $[l,r]$ 看成一个二元组 $(l,r)$，合并两个二元组 $(l_1,r_1),(l_2,r_2)$ 有三种情况：
- $\max(l_1,l_2) \le \min(r_1,r_2) \to (\max(l_1,l_2), \min(r_1,r_2))$。
-
$r_1 < l_2$，$l_1 < r_2$，这两种情况好像不能用二元组表示的样子。
那么，我们再设一个三元组 $(l,r,k)$ 表示从 $l$ 走进 $r$ 走出，中间使用技能次数为 $k$。
此时既有二元组又有三元组，我们需要考虑所有合并的情况：
- $(l_1,r_1),(l_2,r_2)$：
- $\max(l_1,l_2) \le \min(r_1,r_2) \to (\max(l_1,l_2), \min(r_1,r_2))$。
- $r_1 < l_2 \to (r_1,l_2,0)$。
- $l_1 > r_2 \to (l_1,r_2,l_1-r_2)$。
- $(l_1,r_1),(l_2,r_2,k_2)$：
- $l_1 \le l_2 \le r_1 \to (l_2,r_2,k_2)$。
- $r_1 < l_2 \to (r_1,r_2,k_2)$。
- $l_1 > l_2 \to (l_1,r_2,k_2+l_1-l_2)$。
- $(l_1,r_1,k_1),(l_2,r_2)$：
- $l_2 \le r_1 \le r_2 \to (l_1, r_1, k_1)$。
- $r_1 < l_2 \to (l_1,l_2,k_1)$。
- $r_1 > r_2 \to (l_1,r_2,k_1+r_1-r_2)$。
- $(l_1,r_1,k_1),(l_2,r_2,k_2)$：$(l_1,r_2,k_1+k_2+\max(r_1-l_2, 0))$。
线段树维护即可，时间复杂度 $\mathcal O(q \log n)$。
const int N = 3e5 + 7;
int n, q;
struct P {
int l, r;
ll k;
inline P() {}
inline P(int l, int r, ll k = -1) : l(l), r(r), k(k) {}
inline friend P operator + (P a, P b) {
if (!~a.k && !~b.k) {
if (max(a.l, b.l) <= min(a.r, b.r))
return P(max(a.l, b.l), min(a.r, b.r));
if (a.r < b.l) return P(a.r, b.l, 0);
if (a.l > b.r) return P(a.l, b.r, a.l - b.r);
}
if (!~a.k && ~b.k) {
if (a.l <= b.l && b.l <= a.r) return b;
if (a.r < b.l) return P(a.r, b.r, b.k);
if (a.l > b.l) return P(a.l, b.r, b.k + a.l - b.l);
}
if (~a.k && !~b.k) {
if (b.l <= a.r && a.r <= b.r) return a;
if (a.r < b.l) return P(a.l, b.l, a.k);
if (a.r > b.r) return P(a.l, b.r, a.k + a.r - b.r);
}
return P(a.l, b.r, a.k + b.k + max(a.r - b.l, 0));
}
} a1[N], a2[N];
struct SGT {
struct T {
int l, r;
P x;
} t[N<<2|1];
inline void update(int p) {
t[p].x = t[ls].x + t[rs].x;
}
void build(int p, int l, int r, P* a) {
t[p].l = l, t[p].r = r;
if (l == r) return t[p].x = a[l], void();
build(ls, l, md, a), build(rs, md + 1, r, a);
update(p);
}
void add(int p, int l, int r, P x) {
if (t[p].l >= l && t[p].r <= r) return t[p].x = x, void();
if (l <= md) add(ls, l, r, x);
if (r > md) add(rs, l, r, x);
update(p);
}
P ask(int p, int l, int r) {
if (t[p].l >= l && t[p].r <= r) return t[p].x;
if (r <= md) return ask(ls, l, r);
if (l > md) return ask(rs, l, r);
return ask(ls, l, r) + ask(rs, l, r);
}
} t1, t2;
int main() {
rd(n, q);
for (int i = 1; i < n; i++)
rd(a1[i].l, a1[i].r), --a1[i].r, a1[i].k = -1, a2[n-i] = a1[i],
a1[i].l -= i, a1[i].r -= i,
a2[n-i].l -= n - i, a2[n-i].r -= n - i;
if (n > 1) t1.build(1, 1, n - 1, a1), t2.build(1, 1, n - 1, a2);
for (int i = 1, o; i <= q; i++) {
rd(o);
if (o == 1) {
int p, s, e;
rd(p, s, e), --e;
if (n == 1) continue;
t1.add(1, p, p, P(s - p, e - p));
t2.add(1, n - p, n - p, P(s - (n - p), e - (n - p)));
} else {
int a, b, c, d;
rd(a, b), rd(c, d);
if (a == c) print(max(0, b - d));
else if (a < c) print((P(b - a, b - a, 0) + t1.ask(1, a, c - 1) + P(d - c, d - c, 0)).k);
else print((P(b - (n - a + 1), b - (n - a + 1), 0) + t2.ask(1, n - a + 1, n - c) + P(d - (n - c + 1), d - (n - c + 1), 0)).k);
}
}
return 0;
}
Day4
ケーキの貼り合わせ (Cake 3)
首先显然对 $c$ 排序后答案是某个区间的前 $k$ 大 $v$ 之和减去两倍的 $c$ 之差。
然而显然我们不需要考虑所有区间，可能成为答案的区间满足决策单调性，只有 $\mathcal O(n)$ 个。
然后区间前 $k$ 大和用个主席树就行了，总时间复杂度 $\mathcal O(n \log^2 n)$。
由于第一次写决策单调性，这里记一下步骤：
建一个队列，里面保存三元组 $(l,r,x)$，表示当前情况下 $l \sim r$ 的最优决策在 $x$。
从小到大枚举 $i$：
- 若队头的 $r < i$，则弹出队头。
- 用此时的队头作为最优决策转移到 $i$。
- 不断弹出比 $i$ 更劣的队尾。
- 若此时队尾比 $i$ 优，则直接将 $i$ 补在队尾。
- 否则在队尾上二分找到第一个以 $i$ 为最优决策点的位置，改变队尾的 $r$ 值，同时插入 $i$。
const int N = 2e5 + 7;
int n, m, b[N], k;
pi a[N];
ll ans = -1e18;
struct P {
int l, r, x;
inline P() {}
inline P(int l, int r, int x) : l(l), r(r), x(x) {}
};
deque<P> q;
struct T {
int l, r, c;
ll s;
} t[N<<6|1];
int rt[N], tot;
int ins(int p, int l, int r, int x) {
int q = ++tot;
t[q] = t[p];
++t[q].c, t[q].s += b[x];
if (l == r) return q;
int d = (l + r) >> 1;
if (x <= d) t[q].l = ins(t[p].l, l, d, x);
else t[q].r = ins(t[p].r, d + 1, r, x);
return q;
}
ll ask(int p, int q, int l, int r, int k) {
if (l == r) return 1ll * b[l] * k;
int c = t[t[p].r].c - t[t[q].r].c, d = (l + r) >> 1;
if (c >= k) return ask(t[p].r, t[q].r, d + 1, r, k);
return t[t[p].r].s - t[t[q].r].s + ask(t[p].l, t[q].l, l, d, k - c);
}
inline ll ask(int l, int r) {
if (r - l + 1 < m) return -1e18;
return ask(rt[r], rt[l-1], 1, k, m) - (a[r].fi - a[l].fi) * 2;
}
int main() {
rd(n, m);
for (int i = 1; i <= n; i++) rd(a[i].se, a[i].fi), b[i] = a[i].se;
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1);
k = unique(b + 1, b + n + 1) - (b + 1);
rt[0] = tot = 1;
for (int i = 1; i <= n; i++)
a[i].se = lower_bound(b + 1, b + k + 1, a[i].se) - b,
rt[i] = ins(rt[i-1], 1, k, a[i].se);
for (int i = 1; i <= n; i++) {
if (q.size() && q.front().r < i) q.pop_front();
if (i >= m) ans = max(ans, ask(q.front().x, i));
while (q.size() && ask(q.back().x, q.back().l) <= ask(i, q.back().l)) q.pop_back();
if (q.size() && ask(q.back().x, q.back().r) <= ask(i, q.back().r)) {
int l = q.back().l, &r = --q.back().r;
while (l < r) {
int d = (l + r + 1) >> 1;
if (ask(q.back().x, d) <= ask(i, d)) r = d - 1;
else l = d;
}
}
if (q.empty()) q.pb(P(i + m - 1, n, i));
else if (q.size() && q.back().r != n) q.pb(P(q.back().r + 1, n, i));
}
print(ans);
return 0;
}
合併 (Mergers)
显然把同一个州用并查集整到一坨里，然后剩下的依然是个树。
问题变成用最少的路径覆盖一棵树的所有边，贪心一下，设叶子数为 $c$，答案就是 $\lfloor \frac {c+1}2 \rfloor$。
const int N = 5e5 + 7;
int n, m, a[N], f[N], ans;
vi e[N], p[N];
namespace HLD {
int d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;
void dfs(int x) {
s[x] = 1;
for (int y : e[x])
if (y != f[x]) {
f[y] = x, d[y] = d[x] + 1;
dfs(y), s[x] += s[y];
if (s[y] > s[son[x]]) son[x] = y;
}
}
void dfs(int x, int p) {
dfn[x] = ++num, rnk[num] = x;
top[x] = p;
if (son[x]) dfs(son[x], p);
for (int y : e[x])
if (y != f[x] && y != son[x])
dfs(y, y);
}
inline int lca(int x, int y) {
while (top[x] != top[y]) {
if (d[top[x]] < d[top[y]]) swap(x, y);
x = f[top[x]];
}
return d[x] < d[y] ? x : y;
}
inline void main() {
d[1] = 1, dfs(1), dfs(1, 1);
}
}
int get(int x) {
return x == f[x] ? x : (f[x] = get(f[x]));
}
set<int> s[N];
int main() {
rd(n, m);
for (int i = 1, x, y; i < n; i++)
rd(x, y), e[x].pb(y), e[y].pb(x);
rda(a, n);
for (int i = 1; i <= n; i++) p[a[i]].pb(i), f[i] = i;
HLD::main();
for (int i = 1; i <= m; i++) {
if (p[i].empty()) continue;
int x = p[i][0];
for (int y : p[i]) {
x = get(x), y = get(y);
int z = get(HLD::lca(x, y));
while (x != z) f[x] = z, x = get(HLD::f[x]);
while (y != z) f[y] = z, y = get(HLD::f[y]);
}
}
for (int x = 1; x <= n; x++)
for (int y : e[x])
if (get(x) != get(y)) s[get(x)].insert(get(y));
for (int i = 1; i <= n; i++) ans += s[i].size() == 1u;
print((ans + 1) >> 1);
return 0;
}
鉱物 (Minerals)
首先用 $2n$ 次将所有元素划分成两个内部没有相同元素的集合 $A,B$。
考虑分治，对于 $m$ 个元素的集合 $A,B$，将 $A$ 的一半与 $B$ 的每一个一起询问。
设 $i$ 个点的询问次数为 $f(i)$，最优情况下可以做到 $f(i) = 2f(\frac i2) + \frac 32i$。
$n = 4.3 \times 10^4$ 时 $f(n) = 1020892$，无法 AC，但能拿 $85$ 分。
考虑不那么平均地分配 $A$ 的「一半」。
假如我们选择了 $A$ 中 $|A| \times p$ 的数，则 $f(i) = f(pi) + f((1-p)i) + (1+p)i$。
取 $p=0.37$ 时能过。
map<int, int> f;
void work(vi a, vi b, int o) {
int n = a.size();
if (!n) return;
if (n == 1) return f[a[0]] = b[0], f[b[0]] = a[0], void();
int mid = n * 0.37;
if (!o) mid = n - mid;
if (!mid) ++mid;
if (mid == n) --mid;
vi a1, a2, b1, b2;
int ret = 0;
for (int i = 0; i < mid; i++) a1.pb(a[i]);
for (int i = mid; i < n; i++) a2.pb(a[i]);
if (o) {
for (int i = 0; i < mid; i++) ret = Query(a[i]);
for (int i = 0; i < n; i++)
if (a1.size() == b1.size()) b2.pb(b[i]);
else if (a2.size() == b2.size()) b1.pb(b[i]);
else {
int now = Query(b[i]);
if (now != ret) b1.pb(b[i]);
else b2.pb(b[i]);
ret = now;
}
} else {
for (int i = mid; i < n; i++) ret = Query(a[i]);
for (int i = 0; i < n; i++)
if (a1.size() == b1.size()) b2.pb(b[i]);
else if (a2.size() == b2.size()) b1.pb(b[i]);
else {
int now = Query(b[i]);
if (now != ret) b1.pb(b[i]);
else b2.pb(b[i]);
ret = now;
}
}
work(a1, b1, 0), work(a2, b2, 1);
}
void Solve(int n) {
int ret = 0;
vi a, b;
for (int i = 1; i <= 2 * n; i++) {
int now = Query(i);
if (now != ret) a.pb(i);
else b.pb(i);
ret = now;
}
random_shuffle(a.begin(), a.end());
random_shuffle(b.begin(), b.end());
work(a, b, 1);
for (int i = 0; i < n; i++) Answer(a[i], f[a[i]]);
}
