P6198 [EER1]单调栈 题解(分治+构造)

题目链接

题目大意

如果没有值，那么\(a[i]=a[i-1]+1\)最优

具体证明我不太会 但是栈元素如果多了，到时候可以变少，少了却不能变多了

然后确定所有\(a[i]\) 如果\(a[i]>a[i-1]+1\)就不存在，因为每次最多入栈一个元素

然后再进行分治求解即可

分治的过程有点意思

复杂度\(O(n)\)

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
const ll INF=0x3f3f3f3f3f3f3f3f;
int n,cnt;
int a[maxn];
vector<int> vec[maxn];
int ans[maxn];
void solve(int l,int r,int val){
    if(l>r) return ;
    vector<int> temp;
    for(int i=vec[val].size()-1;i>=0;i--){
        if(vec[val][i]>r) break;
        temp.push_back(vec[val][i]);
    }
    reverse(temp.begin(),temp.end());
    for(auto i:temp){
        ans[i]=++cnt;
    }
    solve(l,vec[val].back()-1,val+1);
    int x=vec[val].back()+1;
    vec[val].pop_back();
    while(vec[val].size()&&vec[val].back()<=r){
        solve(x,vec[val].back()-1,val+1);
        x=vec[val].back()+1;
        vec[val].pop_back();
    }
    solve(x,r,val+1);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    bool flag=1;
    for(int i=1;i<=n;i++){
        if(a[i]==-1){
            a[i]=a[i-1]+1;
        }else if(a[i]>a[i-1]+1){
            flag=0;
            break;
        }
    }
    for(int i=n;i>=1;i--){
        vec[a[i]].push_back(i);
    }
    if(!flag){
        cout<<-1<<'\n';
    }else{
        solve(1,n,1);
        for(int i=1;i<=n;i++){
            cout<<ans[i]<<" ";
        }
    }
    return 0;
}