笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 P6246 【[IOI2000] 邮局 加强版】

posted on 2020-04-01 08:00:50 | under 题解 |

出了题没多少人做,还不小心卡了神 iostreamcdq,这就很尴尬/kk


这个东西,考虑朴素的dp,就显然是 $f_{i,j}$ 记一下,然后放 $k\to i$ 的中点就好了。这样复杂度是 $n^2k$ 的。

然后编一下发现有决策单调性,就可以 $O(nk\log n)$ 其二分+单调栈,甚至直接用二维决策单调性做到 $O(nk)$ 了。

然而并不可以过233

考虑去优化一下上面那种解法,发现 $k$ 这个限制可以通过wqs二分给消掉,就变成了如果建一次邮局需要额外支付 $mid$ 的代价,但是不限制建的次数时的最短距离和。这个东西就变成了一个1D/1D的 $dp$ ,并且也具有决策单调性。这一部分就可以继续单调栈+二分做到 $n\log V\log n$ 。

不过写了写发现似乎二分的常数还是很小的,$n=5\times 10^5$ 也只需要谷 $2.7s$ 、uoj $2s$ 左右。

int tp ;
ll res ;
ll f[N] ;
ll sum[N] ;
int lrg[N] ;
int cnt[N] ;
int stk[N] ;
int base[N] ;
int n, m, k ;

using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;

il ll calc(int l, int r){
    ll h = (l + r + 1) / 2 ;
    ll ret = sum[r] - sum[h] ;
    ll d1 = 1ll * (h - l) * base[h] ;
    ll d2 = 1ll * (r - h) * base[h] ;
    return ret - d2 + d1 - sum[h] + sum[l] ;
}
il ll trans(ll p, ll x){
    return f[p] + calc(p, x) ;
}
bool check(ll x){
    stk[tp = 0] = 0 ; 
    int h = 0 ; lrg[0] = 1 ;
    for (int i = 1 ; i <= n ; ++ i){
        while (h < tp && lrg[h] < i)
            ++ h ; if (lrg[h] > i) -- h ;
        f[i] = trans(stk[h], i) + x, cnt[i] = cnt[stk[h]] + 1 ;
        while (tp && trans(stk[tp], lrg[tp]) >= trans(i, lrg[tp]))
            stk[tp] = 0, lrg[tp] = n + 1, -- tp ;
        int l = lrg[tp], r = n, mid, ans = n + 1 ;
        while (l <= r){
            int mid = (l + r) >> 1 ;
            if (trans(stk[tp], mid) >= trans(i, mid))
                ans = mid, r = mid - 1 ; else l = mid + 1 ;
        }
        if (ans <= n) stk[++ tp] = i, lrg[tp] = ans ;
    }
    res = f[n] - x * m ; return (bool)(cnt[n] < m) ;
}
int main(){
    qr(n) ; qr(m) ;
    for (int i = 1 ; i <= n ; ++ i)
        qr(base[i]), sum[i] = sum[i - 1] + (ll)base[i] ;  
    ll l = 0, r = 1e9, mid, ans ; 
    lrg[0] = 1 ; sum[n + 1] = sum[n] ; 
    while (l <= r){
        mid = (l + r) >> 1 ;
        if (check(mid)) r = mid - 1 ; 
        else ans = mid, l = mid + 1 ;
    }
    check(ans) ; qw(res) ; return 0 ;
}

#