题解：P14030 【MX-X20-T4】「FAOI-R7」连接时光 I

DSD486 · 2026-11-12 17:29:42 · 题解

简单 \mathcal{O}(n) 做法。

设 f_i 表示前 i - 1 个数中有多少个 p_j > p_i。

对于 a_i \ge 0，我们希望 f_i = i - 1。

对于 a_i < 0，我们希望 f_i = 0。

考虑 a_n \ge 0，此时可以达到期望。

具体地，将 a 中的非负数按顺序编号为 m , m - 1 , \dots , 2 , 1，负数按顺序编号为 m + 1 , m + 2 , \dots , n。

由于 a_n \ge 0，每个数会向 n 连边，所以连通。同时容易看出达到期望。

考虑全负数。

贪心的想，我们只希望代价最小即 a_i 最大的点去连边保证连通。

那么对于后缀最大值的点 x，可以让同为后缀最大值的 y(y < x) 到 x - 1 都向 x 连边。

此时代价为后缀最大值求和，显然没有更少代价。

结合起来，考虑找出最大的 k 使得 a_k \ge 0。

序列被分为两部分，[1 , k] , (k , n]。

对于后部分，全为负数，套用上面的做法。

前部分 a_k \ge 0，也套用上面的做法。

然后将前部分看作一个整体，让后部分后缀最大值向前半部分连边即可。

此时我们可以得出 f，尝试还原 p。

一个简洁做法是 \mathcal{O}(n \log n) 的树状数组倍增。

::::success[Code]

#include <bits/stdc++.h>
//#define int long long
#define PII pair < int , int >
#define x first
#define y second
using namespace std ; 
bool bbb ; 

const int N = 2e5 + 5 , inf = 1e9 ; 
int n , c[N] , mx[N] ; 
int f[N] , a[N] ; 
int tr[N] ; 
#define lowbit(x) (x & -x)
void add(int x , int d){ while(x <= n) tr[x] += d , x += lowbit(x) ; }
int sum(int x){ int res = 0 ; while(x) res += tr[x] , x -= lowbit(x) ; return res ; }
void solve(){
    cin >> n ; 
    for(int i = 1 ; i <= n ; i++) cin >> c[i] ; 
    int p = 0 ; 
    mx[n + 1] = -inf ; 
    for(int i = n ; i >= 1 ; i--){
        mx[i] = max(mx[i + 1] , c[i]) ; 
        if(!p && mx[i] >= 0) p = i ; 
    }
    for(int i = 1 ; i <= p ; i++)
        f[i] = c[i] >= 0 ? i - 1 : 0 ; 
    int lat = p ? p : 1 ; 
    for(int i = p + 1 ; i <= n ; i++)
        if(c[i] == mx[i]){
            f[i] = i - lat ; 
            lat = i ; 
        }
    long long ans = 0 ; 
    for(int i = 1 ; i <= n ; i++) ans += 1ll * f[i] * c[i] ; 
    cout << ans << '\n' ; 
    for(int i = 1 ; i <= n ; i++) add(i , 1) ; 
    for(int i = n ; i >= 1 ; i--){
        int x = 0 , s = 0 , rk = i - f[i] ; 
        for(int j = __lg(n) ; ~j ; j--)
            if(x + (1 << j) <= n && s + tr[x + (1 << j)] < rk)
                x += 1 << j , s += tr[x] ; 
        ++ x ; 
        a[i] = x , add(x , -1) ; 
    }
    for(int i = 1 ; i <= n ; i++)
        cout << a[i] << (i == n ? '\n' : ' ') , 
        f[i] = a[i] = c[i] = 0 ; 
}

bool eee ; 
signed main(){
//  freopen("light.in" , "r" , stdin) ; 
//  freopen("light.out" , "w" , stdout) ; 
    ios :: sync_with_stdio(0) ; 
    cin.tie(0) ; cout.tie(0) ; 
    cerr << "Memory: " << abs((char*)&eee - (char*)&bbb) / 1024.0 / 1024.0 << " MB\n" ; 
    int T ; cin >> T ; 
    while(T--) solve() ; 
    return 0 ; 
}
/*
4
2 4 -2 0

6
7 1 -1 -7 1 -2

*/

::::

这里是 \mathcal{O}(n) 做法。

前部分就是上面的构造。

此时考察一个块 (l , r]，r 肯定是后缀最大值。