求教 wqs 二分 check 内判断的差别

il bool check__(int val) {
    hh = 1; tt = 0; f[0] = g[0] = 0;
    rep(i,1,n) {
        // cerr << hh << " " << tt << endl;
        while (hh <= tt && check(q[hh - 1],q[hh]) <= i) ++ hh;
        int j = q[hh - 1];
        f[i] = f[j] + calc(j + 1,i) - val; g[i] = g[j] + 1;
        while (hh <= tt && check(q[tt - 1],q[tt]) >= check(q[tt],i)) -- tt;
        q[++ tt] = i;
    }
    return g[n] <= p;
}

il void solve() {
    //------------code------------
    read(n,p);
    rep(i,1,n) read(a[i]);
    sort(a + 1,a + n + 1);
    rep(i,1,n) s[i] = s[i - 1] + a[i];
    int l = -1e7,r = 0,ret = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check__(mid)) l = mid + 1,ret = mid;
        else r = mid - 1;
    }
    check__(ret);
    write(f[n] + p * ret,'\n');
    return ;
}