Description
现在有一个从 $ 1 $ 到 $ n $ 的一个全排列,但是你不知道这个排列到底是什么,但是你有一个 $ sum[i] $,其中 $ sum[i] $ 表示 $ sum_{j=1}^{i-1}(a_j<a_i)?a_j:0 $,现在给你 $ sum $ 数组,让你求出这个排列 $ a $
Solution
首先找到最靠后的 (0),将这个位置 (s) 赋值为 (infty),(a) 赋值为 (1),同时将它后面所有的 (s-1),重复下去即可
用线段树维护
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int a[N],val[N],tag[N],n;
void pushup(int p) {
val[p]=min(val[p*2],val[p*2+1]);
}
void pushdown(int p) {
if(tag[p]) {
val[p*2]+=tag[p];
val[p*2+1]+=tag[p];
tag[p*2]+=tag[p];
tag[p*2+1]+=tag[p];
tag[p]=0;
}
}
void build(int p,int l,int r) {
if(l==r) {
cin>>val[p];
}
else {
build(p*2,l,(l+r)/2);
build(p*2+1,(l+r)/2+1,r);
pushup(p);
}
}
void modify(int p,int l,int r,int pos,int key) {
if(l==r) {
val[p]=key;
}
else {
pushdown(p);
if(pos<=(l+r)/2) modify(p*2,l,(l+r)/2,pos,key);
else modify(p*2+1,(l+r)/2+1,r,pos,key);
pushup(p);
}
}
void change(int p,int l,int r,int ql,int qr,int delta) {
if(l>qr || r<ql) return;
if(l>=ql && r<=qr) {
val[p]+=delta;
tag[p]+=delta;
}
else {
pushdown(p);
change(p*2,l,(l+r)/2,ql,qr,delta);
change(p*2+1,(l+r)/2+1,r,ql,qr,delta);
pushup(p);
}
}
int query(int p,int l,int r,int ql,int qr) {
if(l>qr || r<ql) return 1e12;
if(l>=ql && r<=qr) return val[p];
pushdown(p);
return min(query(p*2,l,(l+r)/2,ql,qr),query(p*2+1,(l+r)/2+1,r,ql,qr));
}
int ask(int p,int l,int r,int ql,int qr) {
if(l==r) return l;
pushdown(p);
if(val[p*2+1]==0) return ask(p*2+1,(l+r)/2+1,r,ql,qr);
return ask(p*2,l,(l+r)/2,ql,qr);
}
signed main() {
ios::sync_with_stdio(false);
cin>>n;
build(1,1,n);
for(int i=1;i<=n;i++) {
int p=ask(1,1,n,1,n);
modify(1,1,n,p,1e12);
change(1,1,n,p+1,n,-i);
a[p]=i;
}
for(int i=1;i<=n;i++) cout<<a[i]<<" ";
}