题目

点这里看题目。

分析

不妨先认为 \(C_i=1\)。首先破环为链，则原问题等价于：

你有一个长度为 \(n\) 的序列 \(a\) 和 \(m\) 个二元组 \((l_i,r_i)\)。一开始时，\(a_i=0\)。

对于每个二元组 \((l_i,r_i)\)，你可以选择：

1. （原始操作）\(\forall l_i\le x<r_i\)，令 \(a_x\gets a_x+1\)。

2. （反转操作）\(\forall 1\le x<l_i\lor r_i\le x\le n\)，令 \(a_x\gets a_x+1\)。

最终你需要最小化 \(\max a\)。

一眼二分，但先别急。我们尝试枚举 \(c\) 为选择反转操作的二元组数量，则可以将所有二元组操作都归约为对 \([l_i,r_i)\) 中的数操作。更进一步地，相当于是：

你有一个长度为 \(n\) 的序列 \(a\) 和 \(m\) 个二元组 \((l_i,r_i)\)。一开始时，\(a_i=c+\sum_{k}[l_k\le i<r_k]\)。

对于每个二元组 \((l_i,r_i)\)，你可以选择不操作，也可以选择将下标在 \([l_i,r_i)\) 中的 \(a\) 全部减 \(2\)。执行减 \(2\) 操作的区间个数 \(\le c\)。

最终你需要最小化 \(\max a\)。

此时再二分，检查时可以从左到右扫描。需要将 \(a_i\) 变小时，就贪心地取右端点最大的区间进行操作。复杂度为 \(O(m(n+m)\log^2m)\)。

从更宏观的角度，二分的判断结果仅由 \(c\) 和二分值 \(v\) 影响，记其为 \(f(c,v)\)。我们需要找出存在 \(c\) 使得 \(f(c,v)=1\) 的最小的 \(v\)。

打个表吧，发现 \(f(c,v)\) 的图形很漂亮，似乎是一个凸形。不过，因为我们只需要检查 \(c\) 的存在性，所以我们考察特定的 \(c\)。

考虑使得 \(f(0,v)=1\) 的最小的 \(v\)，可以发现其就是 \(b=\max_{1\le i\le n}\sum_{k}[l_k\le i<r_k]\)。通过打表，可以发现对于特定的 \(v\)，存在使得 \(f(c,v)=1\) 的 \(c\)，则 \(b-v\le c\le b-v+1\)。依靠这个结论，算法的复杂度即可优化到 \(O(m(n+m)\log^2m)\)。

Remark.

可以看到，此结论和其它题解的结论是本质相同的。只不过此处用了一种比较合乎思维逻辑的方法给出。

既然如此，证明这里就先不写了，参考其它题解吧。

当 \(C_i\neq 1\) 时，问题本质上和 \(C_i=1\) 相同。只需要在检查时将相同的右端点压缩在一起处理即可。复杂度不变。

代码

#include <queue>
#include <cstdio>
#include <vector>
#include <iostream>

#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )

typedef long long LL;

const int MAXN = 2e5 + 5;

template<typename _T>
inline void Read( _T &x ) {
    x = 0; char s = getchar(); bool f = false;
    while( s < '0' || '9' < s ) { f = s == '-', s = getchar(); }
    while( '0' <= s && s <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar(); }
    if( f ) x = -x;
}

template<typename _T>
inline void Write( _T x ) {
    if( x < 0 ) putchar( '-' ), x = -x;
    if( 9 < x ) Write( x / 10 );
    putchar( x % 10 + '0' );
}

typedef std :: pair<int, LL> Node;

std :: vector<int> rng[MAXN];
std :: priority_queue<Node> q;

LL low[MAXN], tag[MAXN];

int lef[MAXN], rig[MAXN], wei[MAXN];

int N, M;

inline bool Chk( const LL &c, const LL &r ) {
    while( ! q.empty() ) q.pop();
    LL used = 0;
    rep( i, 1, N ) tag[i] = 0;
    rep( i, 1, N ) {
        tag[i] += tag[i - 1];
        LL cur = low[i] + c + tag[i];
        for( const int &j : rng[i] )
            q.push( { rig[j], wei[j] } );
        while( cur > r ) {
            if( q.empty() || q.top().first <= i ) 
                return false;
            Node h = q.top(); q.pop();
            LL ned = std :: min( ( cur - r + 1 ) >> 1, h.second );
            h.second -= ned, cur -= 2 * ned; 
            tag[i] -= 2 * ned, tag[h.first] += 2 * ned;
            if( ( used += ned ) > c ) return false;
            if( h.second > 0 ) q.push( h );
        }
    }
    return used <= c;
}

int main() {
    Read( N ), Read( M );
    rep( i, 1, M ) {
        Read( lef[i] ), Read( rig[i] ), Read( wei[i] );
        if( lef[i] == rig[i] ) { i --; continue; }
        if( lef[i] > rig[i] ) std :: swap( lef[i], rig[i] );
        low[lef[i]] += wei[i], low[rig[i]] -= wei[i];
        rng[lef[i]].push_back( i );
    }
    LL l = 0, r = 0, mx = 0, mid;
    rep( i, 1, N ) low[i] += low[i - 1];
    rep( i, 1, N ) mx = std :: max( mx, low[i] );
    r = mx;
    while( l < r ) {
        mid = ( l + r ) >> 1;
        if( Chk( mx - mid, mid ) || 
            Chk( mx - mid + 1, mid ) ) r = mid;
        else l = mid + 1;
    }
    Write( l ), putchar( '\n' );
    return 0;
}