JOISC 2019 题解

作者: xht37 分类: 题解 发布时间: 2020-05-17 04:37

点击数:92

JOISC 2019

Day1

試験 (Examination)

裸的三维偏序模板题,$\mathcal O(n \log^2 n)$ 的 CDQ 分治即可。

const int N = 6e5 + 7;
int n, m, a[N], c[N], t, ans[N];
struct P {
    int x, y, z, o;
    inline bool operator < (const P p) const {
        return x == p.x ? o < p.o : x < p.x;
    }
} p[N], q[N];

inline void add(int x, int k) {
    while (x <= t) c[x] += k, x += x & -x;
}

inline int ask(int x) {
    int k = 0;
    while (x) k += c[x], x -= x & -x;
    return k;
}

void cdq(int l, int r) {
    if (l == r) return;
    int mid = (l + r) >> 1;
    cdq(l, mid), cdq(mid + 1, r);
    for (int i = l, j = mid + 1, k = l; k <= r; k++)
        if (j == r + 1 || (i != mid + 1 && p[i].y <= p[j].y)) {
            if (!p[i].o) add(p[i].z, 1);
            q[k] = p[i++];
        } else {
            if (p[j].o) ans[p[j].o] += ask(p[j].z);
            q[k] = p[j++];
        }
    for (int i = l; i <= mid; i++)
        if (!p[i].o) add(p[i].z, -1);
    for (int i = l; i <= r; i++) p[i] = q[i];
}

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++)
        rd(p[i].x, p[i].y), p[i].z = p[i].x + p[i].y;
    for (int i = 1; i <= m; i++)
        rd(p[i+n].x, p[i+n].y, p[i+n].z), p[i+n].o = i;
    n += m;
    for (int i = 1; i <= n; i++)
        a[++t] = p[i].x, a[++t] = p[i].y, a[++t] = p[i].z;
    sort(a + 1, a + t + 1);
    t = unique(a + 1, a + t + 1) - (a + 1);
    for (int i = 1; i <= n; i++)
        p[i].x = t + 1 - (lower_bound(a + 1, a + t + 1, p[i].x) - a),
        p[i].y = t + 1 - (lower_bound(a + 1, a + t + 1, p[i].y) - a),
        p[i].z = t + 1 - (lower_bound(a + 1, a + t + 1, p[i].z) - a);
    sort(p + 1, p + n + 1);
    cdq(1, n);
    for (int i = 1; i <= m; i++) print(ans[i]);
    return 0;
}

ビーバーの会合 (Meetings)

有意思的交互题。

考虑到 $\text{Query}(x,y,z)$ 有以下两种情况:

  • 若 $x,y,z$ 在一条链上,则返回中间的那个点。
  • 若 $x,y,z$ 不在一条链上,则返回以 $x$ 为根时的 $\text{LCA}(y, z)$。

考虑每次对于一个点集随机其中的一条链 $(x,y)$,然后询问其他点与 $x,y$ 的答案。

答案相同的一定在一个子树内,是一个规模更小的子问题,可以递归分治。

同时被返回的所有值构成链上的所有点,同样是一个规模更小的子问题。

这个做法在菊花图的时候询问次数约为 $n^2$,但本题中最大度数为 $18$,因此询问次数约为 $18n$。

const int N = 2e3;

void work(vi a) {
    if (a.size() == 1u) return;
    if (a.size() == 2u) return Bridge(min(a[0], a[1]), max(a[0], a[1]));
    random_shuffle(a.begin(), a.end());
    vi b(a.size()), p(a.size());
    b[0] = a[0], b[1] = a[1];
    for (ui i = 2; i < a.size(); i++) b[i] = Query(a[0], a[1], a[i]);
    for (ui i = 0; i < a.size(); i++) p[i] = i;
    sort(p.begin(), p.end(), [&](int i, int j) { return b[i] < b[j]; });
    vi d;
    for (ui l = 0, r = 0; l < a.size(); l = ++r) {
        d.pb(b[p[l]]);
        vi c(1, a[p[l]]);
        while (r + 1 < a.size() && b[p[r+1]] == b[p[l]]) c.pb(a[p[++r]]);
        work(c);
    }
    work(d);
}

void Solve(int n) {
    srand(time(0) ^ n);
    vi a(n);
    for (int i = 0; i < n; i++) a[i] = i;
    work(a);
}

