zqs`s blog

有朋自远方来，虽远必诛

3/5练习赛题解

发表于 更新于 分类于 Valine：

A：

看起来很签到,写起来很恶心

不过貌似我写的代码是全场最长

类似最大连续和，线段树维护一下最大前缀，最大后缀，最大子段。我的代码里面需要维护一下最大前缀开头的数字是多少，最大后缀开头的数字是多少（所以就有了sub0,sub1,suf0,suf1）。

然后就是码农了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
wrnm，这题出题人没有horse实锤了 
等等，就我一个人写了这么长吗，wtcl 
*/

#include <cstdio>

inline int max(const int x, const int y) {return x > y ? x : y;}
struct Node {
	int l, r, v, sub0, sub1, suf0, suf1;
} c[1000005];
int a[200005];
void make_tree(const int O, const int L, const int R) {
	c[O].l = L, c[O].r = R, c[O].v = c[O].sub0 = c[O].suf0 = 1;
	if (L != R) {
		make_tree(O << 1, L, L + R >> 1);
		make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
	}
}
inline void pushup(const int O) {
	#define ls c[O << 1]
	#define rs c[O << 1 | 1]
	const int llen(ls.r - ls.l + 1), rlen(rs.r - rs.l + 1);
	c[O].sub0 = c[O].sub1 = c[O].suf0 = c[O].suf1 = c[O].v = 0;
	if (ls.suf0 == llen) {
		if (!a[ls.l]) c[O].sub0 = max(c[O].sub0, llen + rs.sub1);
		else c[O].sub1 = max(c[O].sub1, llen + rs.sub1);
	}
	if (ls.suf1 == llen) {
		if (!a[ls.l]) c[O].sub0 = max(c[O].sub0, llen + rs.sub0);
		else c[O].sub1 = max(c[O].sub1, llen + rs.sub0);
	}
	if (rs.sub0 == rlen) {
		if (!a[rs.r]) c[O].suf0 = max(c[O].suf0, rlen + ls.suf1);
		else c[O].suf1 = max(c[O].suf1, rlen + ls.suf1);
	}
	if (rs.sub1 == rlen) {
		if (!a[rs.r]) c[O].suf0 = max(c[O].suf0, rlen + ls.suf0);
		else c[O].suf1 = max(c[O].suf1, rlen + ls.suf0);
	}
	c[O].sub0 = max(c[O].sub0, ls.sub0);
	c[O].sub1 = max(c[O].sub1, ls.sub1);
	c[O].suf0 = max(c[O].suf0, rs.suf0);
	c[O].suf1 = max(c[O].suf1, rs.suf1);
	c[O].v = max(max(ls.v, rs.v), max(ls.suf0 + rs.sub1, ls.suf1 + rs.sub0));
	#undef ls
	#undef rs
}

void update(const int O, const int p) {
	if (c[O].l == c[O].r) {
		if (a[p] == 0) c[O].sub1 = c[O].suf1 = a[p] = 1, c[O].sub0 = c[O].suf0 = 0;
		else c[O].sub0 = c[O].suf0 = 1, c[O].sub1 = c[O].suf1 = a[p] = 0;
		return;
	}
	const int mid(c[O].l + c[O].r >> 1);
	if (p <= mid) update(O << 1, p);
	else update(O << 1 | 1, p);
	pushup(O);
}

int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	make_tree(1, 1, n);
	while (q --) {
		int x;
		scanf("%d", &x);
		update(1, x);
		printf("%d\n", c[1].v);
	}
}

B:

被C题耽误了，没时间想。。。

不难想到给 $A$ 数组排个序，这样可以线段树上二分出当前第一个 $\ge b$ 的位置 $pos$。将 $[pos,n]$ 这段区间设为 $b$ 即可。然后每一次操作都要整体加一下，因此线段树需要写区间赋值，区间加。因为只求总共割掉了多少，因此直接看根节点的值就行了。注意由于要在线段树上二分，所以为了方便我记了一个最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <algorithm>
#define int long long

typedef long long ll;

inline int max(const ll x, const ll y) {return x > y ? x : y;}
struct Node {
	ll l, r, v, mx, Lazy1, Lazy2;
} c[2000005];
ll a[500005], s[500005];
inline void pushdown(const int O) {
	const ll llen(c[O << 1].r - c[O << 1].l + 1), rlen(c[O << 1 | 1].r - c[O << 1 | 1].l + 1);
	if (c[O].Lazy2 != -1) {
		c[O << 1].Lazy2 = c[O << 1 | 1].Lazy2 = c[O].Lazy2;
		c[O << 1].v = llen * c[O].Lazy2, c[O << 1 | 1].v = rlen * c[O].Lazy2;
		c[O << 1].mx = c[O << 1 | 1].mx = c[O].Lazy2;
		c[O << 1].Lazy1 = c[O << 1 | 1].Lazy1 = 0LL;
	}
	c[O << 1].v += (s[c[O << 1].r] - s[c[O << 1].l - 1]) * c[O].Lazy1;
	c[O << 1].Lazy1 += c[O].Lazy1;
	c[O << 1 | 1].v += (s[c[O << 1 | 1].r] - s[c[O << 1 | 1].l - 1]) * c[O].Lazy1;
	c[O << 1 | 1].Lazy1 += c[O].Lazy1;
	c[O << 1].mx += c[O].Lazy1 * a[c[O << 1].r], c[O << 1 | 1].mx += c[O].Lazy1 * a[c[O].r];
	c[O].Lazy1 = 0LL, c[O].Lazy2 = -1LL;
}
inline void pushup(const int O) {
	c[O].v = c[O << 1].v + c[O << 1 | 1].v;
	c[O].mx = max(c[O << 1].mx, c[O << 1 | 1].mx);
}
void make_tree(const int O, const int L, const int R) {
	c[O].l = L, c[O].r = R, c[O].Lazy2 = -1LL;
	if (L != R) {
		make_tree(O << 1, L, L + R >> 1);
		make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
	}
}
void Set(const int O, const int L, const int R, const ll d) {
	if (L > R) return;
	if (L <= c[O].l && c[O].r <= R) {
		c[O].v = d * (c[O].r - c[O].l + 1);
		c[O].Lazy1 = 0LL, c[O].Lazy2 = c[O].mx = d;
		return;
	}
	const int mid(c[O].l + c[O].r >> 1);
	pushdown(O);
	if (L <= mid) Set(O << 1, L, R, d);
	if (mid < R) Set(O << 1 | 1, L, R, d);
	pushup(O);
}
void update(const int O, const int L, const int R, const ll d) {
	if (L <= c[O].l && c[O].r <= R) {
		c[O].v += d * (s[c[O].r] - s[c[O].l - 1]);
		c[O].Lazy1 += d, c[O].mx += a[c[O].r] * d;
		return;
	}
	const int mid(c[O].l + c[O].r >> 1);
	pushdown(O);
	if (L <= mid) update(O << 1, L, R, d);
	if (mid < R) update(O << 1 | 1, L, R, d);
	pushup(O);
}
int query(const int O, const int x) {
	if (c[O].mx <= x) return c[O].r + 1;
	if (c[O].l == c[O].r) return c[O].l;
	pushdown(O);
	if (c[O << 1].mx > x) return query(O << 1, x);
	return query(O << 1 | 1, x);
}

signed main() {
	int n, m, pred(0);
	scanf("%lld%lld", &n, &m);
	for (int i(1); i <= n; ++ i) scanf("%lld", a + i);
	std::sort(a + 1, a + n + 1);
	for (int i(1); i <= n; ++ i) s[i] = s[i - 1] + a[i];
	make_tree(1, 1, n);
	while (m --) {
		ll d, b;
		scanf("%lld%lld", &d, &b);
		update(1, 1, n, d - pred);
		pred = d;
		ll t(c[1].v);
		Set(1, query(1, b), n, b);
		printf("%lld\n", t - c[1].v);
	}
	return 0;
}

C:

考场上送我爆零的题。

考虑暴力。自然就是 $dp_{i,j}$ 表示完成了前 $i$ 个操作，其中位置不在 $x_i$ 上的棋子的位置为 $j$。对于所有的 $dp_{i,j}$，$dp_{i,j}=dp_{i-1,j}+abs(x_i-x_{i-1})$。对于 $dp_{i,x_{i-1}}$，$dp_{i,x_{i-1}}=min(dp_{i-1,j}+abs(x_i-j))$。展开绝对值分类讨论即可。

滚动dp数组然后，对于每个操作，$dp$ 数组先整体加上 $abs(x_i-x_{i-1})$。单独考虑 $dp_{i,x_{i-1}}$。这里对于 $j\le x_i$ 的取一个min,对于 $j\ge x_i$ 取一个min。显然两颗线段树优化。

草稿本上的式子抄错调了2h无果，不愧是我。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <cstdio>
#include <cstdlib>
#define Tree1 Tree[0]
#define Tree2 Tree[1]
#define Tree3 Tree[2]
#define int long long
#define INF 100000000000000000LL

inline int min(const int x, const int y) {return x < y ? x : y;}
inline int abs(const int k) {return k >= 0 ? k : -k;}
int x[200005], tot;
struct Segment_tree {
	struct Node {
		int l, r, v, Lazy;
	} c[1000005];
	void make_tree(const int O, const int L, const int R) {
		c[O].l = L, c[O].r = R, c[O].v = INF;
		if (L != R) {
			make_tree(O << 1, L, L + R >> 1);
			make_tree(O << 1 | 1, (L + R >> 1) + 1, R);
		}
	}
	void pushdown(const int O) {
		c[O << 1].v += c[O].Lazy, c[O << 1].Lazy += c[O].Lazy;
		c[O << 1 | 1].v += c[O].Lazy, c[O << 1 | 1].Lazy += c[O].Lazy;
		c[O].Lazy = 0LL;
	}
	void update(const int O, const int p, const int d) {
		if (c[O].l == c[O].r) {c[O].v = min(c[O].v, d); return;}
		pushdown(O);
		const int mid(c[O].l + c[O].r >> 1);
		if (p <= mid) update(O << 1, p, d);
		else update(O << 1 | 1, p, d);
		c[O].v = min(c[O << 1].v, c[O << 1 | 1].v);
	}
	void Add(const int O, const int L, const int R, const int d) {
		if (L > R) return;
		if (L <= c[O].l && c[O].r <= R) {c[O].v += d, c[O].Lazy += d; return;}
		const int mid(c[O].l + c[O].r >> 1);
		pushdown(O);
		if (L <= mid) Add(O << 1, L, R, d);
		if (mid < R) Add(O << 1 | 1, L, R, d);
		c[O].v = min(c[O << 1].v, c[O << 1 | 1].v);
	}
	int query(const int O, const int L, const int R) {
		if (L > R) return INF;
		if (L <= c[O].l && c[O].r <= R) return c[O].v;
		const int mid(c[O].l + c[O].r >> 1);
		pushdown(O);
		int ans(INF);
		if (L <= mid) ans = min(ans, query(O << 1, L, R));
		if (mid < R) ans = min(ans, query(O << 1 | 1, L, R));
		return ans;
	}
} Tree[3];

signed main() {
	int n, q, A, B;
	scanf("%lld%lld%lld%lld", &n, &q, &A, &B);
	Tree1.make_tree(1, 1, n);
	Tree2.make_tree(1, 1, n);
	Tree3.make_tree(1, 1, n);
	x[tot = 1] = A;
	Tree1.update(1, B, -B);
	Tree2.update(1, B, B);
	Tree3.update(1, B, 0);
	while (q --) {
		++ tot; 
		scanf("%lld", &x[tot]);
		int ret(min(x[tot] + Tree1.query(1, 1, x[tot]), Tree2.query(1, x[tot], n) - x[tot])), add();
		for (int i(0); i <= 2; ++ i)
			Tree[i].Add(1, 1, n, abs(x[tot] - x[tot - 1]));
		Tree1.update(1, x[tot - 1], ret - x[tot - 1]);
		Tree2.update(1, x[tot - 1], ret + x[tot - 1]);
		Tree3.update(1, x[tot - 1], ret);
	}
	printf("%lld", Tree3.query(1, 1, n));
	return 0;
}
-------------本文结束感谢您的阅读-------------