【题解】P5073 | 凸包 线段树 空间优化

ღꦿ࿐ · 2024-01-04 15:26:01 · 题解

常见的对于某个 x 求形如 \max(k_i x+b_i) 的斜率类问题有两种凸包的描述方式，第一种是点 (k_i,b_i) 的凸包求切线截距，第二种是直接对 (k_i,b_i) 建出线凸包求点值。

本题的其它题解都维护了第一种这种不太直观的斜率优化方式，还要使用闵可夫斯基和，在这里我是用的第二种方式，较为直观。

全局加，区间最大子段和。

考虑类似普通分治形带修最大子段和的方式维护，使用线段树的方式维护如下四个值：区间和，区间前缀和最值，区间后缀和最值，区间最大子段和最值。

现在我们拓展这个做法，来考虑这些值随着全局增加量 \Delta 的变化。

首先有区间和为一次函数 \text{Sum}(\Delta)=len \times \Delta + \sum a，这是显然的，可以直接在线段树上对其两个儿子求和得到。

区间前缀和和区间后缀和没有本质区别，在这里拿区间前缀和分析：

令 p_i 表示该区间长度为 i 的前缀和，则有 \text{MaxPre}(\Delta) =\max_{} ( i \Delta + p_i)，这是若干个一次函数取 \max 的形式，所以是一个下凸函数，我们可以直接枚举所有直线，建出该函数的凸包。

接下来是最大子段和的变化，其也是一些一次函数的最值，所以也是凸函数 \text{MaxSub}(\Delta)=\max(i\Delta + m_i)，其中 m_i 表示 a 上长度为 i 的子段和的最大值。

但是与上面不同的是，我们难以低于 O(len^2) 地求出所有 m_i，所以我们需要考虑别的方式求出这个凸包，考虑回到最原始的线段树求最大子段和的方式，由左边子段，右边子段和跨过中间的子段转移而来，即：

因为我们在上面证明了这个 \text{MaxSub}(\Delta) 是凸函数，所以可以放心地对两个子凸包分段求和，求出来仍然是凸的（结果就是若干一次函数的最值，必须得是凸的），求 \max 就直接把所有直线拉出来求新的凸包就行了。

直接建出这样一颗线段数，每个点上维护这样三个凸包，查询时在对应凸包上二分求出三个最值，然后就像普通的最大子段和那样合并就行了。

时间复杂度 O(n\log n + m \log ^2n)，空间复杂度 O(n\log n)，均无法接受，考虑优化。

因为我们的询问的信息只和目前增加的 \Delta_i 相关，所以考虑离线将询问按照询问时的 \Delta 排个序，然后就可以把凸包上二分换成拿指针单调向前扫。

空间优化同样地考虑离线询问后使用 “线段树分治线性空间” 的 Trick，直接带着所有询问向下递归，判断该询问在该区间是否生效，是否下放到左右儿子即可（下放后要释放空间或是直接使用单链表移过去下放！），这样每个时刻每个询问至多只会在两个节点上。

我们得到了一个时间 O((n+m)\log n)，空间 O(n+m) 的优秀做法。

一种很优秀的写法是不建出成型的线段树，在递归时直接下传询问，返回凸包，这样每个时刻一个询问只会存在在至多两个节点上（线段树上其跨过 mid 劈开的两个节点），保留的凸包中的信息也是线段树目前还未完成的节点，其对应的大小和也是 O(n) 的，最大空间消耗仅有约 60 MB。

这是关键部分的代码：

std :: tuple < covex , covex , covex , line > solve (int l,int r,std :: vector <int> &ques) {
    int mid = (l + r) >> 1; 
    std :: vector <int> ls , rs , ths ;

    for (auto q : ques) {
        if (ql[q] <= l && r <= qr[q]) { 
            ths.emplace_back(q) ; 
            continue;
        }
        if (ql[q] <= mid) ls.emplace_back(q) ;
        if (qr[q] > mid) rs.emplace_back(q) ;
    }
    ls.shrink_to_fit() , rs.shrink_to_fit( ) ;
    std :: vector<int> ().swap (ques) ;  

    covex pre , suf , sub ; line sum ; 
    if (l == r) {
        pre.f.emplace_back(0 , 0) ;
        pre.f.emplace_back(1 , a[l]) ;
        suf = pre ;
        sub = pre ;
        sum = line (1 , a[l]) ;
    }
    else {
        auto [prel , sufl , subl , suml] = solve (l , mid , ls) ;
        auto [prer , sufr , subr , sumr] = solve (mid + 1 , r , rs) ;
        sum = suml + sumr ;         
        /*
            pre = max (prel , prer + suml) 
            suf = max (sufr , prel + sufr) 
            sub = max (subl , subr , prer + sufl)
        */ 
        sub.sum (sufl , prer) ;
        sub.max (subl) ;
        sub.max (subr) ;
        prer.shift (suml) ;
        sufl.shift (sumr) ;
        pre.swap (prel) ;
        suf.swap (sufr) ;
        pre.max (prer) ;
        suf.max (sufl) ;
    }

    std :: vector<line> &c1 = pre.f , &c2 = suf.f , &c3 = sub.f ;

    int pt1 = 0 , pt2 = 0 , pt3 = 0 , s1 = (int)pre.f.size() - 1 , s2 = (int)suf.f.size( ) - 1 , s3 = (int)sub.f.size( ) - 1 ;
    for (const auto &q:ths) {

        ll del = qx[q] ;
        ll qpre , qsuf , qsub , qsum = sum(del) ;

        while (pt1 < s1 && c1[pt1](del) <= c1[pt1 + 1](del))
            ++ pt1 ;
        qpre = c1[pt1] (del) ;
        while (pt2 < s2 && c2[pt2](del) <= c2[pt2 + 1](del))
            ++ pt2 ;
        qsuf = c2[pt2] (del) ;
        while (pt3 < s3 && c3[pt3](del) <= c3[pt3 + 1](del))
            ++ pt3 ;
        qsub = c3[pt3] (del) ;

        ans[q] = std :: max (ans[q] , sf[q] + qpre ) ;
        ans[q] = std :: max (ans[q] , qsub ) ; 
        sf[q] = std :: max (qsuf , qsum + sf[q]) ;
    }
    return {pre , suf , sub , sum} ;
}

这是完整的代码。