徐皓天 / 博客
← 全部文章

JOISC 2019 题解

题解更新于 2020 年 7 月 28 日

本文目录（16 节）
  1. Day1
  2. 試験 (Examination)
  3. ビーバーの会合 (Meetings)
  4. ナン (Naan)
  5. Day2
  6. ふたつのアンテナ (Two Antennas)
  7. ふたつの料理 (Two Dishes)
  8. ふたつの交通機関 (Two Transportations)
  9. Day3
  10. 指定都市 (Designated Cities)
  11. ランプ (Lamps)
  12. 時をかけるビ太郎 (Bitaro, who Leaps through Time)
  13. Day4
  14. ケーキの貼り合わせ (Cake 3)
  15. 合併 (Mergers)
  16. 鉱物 (Minerals)

JOISC 2019

Day1

試験 (Examination)

裸的三维偏序模板题，O(nlog⁡2n)\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)

有意思的交互题。

考虑到 Query(x,y,z)\text{Query}(x,y,z) 有以下两种情况：

  • 若 x,y,zx,y,z 在一条链上，则返回中间的那个点。
  • 若 x,y,zx,y,z 不在一条链上，则返回以 xx 为根时的 LCA(y,z)\text{LCA}(y, z)。

考虑每次对于一个点集随机其中的一条链 (x,y)(x,y)，然后询问其他点与 x,yx,y 的答案。

答案相同的一定在一个子树内，是一个规模更小的子问题，可以递归分治。

同时被返回的所有值构成链上的所有点，同样是一个规模更小的子问题。

这个做法在菊花图的时候询问次数约为 n2n^2，但本题中最大度数为 1818，因此询问次数约为 18n18n。

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)

贪心。

对于每个人，求出其划分为 nn 等份的切割点。

对于第 ii 次切割，在还未选中的人中选择第 ii 份切割点最小的人。

时间复杂度 O(n(n+L))\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)

对于 ii，我们可以将其拆成在 i+aii+a_i 处出现，i+bi+1i+b_i+1 处消失的两个事件。

考虑从小到大枚举 jj，同时维护 did_i 表示 ii 的最大成本。

则每新加入一个 jj，我们要把当前存在的 ii 中 ∈[j−bj,j−aj]\in [j-b_j,j-a_j] 的 ii，将 did_i 对 ∣hi−hj∣|h_i-h_j| 取 max⁡\max。

对于询问 l,rl,r，答案就是枚举到 j=rj=r 时的 max⁡i=lrdi\max_{i=l}^{r} d_i。

接下来考虑如何维护这个过程。

首先那个绝对值可以去掉，正反做两次就可以了，不妨设此时要求 hi≥hjh_i \ge h_j。

然后对于每个 ii 再维护一个 cic_i，当其存在时 ci=hic_i = h_i，否则 ci=−∞c_i = -\infty。

那么加入一个 jj 时，我们就是要把 [j−bj,j−aj][j-b_j,j-a_j] 中的 dd 对 ci−hjc_i - h_j 取 max⁡\max。

这些都可以线段树实现，时间复杂度 O(nlog⁡n)\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)

首先有一个 O(nm)\mathcal O(nm) 的 DP。

设 fi,jf_{i,j} 表示完成了 II 的 ii 个步骤 JJ 的 jj 个步骤时的最高得分，有转移 fi,j=max⁡(fi−1,j+[sai+sbj≤si]pi,fi,j−1+[sai+sbj≤tj]qj) 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,sbsa,sb 分别是 a,ba,b 的前缀和。

考虑优化这个 DP。

将第一维看成时间轴，即从小到大枚举 ii，同时维护 fjf_j。

那么当枚举到 ii 时：

  • 将满足 sai+sbj≤sisa_i + sb_j \le s_i 的 jj，fjf_j 加上 pip_i。
    显然满足条件的 jj 是一个前缀。
  • 设 vj=[sai+sbj≤tj]qjv_j = [sa_i+sb_j \le t_j]q_j，将 fjf_j 与 fj−1+vjf_{j-1} + v_j 取 max⁡\max。
    注意 vjv_j 一定是先为 qjq_j 后为 00。

考虑维护 ff 的差分 gg，则两种操作分别改为：

  • 单点加。
  • 将 gjg_j 与 vjv_j 取 max⁡\max。
    注意 gg 是差分数组，所以 gj+1g_{j+1} 还要减去 gjg_j 取 max⁡\max 前后的差值。

再考虑所有的 wj=gj−vjw_j = g_j - v_j，则两种操作再改为：

  • 单点加。
  • 如果 vjv_j 要从 qjq_j 变为 00，则将 wjw_j 加上 qjq_j。
    如果 wj<0w_j < 0，则 wj+1w_{j+1} 加上 wjw_j，wjw_j 赋值为 00。

发现所有的操作都神奇地变成了是单点操作！

注意到 wj=0w_j = 0 的 jj 实际上并没有什么用，考虑用一个 set 维护所有 wj≠0w_j \ne 0 的 jj。

每次暴力修改涉及到的所有 gjg_j 即可，时间复杂度 O(nlog⁡n)\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/21/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)

存在一种最优策略为，赋值操作的区间两两不交，取反操作的区间两两不交，所有赋值操作在取反操作之前。

