CF1208D Restore Permutation

题目传送门

思路

别的题解讲的比较奇妙，来一篇易懂的题解。

首先我们发现最后一个位置的值是可以首先确定的，因为它前面的数已经填完了。

设最后一个位置的数为 \(x\)，则它的贡献就是 \(\frac{x \times (x+1)}{2}\)，所以最后一个数就是满足 \(\frac{x \times (x+1)}{2}=a_n\) 的 \(x\)。

以此类推，我们从后往前考虑，对于每个节点的数可以二分求得，直接树状数组动态维护前缀和即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
int const N=1e6+10;
int a[N],ans[N],n,vis[N];
struct Tree_Array{
    int c[N];
    inline int lowbit(int x){return x&-x;}
    inline void update(int x,int v){while (x<=n) c[x]+=v,x+=lowbit(x);}
    inline int query(int x){int res=0;while (x) res+=c[x],x-=lowbit(x);return res;}
}T;
inline int check(int x){return (x+1)*x/2-T.query(x);}
inline int qry(int x){
    int l=0,r=n;
    while (l<r){
        if (l+1==r){
            if (check(r)<=x) ++l;
            break;
        }
        int mid=(l+r)>>1;
        if (check(mid)>x) r=mid-1;
        else l=mid;
    }
    return l+1;
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i=1;i<=n;++i) cin>>a[i];
    for (int i=n;i>=1;--i){
        ans[i]=qry(a[i]);
        T.update(ans[i],ans[i]);
    }
    for (int i=n;i;--i){
        while (vis[ans[i]]) --ans[i];
        vis[ans[i]]=1;
    }
    for (int i=1;i<=n;++i) cout<<ans[i]<<' ';
    cout<<'\n';
    return 0;
}