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;
}