CF1852E 题解

· · 题解

首先有一个显然的观察：对于一个数 x，只有其出现的最左/最右位置会对子区间权重产生影响。那么，可以将每个序列中的数抽象为一个三元组 (L,R,x)。

容易发现，对于 x < y，且 x 的 [L,R] 包含了 y 的 [L,R]，那 x 就不可能是任何子区间的权重，这个数就没用了。

删去这样的数之后，所有的数都会是某个子区间的权重，而且，这样的数的两个端点都已经确定，不会改变。

考虑如何填写那些并不是某个数的区间端点的位置。

一个显然的想法是对位置 i，填 [L,R] 包含它的 (L,R,x) 中 x 最大者，下文设这个值为 b_i。但你发现这么写过不了样例中 1 1 1 1 4 4 3 3 3 的数据。然后你惊奇地发现答案中出现了原序列没有的数。

不过好消息是，只会出现一种新的数，因为如果出现了两种，显然可以把小的数全都变成大的数，子区间权重不变。

设这个数为 now。假设我们已经知道 now 的左右端点 l',r'，那就必须存在一个 x > now 的 (L,R,x)，使得 l' \lt L \lt R \lt r'，否则 now 就会成为某个子区间的权重，产生矛盾。换个角度来说，如果我们枚举这个 x，那么 now 就必须是小于它的，最大的没有出现过的元素，这样显然是最优的。

考虑枚举 x 之后怎么填 now。我们从大到小枚举 x，并将 b_i > now 的位置先填上 b_i。将 b_i \le now 的位置全部填上 now。但这么填还不一定能满足上面的条件，所以如果上一步在 L 的左边没有填上 now，就得找一个 已经填了 b_i 的数，将其改为 now，显然找最小的最优。R 的右边同理。

于是本题就做完了，时间复杂度 O(n \log n)。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define FI first
#define SE second
const int N = 1e5 + 5;
int n,a[N];

pii Mn[N << 2];
void pushup(int k) { Mn[k] = min(Mn[k << 1],Mn[k << 1 | 1]);}
void Change(int k,int l,int r,int pos,int v) {
    if(l == r) { Mn[k] = make_pair(v,pos);return;}
    int mid = l + r >> 1;
    if(pos <= mid) Change(k << 1,l,mid,pos,v);
    else Change(k << 1 | 1,mid + 1,r,pos,v);
    pushup(k);
}
pii Query(int k,int l,int r,int x,int y) {
    if(x <= l && r <= y) return Mn[k];
    int mid = l + r >> 1;
    if(y <= mid) return Query(k << 1,l,mid,x,y);
    else if(x > mid) return Query(k << 1 | 1,mid + 1,r,x,y);
    else return min(Query(k << 1,l,mid,x,y),Query(k << 1 | 1,mid + 1,r,x,y));
}
void build(int k,int l,int r) {
    Mn[k] = make_pair(1e9,1e9);
    if(l == r) return;
    int mid = l + r >> 1;
    build(k << 1,l,mid);build(k << 1 | 1,mid + 1,r);
}
vector<int> vals,usd;
map<int,vector<int> > Qu;
int Ans[N];
inline void work() {
    vals.clear();Qu.clear();
    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> a[i],Qu[Ans[i] = a[i]].push_back(i);
    for(auto i : Qu) vals.push_back(i.FI);
    build(1,1,n);
    usd.clear();
    reverse(vals.begin(),vals.end());
    for(auto &i : Qu) {
        for(int j = 1;j < i.SE.size() - 1;j++)
            Ans[i.SE[j]] = 0;
    }

    for(auto i : vals) {
        int l = Qu[i][0],r = Qu[i].back();
        if(Query(1,1,n,l,r).FI <= r)
            Ans[l] = Ans[r] = 0;
        else Change(1,1,n,l,r),usd.push_back(i);
    }
    vector<int> lst(usd.size());
    lst.back() = usd.back() - 1;
    for(int j = lst.size() - 2;j >= 0;j--)
        if(usd[j] - 1 != usd[j + 1]) lst[j] = usd[j] - 1;
        else lst[j] = lst[j + 1];

    long long mxans = 0;
    int mxval = 0;
    build(1,1,n);
    set<int> S;
    for(int i = 1;i <= n;i++) if(!Ans[i]) S.insert(i),Change(1,1,n,i,-1);
    long long sum = 0; // 比 t 大的数之和 
    vector<pair<int,int> > Upd;
    int lnew = -1,rnew = -1;
    int poi = 0;
    for(int t = 0;t < usd.size();t++)
    {
        while(poi < usd.size() && usd[poi] > lst[t]) {
            int l = Qu[usd[poi]][0],r = Qu[usd[poi]].back();
            auto it = S.lower_bound(l);
            while(it != S.end() && *it <= r) {
                sum += usd[poi];
                Change(1,1,n,*it,usd[poi]);
                Upd.emplace_back(*it,usd[poi]);
                it = S.erase(it);
            }
            ++poi;
        }
        if(!lst[t]) continue;
        int L = Qu[usd[t]][0],R = Qu[usd[t]].back();
        if(L == 1 || R == n) continue;
        pii lp = Query(1,1,n,1,L - 1),rp = Query(1,1,n,R + 1,n);
        if(lp.FI >= 1e9 || rp.FI >= 1e9) continue;
        long long add = lst[t] * S.size() + (lp.FI == -1 ? 0 : lst[t] - lp.FI) + (rp.FI == -1 ? 0 : lst[t] - rp.FI);
        if(lst[t] && sum + add > mxans) {
            mxans = sum + add;
            mxval = lst[t];
            lnew = (lp.FI == -1 ? -1 : lp.SE);
            rnew = (rp.FI == -1 ? -1 : rp.SE);
            while(!Upd.empty()) {
                Ans[Upd.back().FI] = Upd.back().SE;
                Upd.pop_back();
            }
        }
    }
    if(S.size() == 0 && sum > mxans) {
        mxans = sum;
        lnew = rnew = -1;
        while(!Upd.empty()) {
            Ans[Upd.back().FI] = Upd.back().SE;
            Upd.pop_back();
        }
    }
    if(~lnew) Ans[lnew] = 0;
    if(~rnew) Ans[rnew] = 0;
    for(int i = 1;i <= n;i++)
        printf("%d ",Ans[i] ? Ans[i] : mxval);
    printf("\n");
}   
int main()
{
    int T;
    cin >> T;
    while(T--) work();
    return 0;
}