ナン (Naan)

贪心。

对于每个人,求出其划分为 $n$ 等份的切割点。

对于第 $i$ 次切割,在还未选中的人中选择第 $i$ 份切割点最小的人。

时间复杂度 $\mathcal O(n(n+L))$。

#define pl pair<ll, ll>
const int N = 2e3 + 7;
int n, m, ans2[N];
ll a[N];
pl p[N][N], ans1[N];
bool v[N];

inline bool operator < (pl a, pl b) {
    return (__int128)a.fi * b.se < (__int128)b.fi * a.se;
}

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++) {
        rda(a, m);
        ll s = 0, o = 0;
        for (int j = 1; j <= m; j++) s += a[j];
        for (int j = 1, k = 1; j <= n; j++) {
            while (k < m && (o + a[k]) * n < s * j) o += a[k++];
            ll A = 1ll * n * a[k] * (k - 1) + s * j - o * n;
            ll B = 1ll * n * a[k];
            ll D = __gcd(A, B);
            p[i][j] = mp(A / D, B / D);
        }
    }
    for (int i = 1; i <= n; i++) {
        int k = 0;
        p[k][i] = mp(1, 0);
        for (int j = 1; j <= n; j++)
            if (!v[j]) k = p[j][i] < p[k][i] ? j : k;
        v[k] = 1, ans1[i] = p[k][i], ans2[i] = k;
    }
    for (int i = 1; i < n; i++) print(ans1[i].fi, ans1[i].se);
    for (int i = 1; i <= n; i++) print(ans2[i], " \n"[i==n]);
    return 0;
}

Day2

ふたつのアンテナ (Two Antennas)

对于 $i$,我们可以将其拆成在 $i+a_i$ 处出现,$i+b_i+1$ 处消失的两个事件。

考虑从小到大枚举 $j$,同时维护 $d_i$ 表示 $i$ 的最大成本。

则每新加入一个 $j$,我们要把当前存在的 $i$ 中 $\in [j-b_j,j-a_j]$ 的 $i$,将 $d_i$ 对 $|h_i-h_j|$ 取 $\max$。

对于询问 $l,r$,答案就是枚举到 $j=r$ 时的 $\max_{i=l}^{r} d_i$。

接下来考虑如何维护这个过程。

首先那个绝对值可以去掉,正反做两次就可以了,不妨设此时要求 $h_i \ge h_j$。

然后对于每个 $i$ 再维护一个 $c_i$,当其存在时 $c_i = h_i$,否则 $c_i = -\infty$。

那么加入一个 $j$ 时,我们就是要把 $[j-b_j,j-a_j]$ 中的 $d$ 对 $c_i – h_j$ 取 $\max$。

这些都可以线段树实现,时间复杂度 $\mathcal O(n \log n)$。

const int N = 2e5 + 7, inf = 1e9 + 1;
int n, m, h[N], a[N], b[N], ans[N];
vector<pi> q[N];

struct SGT {
    struct T {
        int l, r;
        int c, d, h;
    } t[N<<2|1];

    inline void update(int p) {
        t[p].c = max(t[ls].c, t[rs].c);
        t[p].d = max(t[p].d, max(t[ls].d, t[rs].d));
    }

    inline void work(int p, int x) {
        t[p].h = min(t[p].h, x);
        t[p].d = max(t[p].d, t[p].c - t[p].h);
    }

    inline void spread(int p) {
        work(ls, t[p].h), work(rs, t[p].h), t[p].h = inf;
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        t[p].c = t[p].d = -inf, t[p].h = inf;
        if (l == r) return;
        build(ls, l, md), build(rs, md + 1, r);
        update(p);
    }

    void setc(int p, int x, int k) {
        if (t[p].l == t[p].r) return t[p].c = k, t[p].h = inf, void();
        spread(p);
        if (x <= md) setc(ls, x, k);
        else setc(rs, x, k);
        update(p);
    }

    void add(int p, int l, int r, int x) {
        if (t[p].l >= l && t[p].r <= r) return work(p, x);
        spread(p);
        if (l <= md) add(ls, l, r, x);
        if (r > md) add(rs, l, r, x);
        update(p);
    }

