Editorial for Atcoder Educational DP Contest W - Intervals
Submitting an official solution before solving the problem yourself is a bannable offence.
Gọi ~dp[i]~ là số điểm tối đa có thể đạt được của xâu đang xét với bit thứ ~i~ được bật lên.
Ta có: ~dp[i] = max(dp[j] + cost(i, j))~ Với ~j < i~ và ~cost(i, j)~ là tổng ~a_x~ với ~x~ thỏa mãn ~i~ nằm trên đoạn ~[l_x, r_x]~ còn ~j~ nằm ngoài đoạn ~[l_x, r_x]~. Cách trên có độ phức tạp ~O(n^2)~, tuy nhiên không phù hợp với giới hạn thời gian mà đề bài đưa ra.
Để giảm chi phí khi tính toán ~cost(i, j)~, ta áp dụng thuật toán Sweep line. Xét sự biến đổi từ ~cost(j, i - 1)~ sang ~cost(j, i)~ khi ta di chuyển từ ~i - 1~ sang ~i~:
- Nếu tồn tại đoạn có ~l_x = i~ thì lúc này giá trị của ~cost~ sẽ tăng lên ~a_x~.
- Nếu tồn tại đoạn có ~r_x = i - 1~ (tức ~r_x + 1 = i~) mà ~j < l_x~, lúc này giá trị của cost sẽ bị giảm đi ~a_x~.
Như vậy, ta nhận thấy có thể chia mỗi đoạn thẳng thành ~2~ sự kiện: thêm và bớt. Ta sẽ duyệt ~i~ từ ~1~ đến ~n~. với mỗi đoạn ~[l_x, r_x]~, sự kiện thêm sẽ diễn ra tại thời điểm ~i = l_x~, và sự kiện bớt sẽ diễn ra tại thời điểm ~i = r_x + 1~:
- Tại sự kiện thêm, mọi giá trị ~cost(j, i)~ với ~j < i~ sẽ được tăng thêm bằng tổng ~a_x~ tại vị trí ~i~.
- Tại sự kiện bớt, với đoạn ~[l_x, r_x]~ ~(r_x + 1 = i)~, giá trị của ~cost(j, i)~ với ~j < l_x~ sẽ giảm đi ~a_x~.
Với việc xử lý như trên, ta có thể thấy việc tăng giảm cost sẽ diễn ra trên các đoạn (ở sự kiện thêm là đoạn ~[0, i - 1]~ và sự kiện bớt là ~[0, l_x - 1]~), do đó ta có ý tưởng giúp giảm độ phức tạp cho bài bằng cách sử dụng cấu trúc dữ liệu Segment Tree với kỹ thuật Lazy Propagation.
Ngoài ra để tính được mảng ~dp~ nhanh, Segment Tree của ta sẽ ko chỉ lưu ~cost(j, i)~ tại vị trí ~j~, mà sẽ lưu ~dp[j] + cost(j, i)~ trại vị trí ~j~, như vậy cây của ta sẽ cần thao tác update tăng đoạn và truy vấn max của một đoạn.
Đáp án cân tìm là ~max(dp[i])~ với mọi ~i~ từ ~1~ đến ~n~.
#include <bits/stdc++.h> using namespace std; using ll = long long; const int maxn = (int)2e5 + 10; const ll inf = (ll)1e15; struct Range { int l; ll value; }; int n, m; ll add_events[maxn]; vector<Range> remove_events[maxn]; ll tree[maxn * 4], lazy[maxn * 4]; void push_lazy(int i, int l, int r) { tree[i] += lazy[i]; if (l < r) { lazy[2 * i] += lazy[i]; lazy[2 * i + 1] += lazy[i]; } lazy[i] = 0; } void it_update(int from, int to, ll delta, int i, int l, int r) { push_lazy(i, l, r); if (from > r || l > to) return; if (from <= l && r <= to) { lazy[i] += delta; push_lazy(i, l, r); return ; } int mid = (l + r) / 2; it_update(from, to, delta, 2 * i, l, mid); it_update(from, to, delta, 2 * i + 1, mid + 1, r); tree[i] = max(tree[2 * i], tree[2 * i + 1]); } ll it_query(int from, int to, int i, int l, int r) { push_lazy(i, l, r); if (from > r || l > to) return -inf; if (from <= l && r <= to) return tree[i]; int mid = (l + r) / 2; return max(it_query(from, to, 2 * i, l, mid), it_query(from, to, 2 * i + 1, mid + 1, r)); } void it_update(int from, int to, ll delta) { it_update(from, to, delta, 1, 0, n); } ll it_query(int from, int to) { return it_query(from, to, 1, 0, n); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < m; ++i) { int l, r; ll a; cin >> l >> r >> a; add_events[l] += a; remove_events[r + 1].push_back(Range{l, a}); } ll ans = 0; for (int i = 1; i <= n; ++i) { it_update(0, i - 1, add_events[i]); for (Range cur_range: remove_events[i]) { it_update(0, cur_range.l - 1, -cur_range.value); } ll cur_dp = it_query(0, i - 1); it_update(i, i, cur_dp); ans = max(ans, cur_dp); } cout << ans; return 0; }
Comments