题目大意,给定 $\sum \limits_{a_i<a_x}a_i$ 询问这个排列

最后的一个点显然是一段连续的序列求和,因此知道这个点的答案,并且这个点贡献不了进其他答案,在考虑倒数第二个,如果倒数第一个能贡献答案的话,那就说明也是个连续区间,否则不是,整理一下思路,发现倒过来用树状数组模拟这个过程即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<vector>
#include<set>
#include<map>
#include<algorithm>

using namespace std;

typedef long long ll;

namespace mstd{

//change it if ll

inline void qread(int &x)
{
int f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

inline void qread(ll &x)
{
ll f=1; x=0; static char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-f; c=getchar();}
while(isdigit(c)) x=x*10+c-'0',c=getchar();
x*=f; return ;
}

}

const int maxn=200200;

ll c[maxn];

ll n,m,a[maxn];
int ans[maxn];

struct treerry_tree{

inline int lowbit(int x) {return x&(-x);}
inline void add(int x,int y) { while(x<=n) c[x]+=y,x+=lowbit(x); }
inline ll ask(int x){ll ans=0; while(x) ans+=c[x],x-=lowbit(x); return ans;}

}st;

inline int getpla(ll x)
{
int l=1,r=n,mid,ans=0;
while(l<=r)
{
mid=(l+r)>>1;
if(st.ask(mid)<=x) l=mid+1,ans=mid;
else r=mid-1;
}
return ans;
}

int main()
{
int i,j;
mstd::qread(n);
for(i=1;i<=n;i++) mstd::qread(a[i]),st.add(i,i);
for(i=n;i;i--)
{
ans[i]=getpla(a[i])+1;
st.add(ans[i],-ans[i]);
}
for(i=1;i<=n;i++) printf("%d ",ans[i]);
return 0;
}