    int ask(int p, int l, int r) {
        if (t[p].l >= l && t[p].r <= r) return t[p].d;
        spread(p);
        int ret = -inf;
        if (l <= md) ret = max(ret, ask(ls, l, r));
        if (r > md) ret = max(ret, ask(rs, l, r));
        return ret;
    }
} t;

vi p[N];

inline void solve() {
    t.build(1, 1, n);
    for (int j = 1; j <= n; j++) {
        for (int i : p[j]) t.setc(1, abs(i), i > 0 ? h[i] : -inf);
        if (max(1, j - b[j]) <= max(0, j - a[j]))
            t.add(1, max(1, j - b[j]), max(0, j - a[j]), h[j]);
        for (pi o : q[j]) ans[o.se] = max(ans[o.se], t.ask(1, o.fi, j));
    }
}

int main() {
    rd(n);
    for (int i = 1; i <= n; i++) rd(h[i], a[i], b[i]);
    rd(m);
    for (int i = 1, l, r; i <= m; i++)
        rd(l, r), q[r].pb(mp(l, i)), ans[i] = -1;
    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n) p[i+a[i]].pb(i);
        if (i + b[i] + 1 <= n) p[i+b[i]+1].pb(-i);
    }
    solve();
    for (int i = 1; i <= n; i++) h[i] = inf - h[i];
    solve();
    for (int i = 1; i <= m; i++) print(ans[i]);
    return 0;
}

ふたつの料理 (Two Dishes)

首先有一个 $\mathcal O(nm)$ 的 DP。

设 $f_{i,j}$ 表示完成了 $I$ 的 $i$ 个步骤 $J$ 的 $j$ 个步骤时的最高得分,有转移
$$
f_{i,j} = \max(f_{i-1,j} + [sa_i + sb_j \le s_i]p_i, f_{i,j-1} + [sa_i+sb_j \le t_j]q_j)
$$
其中 $sa,sb$ 分别是 $a,b$ 的前缀和。

考虑优化这个 DP。

将第一维看成时间轴,即从小到大枚举 $i$,同时维护 $f_j$。

那么当枚举到 $i$ 时:

  • 将满足 $sa_i + sb_j \le s_i$ 的 $j$,$f_j$ 加上 $p_i$。
    显然满足条件的 $j$ 是一个前缀。
  • 设 $v_j = [sa_i+sb_j \le t_j]q_j$,将 $f_j$ 与 $f_{j-1} + v_j$ 取 $\max$。
    注意 $v_j$ 一定是先为 $q_j$ 后为 $0$。

考虑维护 $f$ 的差分 $g$,则两种操作分别改为:

  • 单点加。
  • 将 $g_j$ 与 $v_j$ 取 $\max$。
    注意 $g$ 是差分数组,所以 $g_{j+1}$ 还要减去 $g_j$ 取 $\max$ 前后的差值。

再考虑所有的 $w_j = g_j – v_j$,则两种操作再改为:

  • 单点加。
  • 如果 $v_j$ 要从 $q_j$ 变为 $0$,则将 $w_j$ 加上 $q_j$。
    如果 $w_j < 0$,则 $w_{j+1}$ 加上 $w_j$,$w_j$ 赋值为 $0$。

发现所有的操作都神奇地变成了是单点操作!

注意到 $w_j = 0$ 的 $j$ 实际上并没有什么用,考虑用一个 set 维护所有 $w_j \ne 0$ 的 $j$。

每次暴力修改涉及到的所有 $g_j$ 即可,时间复杂度 $\mathcal O(n \log n)$。

