题目

点这里看题目。

分析

有一定难度的题目，但是可以说问题的限制是比较常见的。

Subtask 3

也就在这个 subtask 上面有所突破

所有糖果盒子的容量相等，不妨设这个值为 \(c\)。

问题的结构是“区间修改、单点查询”，这里我们可以扫描序列，在端点处插入或删除修改，从而具体地拿出每个糖果盒子面对的修改。

接着考虑修改本身的特点。我们可以将多个修改的接连进行等价看作函数复合，则不难发现修改没有交换律，因此我们必须保证解决询问时，修改是有序的。

不难想到直接使用线段树来维护修改集合，这样我们需要做的是快速函数复合。

先来考虑一个更简单的模型：给定一个修改序列，如何求出初始糖果数为 \(w\) 时，经过修改后的最终值？

称某一次操作后 \(p+v_j>c_i\) 为“碰上壁”，某一次操作后 \(p+v_j<0\) 为碰下壁。首先，对于修改序列，我们可以找出 \(w\) 的区间 \([l_0,r_0]\)，使得当且仅当 \(w\in [l_0,r_0]\) 时，\(w\) 不会碰壁，此时可以直接算出结果为 \(w+\sum v\)。

否则 \(w\) 会碰壁，但是如果我们可以找出 \(w\) 最后一次碰壁的位置，我们就可以直接越过所有碰壁过程而计算最终结果。这个东西一时半会儿算不出来，我们间接地先考虑第一次碰壁，这个很容易用二分求解。如果第一次碰了上壁，则值得注意的一点是，从 \(w=c\) 出发也一定会在同一个位置碰上壁，因此在这次碰壁之后，\(w=c\) 的路线和 \(w\) 原本的路线就是一致的，我们可以直接调用 \(w=c\) 这条路线最后一次碰壁的位置（假如我们可以做到），从而算出 \(w\) 的结果。

第一次碰了下壁的情况类似，调用 \(w=0\) 的即可。因此，对于一个序列，我们需要求出：

• \([l_0,r_0]\) 和 \(\sum v\)；
• \(w=c\) 和 \(w=0\) 时最后一次碰上壁的位置；

这些信息可以在线段树上很方便地合并（合并过程需要二分），因此可以 \(O(q\log_2^2n)\) 解决。

比正解难写，比正解慢 ??

正解

前面的扫描线思路是没有问题的，问题在于我们没有必要动态维护答案，只需要解决 \(n\) 次询问。

我们尝试改写一下答案的形式。还是认为我们有了一个长度为 \(m\) 修改序列，第 \(k\) 次的参数为 \(v_k\)。

两个限制我们先挑简单的解决，那当然是 \(\max\{0,p+v_k\}\) 的限制容易。考虑按照操作编号和操作结束后糖果数构成坐标，并且画出轨迹。则每次碰下壁一定会导致轨迹上移，最终结果更大。因此，我们设 \(f(c,k)\) 为容量限制为 \(c\)，从第 \(k\) 个操作开始，且不考虑下界时的最终糖果数，则答案为 \(\max_{1\le k\le m}\{f(c,k)\}\)。

再考虑 \(f(c,k)\) 怎么求。类似的，我们发现每次碰下壁就会导致轨迹下移，且最终结果更小。设 \(s_k=\sum_{j=k}^mv_j\)，则可以得到 \(f(c,k)=\min\{s_k,\min_{k\le j\le m}s_j+c\}\)。

最终我们需要求的是：

\[\max_{1\le k\le m}\{\min\{s_k,\min_{k\le j\le m}s_j+c\}\} \]

想个办法把 \(\max\) 化掉，所以我们可以尝试随便提两个元素出来比大小。取 \(1\le k_1\le k_2\le m\)，则一定有 \(\min_{k_1\le j\le m}s_j\le \min_{k_2\le j\le m}\)。如果还有 \(s_{k_1}\le s_{k_2}\)，则 \(k_1\) 劣于 \(k_2\)，我们不需要考虑 \(k_1\)。

因此，有效的 \(k_2\) 对应了 \(s\) 的后缀最大值。当然，更简单的做法是直接求：

\[\max_{1\le k\le m}\{\min\{\max_{k\le j\le m}s_k,\min_{k\le j\le m}s_j + c\}\} \]

注意到 \(\min\) 中的两项都是单调的，并且彼此异调，因此 \(\max\) 一定取在大小关系交换处。线段树上维护后缀最值，二分找出断点即可。

时间复杂度为 \(O((n+q)\log n)\)。

主体思路

graph TB lmt1(区间修改单点查询)-->pnt1(扫描线) lmt2(复合性,保序要求)-->pnt2(线段树) pnt1-->pnt2 subgraph "Subtask 3" pnt3(试图合并修改)-->pnt4(观察第一次碰壁)-->pnt10(碰壁单调性) end pnt2-->pnt3 subgraph std pnt5(数学化目标)-->pnt6(用'枚举'方式改写限制) lmt3(min,max 限制)--分步处理限制-->pnt6 pnt6--整理-->pnt7(初步的求值式子)==主动消项,用单调性去掉没用的项==>pnt8(简化的求值式子) pnt8--异调 min 最值-->pnt9(线段树二分断点) end pnt2-->pnt9 pnt9-->final(正解)

