不曾留下涓滴的踌躇

AzusagawaKaede · 2024-02-19 22:45:56 · 题解

一道有点奇怪思路的题.

考虑第一问，容易发现要选出一个长度不小于 k 的区间，最大化 区间前 k 大 s 的和减去区间 c 和.

记区间 [l, r] 前 k 大 s 的和减去区间 c 和为 w(l, r). 那么可以发现 w(l, r) 满足四边形不等式，证明考虑区间 c 和会被消掉，于是对于 a < b < c < d 有 w(a, c) + w(b, d) \ge w(a, d) + w(b, c).

那么第一问可以通过决策单调性分治解决，可以使用权值线段树维护区间前 k 大和，移动左右端点，计算答案，当然也可以直接上主席树. 这一步的时间复杂度是 \mathcal{O}(n\log^2 n).

记第一问的答案为 ans，考虑第二问，我们将 w=ans 的区间称为最优区间，一个数可以被选，当且仅当其为某个最优区间中的前 k 大.

一个直接的想法是找出所有最优区间，用线段树维护每个点能被选所需要达到的最小值，然而最优区间的数目可以达到 \Theta(n^2) 级别，因此需要进行一定的优化.

考虑如果有两个最优区间 [l_1, r_1], [l_2, r_2] 满足 l_1< l_2 < r_2 < r_1. 由四边形不等式有 w(l_1, r_2) + w(l_2, r_1)\ge w(l_1, r_1) + w(l_2, r_2)，即 w(l_1, r_2) + w(l_2, r_1)\ge 2\times ans，因此 [l_1, r_2] 和 [l_2, r_1] 也是最优区间. 易知只需要将 [l_1, r_2], [l_2, r_2], [l_2, r_1] 三个区间计入考虑，需要计入考虑的左端点关于右端点单调不减，于是这是一个类双指针状物.

在分治过程中，对于每个 r 计算最大的使 w(l, r) 最大的 l. 将如此得到的所有最优区间存起来. 于是对于所有可以为最优区间右端点的 r，都得到了其对应的最大左端点 l，那么做一次双指针统计答案即可.

code:

#include<bits/stdc++.h>

using i64 = long long;
#define int i64
const int N = 250005;

int n, k;

int c[N], s[N];
int v[N], len;
i64 sum[N];

namespace seg_t1 {

struct node {
    int l, r, c;
    i64 s;
}tree[N << 2];

#define ls(p) (p << 1)
#define rs(p) (ls(p) | 1)
#define l(p)  tree[p].l
#define r(p)  tree[p].r
#define c(p)  tree[p].c
#define s(p)  tree[p].s

inline void pushup(int p) {
    c(p) = c(ls(p)) + c(rs(p));
    s(p) = s(ls(p)) + s(rs(p));
}

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
}

void add(int p, int x, int val) {
    if (x > r(p) || x < l(p)) return;
    if (l(p) == x && r(p) == x) {
        c(p) += val;
        s(p) = 1ll * c(p) * v[l(p)];
        return;
    }
    add(ls(p), x, val);
    add(rs(p), x, val);
    pushup(p);
}

int qc(int p, int l, int r) {
    if (l > r(p) || r < l(p)) return 0;
    if (l <= l(p) && r(p) <= r) return c(p);
    return qc(ls(p), l, r) + qc(rs(p), l, r);
}

i64 qs(int p, int l, int r) {
    if (l > r(p) || r < l(p)) return 0;
    if (l <= l(p) && r(p) <= r) return s(p);
    return qs(ls(p), l, r) + qs(rs(p), l, r);
}

inline int bs(int k) {
    k = c(1) - k + 1;
    int cur = 1;
    while (l(cur) != r(cur)) {
        if (k > c(ls(cur))) k -= c(ls(cur)), cur = rs(cur);
        else cur = ls(cur);
    }
    return l(cur);
}

inline i64 get_ksum() {
    int x = bs(k);
    return qs(1, x + 1, len) + 1ll * (k - qc(1, x + 1, len)) * v[x];
}

#undef ls
#undef rs
#undef l
#undef r
#undef c
#undef s

}

using seg_t1::add;
using seg_t1::get_ksum;
using seg_t1::bs;

int _l = 1, _r;

inline void ins(int x) {
    add(1, s[x], 1);
}

inline void del(int x) {
    add(1, s[x], -1);
}

inline i64 g_res(int l, int r) {
    while (_l > l) ins(--_l);
    while (_r < r) ins(++_r);
    while (_l < l) del(_l++);
    while (_r > r) del(_r--);
    return get_ksum() - (sum[_r] - sum[_l - 1]);
}

i64 ans = -(1ll << 60);
std::vector<std::pair<int, int> > vc;

inline void solve(int l, int r, int ql, int qr) {
    if (l > r) return;
    int p = (l + r) >> 1;
    int pos = 0;
    i64 res = -(1ll << 60);
    for (int i = std::min(qr, p - k + 1); i >= ql; i--) {
        if (g_res(i, p) > res) {
            pos = i;
            res = g_res(i, p);
        }
    }
    if (res > ans) {
        ans = res;
        vc.clear();
    }
    if (res == ans) vc.emplace_back(pos, p);
    solve(l, p - 1, ql, pos);
    solve(p + 1, r, pos, qr);
}

bool f[N];

namespace seg_t2 {

struct node {
    int l, r, v;
}tree[N << 2];

#define ls(p) (p << 1)
#define rs(p) (ls(p) | 1)
#define l(p)  tree[p].l
#define r(p)  tree[p].r
#define v(p)  tree[p].v

void build(int p, int l, int r) {
    l(p) = l, r(p) = r;
    v(p) = 0x7fffffff;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls(p), l, mid);
    build(rs(p), mid + 1, r);
}

void chkmin(int p, int l, int r, int v) {
    if (l > r(p) || r < l(p)) return;
    if (l <= l(p) && r(p) <= r) {
        v(p) = std::min(v(p), v);
        return;
    }
    chkmin(ls(p), l, r, v);
    chkmin(rs(p), l, r, v);
}

inline int qry(int p, int x) {
    if (x > r(p) || x < l(p)) return 0x7fffffff;
    if (l(p) == r(p)) return v(p);
    return std::min(v(p), std::min(qry(ls(p), x), qry(rs(p), x)));
}

}

using seg_t2::chkmin;
using seg_t2::qry;

signed main() {
    std::cin.tie(0)->sync_with_stdio(0);
    std::cin >> n >> k;
    for (int i = 1; i <= n; i++) std::cin >> c[i];
    for (int i = 1; i <= n; i++) std::cin >> s[i];

    memcpy(v, s, sizeof s);
    std::sort(v + 1, v + n + 1);
    len = std::unique(v + 1, v + n + 1) - v - 1;
    for (int i = 1; i <= n; i++) s[i] = std::lower_bound(v + 1, v + len + 1, s[i]) - v;

    for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + c[i];

    seg_t1::build(1, 1, len);
    solve(k, n, 1, n);
    seg_t2::build(1, 1, n);
    std::sort(vc.begin(), vc.end());
    for (const auto &[ml, r] : vc) {
        static int l = 1;
        for (; l <= ml; l++) 
            if (g_res(l, r) == ans) chkmin(1, l, r, bs(k));
        l = ml;
    }
    std::cout << ans << '\n';
    for (int i = 1; i <= n; i++) std::cout << (s[i] >= qry(1, i));
    std::cout << '\n';
}