题解：CF2071F Towering Arrays

· · 题解

平衡树卡常带师！

题意

称一个序列 a_{1\sim n} 是 p - towering 的，当存在一个位置 a_i，使得对于任意 a_j 都有 a_j\ge p-|i - j|。

给定 a，可以将 a 中不超过 k 个元素删去。求删去后可以使 a 为 p - towering 的最大 p。

思路

注意到删的越多 p 能够越大；p 越大需要删的也越多。于是二分答案 p，并判断至少需要删几个。

由于绝对值限制且左右两边相对独立，于是我们枚举中心点 mid（也就是条件中的 i），并前后缀各自做一遍 dp 看左边和右边能够选择的最长长度。

以前缀为例，设 dp_{i,j} 表示考虑了前缀 1\sim i，最后一个到中心点的距离是 j（即剩余 j 个要选），能够选的最长长度。于是我们有：

dp_{i,j}=\begin{cases} dp_{i-1,j} & j<p-a_i\\ dp_{i-1,j+1}+1 & j\ge p-a_i \end{cases}

其中 i+j\le n。

至于为什么第二项能够直接取而不和 dp_{i-1,j} 取 \max：根据归纳法可以证明 dp_{i,0\sim n-i} 是单调不减的，那么

容易发现，每次从 dp_{i-1} 转移到 dp_i 时，就是以 dp_{i,p-a_i} 为分界线，右半边整体 +1，最后将左边的和右边的拼在一起。这个可以方便地使用 FHQ-Treap 维护。

而对于枚举的中心点 mid，左半边的答案便是 dp_{mid,0}。

右半边同理，除了倒着扫一遍，其余全部一样。

最后对每个 mid 判断是否 lans + rans - 1\ge n-k，是即合法。

时间复杂度 O(n\log n\log V)。但是常数有亿点大。我们需要进行一下优化：

  1. split 时可以专门写一个只分裂一个出来的函数，理论上来说可以减少一点常数；并且这个函数不要用递归写。

  2. check 时找到一个合法位置就退出。

  3. 值域取 [0,\max{a_i}]。

这样最慢点 #29 3718ms。

代码

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
ll T, n, k, a[200002], ans[200002], rt, maxv, st[200002], len;
struct node {
    ll v, sz, ls, rs, pr, lt;
}tr[200002];
inline void pu(ll x) {
    tr[x].sz = tr[tr[x].ls].sz + tr[tr[x].rs].sz + 1;
}
inline void pd(ll x) {
    if (! x) return;
    tr[tr[x].ls].lt += tr[x].lt, tr[tr[x].ls].v += tr[x].lt;
    tr[tr[x].rs].lt += tr[x].lt, tr[tr[x].rs].v += tr[x].lt;
    tr[x].lt = 0;
}
void split(ll x, ll ss, ll &lrt, ll &rrt) {
    if (! x) return lrt = rrt = 0, void(0);
    pd(x);
    if (tr[tr[x].ls].sz + 1 <= ss) lrt = x, split(tr[x].rs, ss - tr[tr[x].ls].sz - 1, tr[x].rs, rrt), pu(x);
    if (tr[tr[x].ls].sz + 1 >  ss) rrt = x, split(tr[x].ls, ss, lrt, tr[x].ls), pu(x);
}
inline void split1(ll x, ll &lrt, ll &rrt) { // 只分一个出来 
    if (! tr[x].ls) pd(x), lrt = x, rrt = tr[x].rs, tr[x].rs = 0, tr[x].sz = ! (! x);
    else {
        rrt = x, tr[x].sz --;
        while (tr[tr[x].ls].ls) pd(x), x = tr[x].ls, tr[x].sz --;
        pd(tr[x].ls), lrt = tr[x].ls, tr[x].ls = tr[lrt].rs, tr[lrt].rs = 0, tr[lrt].sz = 1;
    }

}
ll merge(ll lrt, ll rrt) {
    if (!lrt || !rrt) return lrt | rrt;
    pd(lrt), pd(rrt);
    if (tr[lrt].pr >= tr[rrt].pr) return tr[lrt].rs = merge(tr[lrt].rs, rrt), pu(lrt), lrt;
    if (tr[lrt].pr <  tr[rrt].pr) return tr[rrt].ls = merge(lrt, tr[rrt].ls), pu(rrt), rrt;
}
inline ll minn(ll x) {
    while (tr[x].ls) pd(x), x = tr[x].ls;
    return tr[x].v;
}
bool check(ll p) {
    rt = 0;
    ll res = 0;
    for (ll i = 1; i <= n + 1; i ++ ) tr[i] = {0, 1, 0, 0, (rand() << 16) | rand(), 0}, rt = merge(rt, i);
    for (ll i = 1, lrt, rrt, trt; i <= n; i ++ ) { // 前缀 
        split(rt, p - a[i], lrt, rrt); // 按照 p - a[i] 切开 
        split1(rrt, trt, rrt); // 把 dp[p - a[i]] 分出来扔掉 
        if (rrt) tr[rrt].lt ++, tr[rrt].v ++, pd(rrt);
        rt = merge(lrt, rrt); // 把左右两边拼起来 
        ans[i] = minn(rt); 
    }
    rt = 0;
    for (ll i = 1; i <= n + 1; i ++ ) tr[i] = {0, 1, 0, 0, (rand() << 16) | rand(), 0}, rt = merge(rt, i);
    for (ll i = n, lrt, rrt, trt; i >= 1; i -- ) { // 后缀，同理 
        split(rt, p - a[i], lrt, rrt);
        split1(rrt, trt, rrt);
        if (rrt) tr[rrt].lt ++, tr[rrt].v ++, pd(rrt);
        rt = merge(lrt, rrt);
        if (ans[i] + minn(rt) - 1 >= n - k) return 1;
    }
    return 0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> T;
    while (T -- ) {
        cin >> n >> k;
        maxv = 0;
        for (ll i = 1; i <= n; i ++ ) cin >> a[i], maxv = max(maxv, a[i]);
        ll l = 0, r = maxv, res;
        while (l <= r) {
            ll mid = l + r >> 1;
            if (check(mid)) res = mid, l = mid + 1;
            else r = mid - 1;
        }
        cout << res << "\n";
    }
}