代码

#include "candies.h"

#include 
#include 

#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;
typedef std :: vector Vec;

namespace Studio {
    const  LL INF = 1e18;
    const int MAXN = 2e5 + 5;
    
    template
    _T MIN( const _T a, const _T b ) {
        return a < b ? a : b;
    }

    template
    _T MAX( const _T a, const _T b ) {
        return a > b ? a : b;
    }

    std :: vector que[MAXN];

    LL su[MAXN << 2], sufMn[MAXN << 2], sufMx[MAXN << 2];

    int qL[MAXN], qR[MAXN], qV[MAXN]; 
    LL ans[MAXN];

    int C[MAXN];

    int N, Q;

    inline void Upt( const int x ) {
        su[x] = su[x << 1] + su[x << 1 | 1];
        sufMn[x] = MIN( sufMn[x << 1] + su[x << 1 | 1], sufMn[x << 1 | 1] );
        sufMx[x] = MAX( sufMx[x << 1] + su[x << 1 | 1], sufMx[x << 1 | 1] );
    }

    void Build( const int x, const int l, const int r ) {
        if( l > r ) return ;
        if( l == r ) {
            su[x] = sufMn[x] = sufMx[x] = 0;
            return ;
        }
        int mid = ( l + r ) >> 1;
        Build( x << 1, l, mid );
        Build( x << 1 | 1, mid + 1, r );
        Upt( x );
    }

    void Update( const int x, const int l, const int r, const int p, const int nVal ) {
        if( l == r ) {
            su[x] = sufMn[x] = sufMx[x] = nVal;
            return ;
        }
        int mid = ( l + r ) >> 1;
        if( p <= mid ) Update( x << 1, l, mid, p, nVal );
        else Update( x << 1 | 1, mid + 1, r, p, nVal );
        Upt( x );
    }

    LL Query( const int x, const int l, const int r, const int p, const int c, 
              const LL s, const LL mn, const LL mx ) {
        if( l == r ) return MIN( MAX( mx, sufMx[x] + s ), MIN( sufMn[x] + s, mn ) + c );
        int mid = ( l + r ) >> 1;
        if( p <= mid ) return Query( x << 1, l, mid, p, c, 
                                     s + su[x << 1 | 1], MIN( mn, s + sufMn[x << 1 | 1] ), MAX( mx, s + sufMx[x << 1 | 1] ) );
        return Query( x << 1 | 1, mid + 1, r, p, c, s, mn, mx );
    }

    int Search( const int x, const int l, const int r, const int c, const LL s, const LL mn, const LL mx ) {
        if( l == r ) return l;
        int mid = ( l + r ) >> 1;
        if( MAX( s + sufMx[x << 1 | 1], mx ) < MIN( s + sufMn[x << 1 | 1], mn ) + c )
            return Search( x << 1, l, mid, c, 
                           s + su[x << 1 | 1], MIN( s + sufMn[x << 1 | 1], mn ), MAX( s + sufMx[x << 1 | 1], mx ) );
        return Search( x << 1 | 1, mid + 1, r, c, s, mn, mx );
    }

    void Work() {
        rep( i, 1, Q ) 
            que[qL[i] + 1].push_back( i ),
            que[qR[i] + 2].push_back( - i );
        Build( 1, 0, Q );
        rep( i, 1, N ) {
            int n = que[i].size();
            rep( j, 0, n - 1 ) {
                if( que[i][j] > 0 )
                    Update( 1, 0, Q, que[i][j], qV[que[i][j]] );
                else Update( 1, 0, Q, - que[i][j], 0 );
            }
            ans[i] = - INF;
            int brk = Search( 1, 0, Q, C[i], 0, INF, - INF );
            if( brk ) ans[i] = MAX( ans[i], Query( 1, 0, Q, brk, C[i], 0, INF, - INF ) );
            if( brk < Q ) ans[i] = MAX( ans[i], Query( 1, 0, Q, brk + 1, C[i], 0, INF, - INF ) );
            ans[i] = MAX( 0ll, MIN( ans[i], ( LL ) C[i] ) );
        }
    }
}

Vec distribute_candies( Vec c, Vec l, Vec r, Vec v ) {
    static std :: vector ret;
    
    Studio :: N = c.size();
    Studio :: Q = l.size();
    rep( i, 0, Studio :: N - 1 ) Studio ::  C[i + 1] = c[i];
    rep( i, 0, Studio :: Q - 1 ) Studio :: qL[i + 1] = l[i];
    rep( i, 0, Studio :: Q - 1 ) Studio :: qR[i + 1] = r[i];
    rep( i, 0, Studio :: Q - 1 ) Studio :: qV[i + 1] = v[i];
    Studio :: Work();
    rep( i, 0, Studio :: N - 1 ) ret.push_back( Studio :: ans[i + 1] );
    return ret;
}