专栏文章

题解：AT_arc114_f [ARC114F] Permutation Division

MMoyou
AT_arc114_f题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip8ec51
此快照首次捕获于
2025/12/03 07:50
3 个月前
此快照最后确认于
2025/12/03 07:50
3 个月前
查看原文

[ARC114F] Permutation Division 题解

考虑二分不变前缀的长度，判定的时候，如果前缀分为了 ii 段，且最后一段开头为 xx，那么这个前缀之后的所有段开头都要小于 xx，并且这个前缀之后应当至少有 k−ik - i 段，所以选择最小的 k−ik -i 个数作为开头就行，并且显然这种贪心是最优的，预处理 cnticnt_i 表示后半部分 ≤i\le i 的个数（或者第 ii 小应该也可以）。
同时我们发现，前缀划分后，每段开头形成了一个最长下降子序列（LDS），所以我们可以预处理出 gig_i 表示长度为 ii 的 LDS 结尾最大值。
根据 cnt,gcnt, g 可以判定一个前缀是否可以是不变的。
最后计算答案的时候，这个前缀之后的段开头一定是最 k−ik - i 小的那些数，这也是好处理的。
CPP
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define int long long
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10;

int n, m, p[N], tr[N];
void update(int u, int c) {
    for(; u; u &= u - 1)
        tr[u] = max(tr[u], c);
}
int query(int u) {
    int sum = -1e9; for(; u <= n; u += u & -u)
        sum = max(tr[u], sum);
    return sum;
}
int cnt[N], g[N], f[N];
int check(int mid) {
    for(int i = 1; i <= n; i ++) cnt[i] = 0, tr[i] = -1e9;
    for(int i = mid + 1; i <= n; i ++)
        cnt[p[i]] ++;
    for(int i = 1; i <= n; i ++) cnt[i] += cnt[i - 1];
    for(int i = 1; i <= mid + 1; i ++) g[i] = -1e9;
    update(p[1], 1), f[1] = 1, g[1] = p[1];
    for(int i = 2; i <= mid; i ++) {
        f[i] = query(p[i]) + 1;
        if(f[i] > 0) {
            g[f[i]] = max(g[f[i]], p[i]);
            update(p[i], f[i]);
        }
    }
    for(int i = mid; i; i --) g[i] = max(g[i], g[i + 1]);
    for(int i = mid; i; i --) if(g[i] >= 0 && i + cnt[g[i]] >= m)
        return i;
    return 0;
}
bool fr[N];
signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> p[i];
    int l = 1, r = n, mid, ans = 0;
    while(l <= r) {
        mid = l + r >> 1;
        if(check(mid)) l = mid + 1, ans = mid;
        else r = mid - 1;
    }
    int x = (ans == 0 ? m : cnt[g[check(ans)]]);
    for(int i = 1; i <= ans; i ++) cout << p[i] << ' ';
    if(ans == n) return 0;
    vector<PII> t;
    for(int i = ans + 1; i <= n; i ++) t.push_back({p[i], i});
    sort(t.begin(), t.end());
    int y = t[x - 1].x;
    for(int i = ans + 1; i <= n; i ++) fr[i] = (p[i] <= y);
    for(int i = x - 1; ~i; i --) {
        int j = t[i].y;
        while(j + 1 <= n && !fr[j + 1]) j ++; 
        for(int k = t[i].y; k <= j; k ++) cout << p[k] << ' ';
    }
    cout << '\n';
    
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...