Auto comment: topic has been updated by Ragnar7 (previous revision, new revision, compare).

Check this out https://youtu.be/FAQxdm0bTaw

If you want to brute force this, let $$$dp_i$$$ denote the maximum score you can get if the last 1 you placed was at $$$i$$$. Now consider transitions from $$$dp_j$$$. it is $$$dp_i = max(dp_i, dp_j + s)$$$, where $$$s$$$ is the sum of all ranges such that $$$j<l$$$ and $$$i<r$$$. To maintain this information, we use a lazy segment tree that allows range increments and maximums. We iterate over $$$i$$$ from $$$1$$$ to $$$n$$$. When there is a range whose $$$l\le i$$$, we update the range $$$[0,l)$$$ with the value of the range, as those dp values will now have this range added to their $$$s$$$ value. When there is a range whose $$$r<i$$$, we undo the range update $$$[0,l)$$$ with $$$-val$$$, because this range no longer contributes to the $$$s$$$ value. We can implement this by sorting and 2 pointers.

//Rangesbyl and r is sorted by l and r values respectively.
ll ans = 0;
for(int i=1,j=0,k=0;i<=n;i++){
    while(k<m && rangesbyl[k].l<=i){
        segtree.updaterange(0,rangesbyl[k].l-1, rangesbyl[k].val);
        ++k;
    }
    while(j<m && rangesbyr[j].r<i){
        segtree.updaterange(0,rangesbyr[j].l-1, -rangesbyr[j].val);
        ++j;
    }
    ll curr = segtree.query(0,i-1);
    ans = max(ans, curr);
    segtree.updaterange(i,i,curr);
}