const int N = 1e6 + 7;
int n, m;
ll a[N], s[N], p[N], b[N], t[N], q[N];
ll sa[N], sb[N], g[N], ans;
int pa[N], pb[N];
vi E[N], P;
set<int> S;

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++) rd(a[i], s[i], p[i]);
    for (int j = 1; j <= m; j++) rd(b[j], t[j], q[j]);
    for (int i = 1; i <= n; i++) sa[i] = sa[i-1] + a[i];
    for (int j = 1; j <= m; j++) sb[j] = sb[j-1] + b[j];
    for (int i = 1; i <= n; i++)
        pa[i] = upper_bound(sb, sb + m + 1, s[i] - sa[i]) - sb - 1;
    for (int j = 1; j <= m; j++)
        pb[j] = upper_bound(sa, sa + n + 1, t[j] - sb[j]) - sa - 1;
    for (int j = 1; j <= m; j++)
        if (pb[j] >= 0) {
            if (pb[j] + 1 <= n) E[pb[j]+1].pb(j);
            else ans += q[j];
        }
    for (int i = 1; i <= n; i++) {
        P.clear();
        if (pa[i] >= 0) {
            ans += p[i];
            if (pa[i] + 1 <= m)
                g[pa[i]+1] -= p[i], S.insert(pa[i] + 1), P.pb(pa[i] + 1);
        }
        for (int j : E[i]) g[j] += q[j], S.insert(j), P.pb(j);
        sort(P.begin(), P.end());
        for (int j : P) {
            auto l = S.lower_bound(j), r = l;
            ll o = 0;
            while (r != S.end()) {
                g[*r] += o;
                if (g[*r] >= 0) break;
                o = g[*r], g[*r++] = 0;
            }
            S.erase(l, r);
        }
    }
    for (int j = 1; j <= m; j++) ans += g[j];
    print(ans);
    return 0;
}

ふたつの交通機関 (Two Transportations)

通信题不做。

Day3

指定都市 (Designated Cities)

$1/2$ 的答案 DP 求,后面的贪心往点集里加叶子,线段树/长链剖分维护。

const int N = 2e5 + 7;
int n, m, rt;
vector<pi> e[N];
ll f[N], g[N], ans[N];

void dfs1(int x, int fa) {
    for (pi o : e[x]) {
        int y = o.fi;
        if (y == fa) continue;
        dfs1(y, x), f[x] += f[y] + o.se;
    }
}

void dfs2(int x, int fa) {
    for (pi o : e[x]) {
        int y = o.fi;
        if (y == fa) {
            g[x] += o.se;
            break;
        }
    }
    for (pi o : e[x]) {
        int y = o.fi;
        if (y == fa) continue;
        g[y] = g[x] + f[x] - f[y] - o.se;
        dfs2(y, x);
    }
}

int l[N], r[N], s[N], p[N], t, fa[N], hh[N];
ll ga[N], h[N][2];

void dfs3(int x, int fa) {
    hh[x] = x;
    for (pi o : e[x]) {
        int y = o.fi;
        if (y == fa) continue;
        dfs3(y, x);
        if (h[x][1] < h[y][0] + o.se) h[x][1] = h[y][0] + o.se;
        if (h[x][0] < h[x][1]) swap(h[x][0], h[x][1]), hh[x] = hh[y];
    }
}

void dfs4(int x, int fa) {
    ::fa[x] = fa;
    l[x] = t + 1;
    if (e[x].size() == 1u) s[++t] = x, p[t] = x;
    for (pi o : e[x]) {
        int y = o.fi;
        if (y == fa) continue;
        ga[y] = o.se, h[y][0] = h[x][0] + o.se, dfs4(y, x);
    }
    r[x] = t;
}

struct SGT {
    struct T {
        int l, r;
        int o;
        ll x, z;
    } t[N<<2|1];

    inline void update(int p) {
        if (t[ls].x >= t[rs].x) t[p].x = t[ls].x, t[p].o = t[ls].o;
        else t[p].x = t[rs].x, t[p].o = t[rs].o;
    }

    inline void work(int p, ll x) {
        t[p].x += x, t[p].z += x;
    }

    inline void spread(int p) {
        if (t[p].z) work(ls, t[p].z), work(rs, t[p].z), t[p].z = 0;
    }

    void build(int p, int l, int r) {
        t[p].l = l, t[p].r = r;
        if (l == r) return t[p].x = h[::p[l]][0], t[p].o = l, void();
        build(ls, l, md), build(rs, md + 1, r);
        update(p);
    }

    void add(int p, int l, int r, ll x) {
        if (t[p].l >= l && t[p].r <= r) return work(p, x);
        spread(p);
        if (l <= md) add(ls, l, r, x);
        if (r > md) add(rs, l, r, x);
        update(p);
    }
} sgt;

bool v[N];
ll now;

