一道 sb 题的 sb 做法

有 $n$ 座城市，第 $i$ 座城市里宝石的交易价格为 $a_i$。当你经过第 $i$ 座城市时，你可以以 $a_i$的价格购买或卖出一个宝石。在任意时刻，你最多只能携带一个宝石。

有 $m$ 次操作，操作分为两种：

  • 询问依次经过 $l$ 到 $r$ 的城市的城市能获得的最大收益。最后离开编号为 $r$ 的城市时，身上不能携带宝石；

  • 将 $l$ 到 $r$ 的宝石价格修改为一个首项为 $x$，公差为 $y$的等差数列；

$1 \le n ,m \le 2 \times 10^5$，$1 \le l \le r \le n$，$1 \le a_i,x \le 10^9$，$|y|\le10^4$

看到这个题感觉就是线段树，所以我们用线段树做。

主要的问题是询问操作不好维护，我们要思考怎么用两个儿子的答案合并出父亲的答案。

如果我们对于一个线段树节点只记录它这个区间的最大收益，显然是不能合并的。为什么？因为有种情况是走出左儿子后还剩下一个宝石，把这个宝石留到右儿子去卖。

为了处理这个情况，我们维护四个信息 $a\left[0/1\right]\left[0/1\right]$，一维的 $0/1$ 表示进入这个区间，即到了 $l$ 时时有没有宝石，二维的表示出这个区间的时候有没有宝石。然后合并就非常简单了：

接下来要考虑的问题就是修改。我们要想办法让修改区间覆盖一个线段树区间时 $\Theta(1)$ 修改。

其实很简单，两种情况：

  • $ y<0$，这时等差数列是递减的，所以
    • 前面买后面卖肯定是亏的，所以 $a[0][0]=0$；
    • 最后一个最小所以肯定在最后一个买，所以 $a[0][1]=x+y\times(r-l)$；
    • 第一个最大所以在第一个买最赚，所以 $a[1][0]=x$；
    • 在第一个卖，最后一个买最赚，所以 $a[1][1] = -y\times(r-l)$
  • $y > 0$，等差数列递增，读者自算不难；

然后这题就做完了。

CODE :

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
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;

#define int long long

inline int $() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c & 15), c = getchar();
	return f ? -x : x;
}

#define N 200010
#define INF (1e16)

int n, m, a[N];

struct node {
	int a[2][2];
	node (int x = -INF, int y = -INF, int z = -INF, int w = -INF) {
		a[0][0] = x, a[0][1] = y, a[1][0] = z, a[1][1] = w;
	}
};
node F(node x, node y) {
	node r;
	for (int i = 0; i <= 1; i ++) {
		for (int j = 0; j <= 1; j ++) {
			for (int k = 0; k <= 1; k ++) {
				r.a[i][j] = max(r.a[i][j], x.a[i][k] + y.a[k][j]);
			}
		}
	}
	return r;
}

#define lid (id << 1)
#define rid (id << 1 | 1)
#define mid (l + r >> 1)
struct Seg { node s; int x, y; }tr[N * 4];
void build(int id, int l, int r) {
	if (l == r) {
		return tr[id].s = node(0, -a[l], a[l], 0), void();
	}
	build(lid, l, mid), build(rid, mid + 1, r);
	tr[id].s = F(tr[lid].s, tr[rid].s);
}
void Calc(int id, int l, int r) {
	int x = tr[id].x, y = tr[id].y;
	if (y < 0) {
		tr[id].s = node(0ll, -(x + (r - l) * y), x, -y * (r - l));
	} else {
		tr[id].s = node(y * (r - l), -x, y * (r - l) + x, 0ll);
	}
}
void Down(int id, int l, int r) {
	if (l == r) return;
	if (tr[id].x == 0 && tr[id].y == 0) return;
	tr[lid].x = tr[id].x;
	tr[rid].x = tr[id].x + tr[id].y * (mid - l + 1);
	tr[lid].y = tr[rid].y = tr[id].y;
	tr[id].x = tr[id].y = 0;
	Calc(lid, l, mid), Calc(rid, mid + 1, r);
}
void Add(int id, int l, int r, int L, int R, int x, int y) {
	Down(id, l, r);
	if (L <= l && r <= R) {
		return tr[id].x = x, tr[id].y = y, Calc(id, l, r);
	}
	if (L <= mid) Add(lid, l, mid, L, R, x, y);
	if (R > mid) Add(rid, mid + 1, r, L, R, x + max(0ll, mid - max(l, L) + 1) * y, y);
	tr[id].s = F(tr[lid].s, tr[rid].s);
}
node Ask(int id, int l, int r, int L, int R) {
	Down(id, l, r);
	if (L <= l && r <= R) return tr[id].s;
	node lr, rr; int vl = 0, vr = 0;
	if (L <= mid) lr = Ask(lid, l, mid, L, R), vl = 1;
	if (R > mid) rr = Ask(rid, mid + 1, r, L, R), vr = 1;
	if (!vl) return rr;
	if (!vr) return lr;
	return F(lr, rr);
}

signed main() {
	freopen("gem.in", "r", stdin);
	freopen("gem.out", "w", stdout);
	n = $(), m = $();
	for (int i = 1; i <= n; i ++) a[i] = $();

	build(1, 1, n);
	for (int i = 1; i <= m; i ++) {
		int op = $(), l = $(), r = $(), x, y;
		if (op == 1) {
			printf("%lld\n", Ask(1, 1, n, l, r).a[0][0]);
		} else {
			x = $(), y = $(), Add(1, 1, n, l, r, x, y);
		}
	}
	return 0;
}
题解
数据结构 线段树

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！