设 fi,0/1/2f_{i,0/1/2} 表示第 ii 位赋值为 0/10/1 或不赋值的情况下操作区间端点的最小个数，则最后答案除以 22 即可。

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)

首先把 ii 的时间减去 ii，则所有斜线移动都变成了横线。

把每个区间 [l,r][l,r] 看成一个二元组 (l,r)(l,r)，合并两个二元组 (l1,r1),(l2,r2)(l_1,r_1),(l_2,r_2) 有三种情况：

  • max⁡(l1,l2)≤min⁡(r1,r2)→(max⁡(l1,l2),min⁡(r1,r2))\max(l_1,l_2) \le \min(r_1,r_2) \to (\max(l_1,l_2), \min(r_1,r_2))。

  • r1<l2r_1 < l_2，l1<r2l_1 < r_2，这两种情况好像不能用二元组表示的样子。

那么，我们再设一个三元组 (l,r,k)(l,r,k) 表示从 ll 走进 rr 走出，中间使用技能次数为 kk。

此时既有二元组又有三元组，我们需要考虑所有合并的情况：

  • (l1,r1),(l2,r2)(l_1,r_1),(l_2,r_2)：
    • max⁡(l1,l2)≤min⁡(r1,r2)→(max⁡(l1,l2),min⁡(r1,r2))\max(l_1,l_2) \le \min(r_1,r_2) \to (\max(l_1,l_2), \min(r_1,r_2))。
    • r1<l2→(r1,l2,0)r_1 < l_2 \to (r_1,l_2,0)。
    • l1>r2→(l1,r2,l1−r2)l_1 > r_2 \to (l_1,r_2,l_1-r_2)。
  • (l1,r1),(l2,r2,k2)(l_1,r_1),(l_2,r_2,k_2)：
    • l1≤l2≤r1→(l2,r2,k2)l_1 \le l_2 \le r_1 \to (l_2,r_2,k_2)。
    • r1<l2→(r1,r2,k2)r_1 < l_2 \to (r_1,r_2,k_2)。
    • l1>l2→(l1,r2,k2+l1−l2)l_1 > l_2 \to (l_1,r_2,k_2+l_1-l_2)。
  • (l1,r1,k1),(l2,r2)(l_1,r_1,k_1),(l_2,r_2)：
    • l2≤r1≤r2→(l1,r1,k1)l_2 \le r_1 \le r_2 \to (l_1, r_1, k_1)。
    • r1<l2→(l1,l2,k1)r_1 < l_2 \to (l_1,l_2,k_1)。
    • r1>r2→(l1,r2,k1+r1−r2)r_1 > r_2 \to (l_1,r_2,k_1+r_1-r_2)。
  • (l1,r1,k1),(l2,r2,k2)(l_1,r_1,k_1),(l_2,r_2,k_2)：(l1,r2,k1+k2+max⁡(r1−l2,0))(l_1,r_2,k_1+k_2+\max(r_1-l_2, 0))。

线段树维护即可，时间复杂度 O(qlog⁡n)\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)

首先显然对 cc 排序后答案是某个区间的前 kk 大 vv 之和减去两倍的 cc 之差。

然而显然我们不需要考虑所有区间，可能成为答案的区间满足决策单调性，只有 O(n)\mathcal O(n) 个。

然后区间前 kk 大和用个主席树就行了，总时间复杂度 O(nlog⁡2n)\mathcal O(n \log^2 n)。

由于第一次写决策单调性，这里记一下步骤：

建一个队列，里面保存三元组 (l,r,x)(l,r,x)，表示当前情况下 l∼rl \sim r 的最优决策在 xx。

从小到大枚举 ii：

  1. 若队头的 r<ir < i，则弹出队头。
  2. 用此时的队头作为最优决策转移到 ii。
  3. 不断弹出比 ii 更劣的队尾。
  4. 若此时队尾比 ii 优，则直接将 ii 补在队尾。
  5. 否则在队尾上二分找到第一个以 ii 为最优决策点的位置，改变队尾的 rr 值，同时插入 ii。
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)

显然把同一个州用并查集整到一坨里，然后剩下的依然是个树。

问题变成用最少的路径覆盖一棵树的所有边，贪心一下，设叶子数为 cc，答案就是 ⌊c+12⌋\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)

首先用 2n2n 次将所有元素划分成两个内部没有相同元素的集合 A,BA,B。

考虑分治，对于 mm 个元素的集合 A,BA,B，将 AA 的一半与 BB 的每一个一起询问。

设 ii 个点的询问次数为 f(i)f(i)，最优情况下可以做到 f(i)=2f(i2)+32if(i) = 2f(\frac i2) + \frac 32i。

n=4.3×104n = 4.3 \times 10^4 时 f(n)=1020892f(n) = 1020892，无法 AC，但能拿 8585 分。

考虑不那么平均地分配 AA 的「一半」。

假如我们选择了 AA 中 ∣A∣×p|A| \times p 的数，则 f(i)=f(pi)+f((1−p)i)+(1+p)if(i) = f(pi) + f((1-p)i) + (1+p)i。

取 p=0.37p=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]]);
}

标签：CDQ 分治、DP、二分、二分图、交互题、决策单调性、前缀和/差分、可持久化、并查集、换根 DP、树形 DP、树状数组、线段树、贪心、随机化

评论

    填写昵称即可留言。评论经站主审核后公开，请勿提交私人信息。

    正在连接评论服务…