int main() {
    rd(n);
    for (int i = 1, a, b, c, d; i < n; i++)
        rd(a, b), rd(c, d), e[a].pb(mp(b, c)), e[b].pb(mp(a, d));
    dfs1(1, 0);
    dfs2(1, 0);
    ans[1] = f[1] + g[1];
    for (int i = 1; i <= n; i++)
        ans[1] = min(ans[1], f[i] + g[i]);
    dfs3(1, 0);
    rt = hh[1], ans[2] = f[1] + g[1] - h[1][0] - h[1][1];
    for (int i = 1; i <= n; i++)
        if (f[i] + g[i] - h[i][0] - h[i][1] < ans[2])
            rt = hh[i], ans[2] = f[i] + g[i] - h[i][0] - h[i][1];
    h[rt][0] = 0, dfs4(rt, 0);
    sgt.build(1, 1, t);
    v[rt] = 1, now = f[rt] + g[rt];
    for (int i = 1 + (e[rt].size() == 1u); i <= t; i++) {
        int x = s[sgt.t[1].o];
        now -= sgt.t[1].x;
        while (!v[x]) sgt.add(1, l[x], r[x], -ga[x]), v[x] = 1, x = fa[x];
        if (i != 1) ans[i] = now;
    }
    rd(m);
    for (int i = 1, x; i <= m; i++) rd(x), print(ans[min(x,t)]);
    return 0;
}

ランプ (Lamps)

存在一种最优策略为,赋值操作的区间两两不交,取反操作的区间两两不交,所有赋值操作在取反操作之前。

设 $f_{i,0/1/2}$ 表示第 $i$ 位赋值为 $0/1$ 或不赋值的情况下操作区间端点的最小个数,则最后答案除以 $2$ 即可。

const int N = 1e6 + 7, inf = 1e9;
const int c[3][3] = {{0,2,1},{2,0,1},{1,1,0}};
int n, f[N][3];
char s[N], t[N];
bool a[N], b[N];

int main() {
    rd(n), rds(s, n), rds(t, n);
    for (int i = 1; i <= n; i++) a[i] = s[i] & 15, b[i] = t[i] & 15;
    ++n;
    f[1][0] = (0 ^ b[1]) + 1;
    f[1][1] = (1 ^ b[1]) + 1;
    f[1][2] = a[1] ^ b[1];
    for (int i = 2; i <= n; i++) {
        f[i][0] = f[i][1] = f[i][2] = inf;
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++) {
                int x = (j == 2 ? a[i-1] : j) ^ b[i-1];
                int y = (k == 2 ? a[i] : k) ^ b[i];
                f[i][k] = min(f[i][k], f[i-1][j] + c[j][k] + (x ^ y));
            }
    }
    print(f[n][2] >> 1);
    return 0;
}

時をかけるビ太郎 (Bitaro, who Leaps through Time)

首先把 $i$ 的时间减去 $i$,则所有斜线移动都变成了横线。

把每个区间 $[l,r]$ 看成一个二元组 $(l,r)$,合并两个二元组 $(l_1,r_1),(l_2,r_2)$ 有三种情况:

  • $\max(l_1,l_2) \le \min(r_1,r_2) \to (\max(l_1,l_2), \min(r_1,r_2))$。
  • $r_1 < l_2$,$l_1 < r_2$,这两种情况好像不能用二元组表示的样子。

那么,我们再设一个三元组 $(l,r,k)$ 表示从 $l$ 走进 $r$ 走出,中间使用技能次数为 $k$。

此时既有二元组又有三元组,我们需要考虑所有合并的情况:

  • $(l_1,r_1),(l_2,r_2)$:
    • $\max(l_1,l_2) \le \min(r_1,r_2) \to (\max(l_1,l_2), \min(r_1,r_2))$。
    • $r_1 < l_2 \to (r_1,l_2,0)$。
    • $l_1 > r_2 \to (l_1,r_2,l_1-r_2)$。
  • $(l_1,r_1),(l_2,r_2,k_2)$:
    • $l_1 \le l_2 \le r_1 \to (l_2,r_2,k_2)$。
    • $r_1 < l_2 \to (r_1,r_2,k_2)$。
    • $l_1 > l_2 \to (l_1,r_2,k_2+l_1-l_2)$。
  • $(l_1,r_1,k_1),(l_2,r_2)$:
    • $l_2 \le r_1 \le r_2 \to (l_1, r_1, k_1)$。
    • $r_1 < l_2 \to (l_1,l_2,k_1)$。
    • $r_1 > r_2 \to (l_1,r_2,k_1+r_1-r_2)$。
  • $(l_1,r_1,k_1),(l_2,r_2,k_2)$:$(l_1,r_2,k_1+k_2+\max(r_1-l_2, 0))$。

