TIOJ-1976

發表於 更新於 Disqus：

給你$N$個線段$[l, r](1\le l\le r\le M)$，每條線段都有權重$w$。

可以選擇一段區間$[s, t](s, t\in \mathbb{Z})$，並且價值為所有與這段區間有交集的權重總和。

輸出最大可能價值。

$1\le N\le 10^5, 0\le M\le 10^9, -1000\le w\le 1000$

子題中有其中一筆是l=r，可以讓人聯想到最大區間和問題。
不過我還是沒想法，所以只能問人QQ。
後來得知的作法是:枚舉最大連續和的右界$t$，注意到如果右界進入某條線段，那當前總和就要加上他的權重。

如果右界離開了某個線段，他就會變成可能被選到的線段(因為如果左界$s$超過那條線段的$r$就會選到那條線段)。

所以可以用一個線段樹，只要離開某條線段就把區間[0, r](1 indexed)給加上他的權重。
左界就是線段樹詢問RMQ問[0, i]的最大值。
然而座標範圍很大，必須離散化，如果單單只存左右端點就會爛掉(範測2就是反例)。
所以我的做法是把左端點+1和右端點+1都給放到離散後的座標軸。
複雜度$\mathcal{O}(NlogN)$

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
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
const int INF     = 0x3F3F3F3F;
/*--------------------------------------------------------------------------------------*/

struct line {
	int l, r, c;
};

const int N = 4e5 + 25;
struct segtree {
	int arr[N << 1], tag[N], n;
	void init(int _n) { n = _n; }
	void upd(int p, int v) {
		arr[p] += v;
		if(p < n)
			tag[p] += v;
	}
	void push(int p) {
		for(int h = __lg(p); ~h; h--) {
			int i = p >> h;
			if(!tag[i >> 1])
				continue;
			upd(i, tag[i >> 1]);
			upd(i ^ 1, tag[i >> 1]);
			tag[i >> 1] = 0;
		}
	}
	void pull(int p) {
		for(; p > 1; p >>= 1)
			arr[p >> 1] = max(arr[p], arr[p ^ 1]) + tag[p >> 1];
	}
	void edt(int l, int r, int v) {
		int tl = l + n, tr = r + n - 1;
		push(tl);
		push(tr);
		for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				upd(l++, v);
			if(r & 1)
				upd(--r, v);
		}
		pull(tl);
		pull(tr);
	}
	int que(int l, int r) {
		push(l += n);
		push((r += n) - 1);
		int res = -INF;
		for(; l < r; l >>= 1, r >>= 1) {
			if(l & 1)
				res = max(res, arr[l++]);
			if(r & 1)
				res = max(res, arr[--r]);
		}
		return res;
	}
} tree;

signed main() { EmiliaMyWife
	int n;
	cin >> n;
	vector<line> arr(n);
	vector<int> v;
	for(int i = 0; i < n; i++)
		cin >> arr[i].l >> arr[i].r >> arr[i].c;
	for(int i = 0; i < n; i++) {
		v.push_back(arr[i].l);
		v.push_back(arr[i].r);
		v.push_back(arr[i].l + 1);
		v.push_back(arr[i].r + 1);
	}
	sort(v.begin(), v.end());
	v.resize(unique(v.begin(), v.end()) - v.begin());
	int m = v.size();
	for(int i = 0; i < n; i++) {
		arr[i].l = lower_bound(v.begin(), v.end(), arr[i].l) - v.begin();
		arr[i].r = lower_bound(v.begin(), v.end(), arr[i].r) - v.begin();
	}
	vector<vector<int>> enter(m), left(m + 1);
	for(int i = 0; i < n; i++) {
		enter[arr[i].l].push_back(arr[i].c);
		left[arr[i].r + 1].push_back(arr[i].c);
	}
	int ans = 0, sum = 0;
	tree.init(m + 1);
	for(int i = 0; i < m; i++) {
		for(int v : enter[i])
			sum += v;
		for(int v : left[i]) {
			sum -= v;
			tree.edt(0, i, v);
		}
		ans = max(ans, sum + tree.que(0, i + 1));
	}
	cout << ans << '\n';
}