https://ac.nowcoder.com/acm/problem/14893

说一下这题用树状数组的解法

树状数组是比较暴力直观的想法，也是我读完题的第一个想法。它不是最好的解法

第一步，贪心思想

首先还是贪心的思想，对于每一次入栈之后，设t为栈顶元素，那么就要判断这个时候取t是不是最优解，如何判断最优解呢？

如果比t大的数已经在栈中出现过（也就是已经输入过），那么此时取t就是最好的情况，否则在答案中这一位置上的数就会更小，那就不是字典序最大了，就不是最优解了。此时就要让t出栈，答案数组res就要push_back(t)。注意这是一个循环。我写了一个while循环。

否则，就继续入栈。

第二步，树状数组的想法

第一步中提到 “如果比t大的数已经在栈中出现过（也就是已经输入过）” 这句话，那么我们就要用一个数据结构存这个信息。用数组作映射，下标为1~n中的数，对应的值应该是大于等于下标的数出现的次数。这个数组名字为v。那么如果v[i]==i，那么栈顶元素t出栈。所以每次入栈的时候，也就是输入的时候，都涉及到v数组的改动。我们发现这是一个区间修改＋单点查询。所以，树状数组，启动！！

```//附上代码，写的不太好
#include<bits/stdc++.h>
using namespace std;
#define int long long

int tree[1000001]={0};
vector<int>res;
int n;
    
int lowbit(int x){
    return x&(-x);
}
int sum(int x){
    int ans=0;
    while(x>0){
        ans+=tree[x];
        x-=lowbit(x);
    }
    return ans;
}
void update(int x,int d){
    while(x<=n){
        tree[x]+=d;
        x+=lowbit(x);
    }
}
//以上为树状数组
signed main(){
    cin>>n;
    vector<int>v(n+1,0);
//其实可以不用数组v，因为初始化每个元素都为0，
//树状数组有差分的思想，原数组v其实没什么用。
   
    for(int i=1;i<=n;i++){
        update(i,v[i]);
    }
    vector<int>sta;//栈，用vector代替
    for(int i=0;i<n;i++){
        int t;
        cin>>t;
        sta.push_back(t);
        update(1,1);
        update(t+1,-1);
        while(!sta.empty()){
            if(sum(t)==n-t+1){
                sta.pop_back();
                res.push_back(t);
            }
            else break;
            t=sta.back();
        }
    }
    for(int i=0;i<res.size();i++){
        cout<<res[i]<<" ";
    }
}
注：未经许可不可转载