线段树维护即可,时间复杂度 $\mathcal O(q \log n)$。

const int N = 3e5 + 7;
int n, q;

struct P {
    int l, r;
    ll k;
    inline P() {}
    inline P(int l, int r, ll k = -1) : l(l), r(r), k(k) {}
    inline friend P operator + (P a, P b) {
        if (!~a.k && !~b.k) {
            if (max(a.l, b.l) <= min(a.r, b.r))
                return P(max(a.l, b.l), min(a.r, b.r));
            if (a.r < b.l) return P(a.r, b.l, 0);
            if (a.l > b.r) return P(a.l, b.r, a.l - b.r);
        }
        if (!~a.k && ~b.k) {
            if (a.l <= b.l && b.l <= a.r) return b;
            if (a.r < b.l) return P(a.r, b.r, b.k);
            if (a.l > b.l) return P(a.l, b.r, b.k + a.l - b.l);
        }
        if (~a.k && !~b.k) {
            if (b.l <= a.r && a.r <= b.r) return a;
            if (a.r < b.l) return P(a.l, b.l, a.k);
            if (a.r > b.r) return P(a.l, b.r, a.k + a.r - b.r);
        }
        return P(a.l, b.r, a.k + b.k + max(a.r - b.l, 0));
    }
} a1[N], a2[N];

struct SGT {
    struct T {
        int l, r;
        P x;
    } t[N<<2|1];

    inline void update(int p) {
        t[p].x = t[ls].x + t[rs].x;
    }

    void build(int p, int l, int r, P* a) {
        t[p].l = l, t[p].r = r;
        if (l == r) return t[p].x = a[l], void();
        build(ls, l, md, a), build(rs, md + 1, r, a);
        update(p);
    }

    void add(int p, int l, int r, P x) {
        if (t[p].l >= l && t[p].r <= r) return t[p].x = x, void();
        if (l <= md) add(ls, l, r, x);
        if (r > md) add(rs, l, r, x);
        update(p);
    }

    P ask(int p, int l, int r) {
        if (t[p].l >= l && t[p].r <= r) return t[p].x;
        if (r <= md) return ask(ls, l, r);
        if (l > md) return ask(rs, l, r);
        return ask(ls, l, r) + ask(rs, l, r);
    }
} t1, t2;

int main() {
    rd(n, q);
    for (int i = 1; i < n; i++)
        rd(a1[i].l, a1[i].r), --a1[i].r, a1[i].k = -1, a2[n-i] = a1[i],
        a1[i].l -= i, a1[i].r -= i,
        a2[n-i].l -= n - i, a2[n-i].r -= n - i;
    if (n > 1) t1.build(1, 1, n - 1, a1), t2.build(1, 1, n - 1, a2);
    for (int i = 1, o; i <= q; i++) {
        rd(o);
        if (o == 1) {
            int p, s, e;
            rd(p, s, e), --e;
            if (n == 1) continue;
            t1.add(1, p, p, P(s - p, e - p));
            t2.add(1, n - p, n - p, P(s - (n - p), e - (n - p)));
        } else {
            int a, b, c, d;
            rd(a, b), rd(c, d);
            if (a == c) print(max(0, b - d));
            else if (a < c) print((P(b - a, b - a, 0) + t1.ask(1, a, c - 1) + P(d - c, d - c, 0)).k);
            else print((P(b - (n - a + 1), b - (n - a + 1), 0) + t2.ask(1, n - a + 1, n - c) + P(d - (n - c + 1), d - (n - c + 1), 0)).k);
        }
    }
    return 0;
}

Day4

ケーキの貼り合わせ (Cake 3)

首先显然对 $c$ 排序后答案是某个区间的前 $k$ 大 $v$ 之和减去两倍的 $c$ 之差。

然而显然我们不需要考虑所有区间,可能成为答案的区间满足决策单调性,只有 $\mathcal O(n)$ 个。

然后区间前 $k$ 大和用个主席树就行了,总时间复杂度 $\mathcal O(n \log^2 n)$。

由于第一次写决策单调性,这里记一下步骤:

建一个队列,里面保存三元组 $(l,r,x)$,表示当前情况下 $l \sim r$ 的最优决策在 $x$。

从小到大枚举 $i$:

  1. 若队头的 $r < i$,则弹出队头。
  2. 用此时的队头作为最优决策转移到 $i$。
  3. 不断弹出比 $i$ 更劣的队尾。
  4. 若此时队尾比 $i$ 优,则直接将 $i$ 补在队尾。
  5. 否则在队尾上二分找到第一个以 $i$ 为最优决策点的位置,改变队尾的 $r$ 值,同时插入 $i$。
const int N = 2e5 + 7;
int n, m, b[N], k;
pi a[N];
ll ans = -1e18;
struct P {
    int l, r, x;
    inline P() {}
    inline P(int l, int r, int x) : l(l), r(r), x(x) {}
};
deque<P> q;

struct T {
    int l, r, c;
    ll s;
} t[N<<6|1];
int rt[N], tot;

int ins(int p, int l, int r, int x) {
    int q = ++tot;
    t[q] = t[p];
    ++t[q].c, t[q].s += b[x];
    if (l == r) return q;
    int d = (l + r) >> 1;
    if (x <= d) t[q].l = ins(t[p].l, l, d, x);
    else t[q].r = ins(t[p].r, d + 1, r, x);
    return q;
}

ll ask(int p, int q, int l, int r, int k) {
    if (l == r) return 1ll * b[l] * k;
    int c = t[t[p].r].c - t[t[q].r].c, d = (l + r) >> 1;
    if (c >= k) return ask(t[p].r, t[q].r, d + 1, r, k);
    return t[t[p].r].s - t[t[q].r].s + ask(t[p].l, t[q].l, l, d, k - c);
}

inline ll ask(int l, int r) {
    if (r - l + 1 < m) return -1e18;
    return ask(rt[r], rt[l-1], 1, k, m) - (a[r].fi - a[l].fi) * 2;
}

int main() {
    rd(n, m);
    for (int i = 1; i <= n; i++) rd(a[i].se, a[i].fi), b[i] = a[i].se;
    sort(a + 1, a + n + 1);
    sort(b + 1, b + n + 1);
    k = unique(b + 1, b + n + 1) - (b + 1);
    rt[0] = tot = 1;
    for (int i = 1; i <= n; i++)
        a[i].se = lower_bound(b + 1, b + k + 1, a[i].se) - b,
        rt[i] = ins(rt[i-1], 1, k, a[i].se);
    for (int i = 1; i <= n; i++) {
        if (q.size() && q.front().r < i) q.pop_front();
        if (i >= m) ans = max(ans, ask(q.front().x, i));
        while (q.size() && ask(q.back().x, q.back().l) <= ask(i, q.back().l)) q.pop_back();
        if (q.size() && ask(q.back().x, q.back().r) <= ask(i, q.back().r)) {
            int l = q.back().l, &r = --q.back().r;
            while (l < r) {
                int d = (l + r + 1) >> 1;
                if (ask(q.back().x, d) <= ask(i, d)) r = d - 1;
                else l = d;
            }
        }
        if (q.empty()) q.pb(P(i + m - 1, n, i));
        else if (q.size() && q.back().r != n) q.pb(P(q.back().r + 1, n, i));
    }
    print(ans);
    return 0;
}

合併 (Mergers)

显然把同一个州用并查集整到一坨里,然后剩下的依然是个树。

问题变成用最少的路径覆盖一棵树的所有边,贪心一下,设叶子数为 $c$,答案就是 $\lfloor \frac {c+1}2 \rfloor$。

const int N = 5e5 + 7;
int n, m, a[N], f[N], ans;
vi e[N], p[N];

namespace HLD {
    int d[N], f[N], s[N], son[N], dfn[N], rnk[N], top[N], num;

    void dfs(int x) {
        s[x] = 1;
        for (int y : e[x])
            if (y != f[x]) {
                f[y] = x, d[y] = d[x] + 1;
                dfs(y), s[x] += s[y];
                if (s[y] > s[son[x]]) son[x] = y;
            }
    }

    void dfs(int x, int p) {
        dfn[x] = ++num, rnk[num] = x;
        top[x] = p;
        if (son[x]) dfs(son[x], p);
        for (int y : e[x])
            if (y != f[x] && y != son[x])
                dfs(y, y);
    }

    inline int lca(int x, int y) {
        while (top[x] != top[y]) {
            if (d[top[x]] < d[top[y]]) swap(x, y);
            x = f[top[x]];
        }
        return d[x] < d[y] ? x : y;
    }

    inline void main() {
        d[1] = 1, dfs(1), dfs(1, 1);
    }
}

int get(int x) {
    return x == f[x] ? x : (f[x] = get(f[x]));
}

set<int> s[N];

int main() {
    rd(n, m);
    for (int i = 1, x, y; i < n; i++)
        rd(x, y), e[x].pb(y), e[y].pb(x);
    rda(a, n);
    for (int i = 1; i <= n; i++) p[a[i]].pb(i), f[i] = i;
    HLD::main();
    for (int i = 1; i <= m; i++) {
        if (p[i].empty()) continue;
        int x = p[i][0];
        for (int y : p[i]) {
            x = get(x), y = get(y);
            int z = get(HLD::lca(x, y));
            while (x != z) f[x] = z, x = get(HLD::f[x]);
            while (y != z) f[y] = z, y = get(HLD::f[y]);
        }
    }
    for (int x = 1; x <= n; x++)
        for (int y : e[x])
            if (get(x) != get(y)) s[get(x)].insert(get(y));
    for (int i = 1; i <= n; i++) ans += s[i].size() == 1u;
    print((ans + 1) >> 1);
    return 0;
}

鉱物 (Minerals)

首先用 $2n$ 次将所有元素划分成两个内部没有相同元素的集合 $A,B$。

考虑分治,对于 $m$ 个元素的集合 $A,B$,将 $A$ 的一半与 $B$ 的每一个一起询问。

设 $i$ 个点的询问次数为 $f(i)$,最优情况下可以做到 $f(i) = 2f(\frac i2) + \frac 32i$。

$n = 4.3 \times 10^4$ 时 $f(n) = 1020892$,无法 AC,但能拿 $85$ 分。

考虑不那么平均地分配 $A$ 的「一半」。

假如我们选择了 $A$ 中 $|A| \times p$ 的数,则 $f(i) = f(pi) + f((1-p)i) + (1+p)i$。

取 $p=0.37$ 时能过。

map<int, int> f;

void work(vi a, vi b, int o) {
    int n = a.size();
    if (!n) return;
    if (n == 1) return f[a[0]] = b[0], f[b[0]] = a[0], void();
    int mid = n * 0.37;
    if (!o) mid = n - mid;
    if (!mid) ++mid;
    if (mid == n) --mid;
    vi a1, a2, b1, b2;
    int ret = 0;
    for (int i = 0; i < mid; i++) a1.pb(a[i]);
    for (int i = mid; i < n; i++) a2.pb(a[i]);
    if (o) {
        for (int i = 0; i < mid; i++) ret = Query(a[i]);
        for (int i = 0; i < n; i++)
            if (a1.size() == b1.size()) b2.pb(b[i]);
            else if (a2.size() == b2.size()) b1.pb(b[i]);
            else {
                int now = Query(b[i]);
                if (now != ret) b1.pb(b[i]);
                else b2.pb(b[i]);
                ret = now;
            }
    } else {
        for (int i = mid; i < n; i++) ret = Query(a[i]);
        for (int i = 0; i < n; i++)
            if (a1.size() == b1.size()) b2.pb(b[i]);
            else if (a2.size() == b2.size()) b1.pb(b[i]);
            else {
                int now = Query(b[i]);
                if (now != ret) b1.pb(b[i]);
                else b2.pb(b[i]);
                ret = now;
            }
    }
    work(a1, b1, 0), work(a2, b2, 1);
}

void Solve(int n) {
    int ret = 0;
    vi a, b;
    for (int i = 1; i <= 2 * n; i++) {
        int now = Query(i);
        if (now != ret) a.pb(i);
        else b.pb(i);
        ret = now;
    }
    random_shuffle(a.begin(), a.end());
    random_shuffle(b.begin(), b.end());
    work(a, b, 1);
    for (int i = 0; i < n; i++) Answer(a[i], f[a[i]]);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注