题意:对应每个 i 给出一个数si,代表i之前比ai小的值的和,求原序列。
对着样例乱猜看出来最后一个0的位置就是1,进一步想到,把1出现的位置之后都减去1,
然后从整个序列里再找最右边(优先搜索右子树实现)的0就是2,然后又是新一轮构造------
想拿树形结构维护,每次要找的是0,一开始思维局限在找0上,其实这个0也是最小值呀摔,
线段树维护的无非那几样东西,最大最小区间和,0是最小值就每次维护最小值就好了,每次进行减操作就是区间修改,
还有要消去前面计算过的0对后面的0的影响,每次求出一个答案都要把0的位置修改为INF。
差不多是个线段树板子,重点在怎么找到要求的东西和你维护的东西之间的关系,实在不知道维护什么可以想想这样可以求出来啥嘛
#include <bits/stdc++.h>
using namespace std;
#define endll '\n'
#define C getchar()
typedef long long ll;
#define pi acos(-1.0)
#define INF 0x3f3f3f3f
#define mod 1000000007
#define pii pair<int, int>
const int MAXN = 4e5 + 10;
#define stop system("pause")
#define lowbit(x) ((x) & (-x))
#define Temp template <typename T>
#define all(vc) vc.begin(),vc.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
Temp inline void rd(T &s)
{
s = 0;T t = 1, k = C;
for (; k < '0' || k > '9'; k = C)if (k == '-') t = -1;
for (; k >= '0' && k <= '9'; k = C) s = (s << 1) + (s << 3) + (k ^ 48);
s *= t;
}
int n;
struct Segment_Tree
{
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
ll minv[MAXN<<2],lazy[MAXN<<2];
inline int ls(int p) {return p<<1;}
inline int rs(int p) {return p<<1|1;}
inline void push_up(int p) {minv[p] = min(minv[ls(p)],minv[rs(p)]);}
inline void push_down(int p)
{
minv[ls(p)]-=lazy[p],minv[rs(p)]-=lazy[p];
lazy[ls(p)]+=lazy[p],lazy[rs(p)]+=lazy[p];
lazy[p]=0;
}
void build(int rt,int l,int r)
{
lazy[rt]=0;
if(l==r) {rd(minv[rt]); return ;}
int mid = (l+r)>>1;
build(lson);build(rson);push_up(rt);
}
int Querymin(int v,int rt,int l,int r)//单点查询,查询最小值所在位置
{
if(l==r) return l;
if(lazy[rt]) push_down(rt);
int mid=(l+r)>>1;
if(minv[rs(rt)]<=v) return Querymin(v,rson);//
else return Querymin(v,lson);
}
void update(int q,int rt,int l,int r)//单点更新
{
int mid = (l+r)>>1;
if(l==r) {minv[rt] = 1e11; return ;}
if(q<=mid) update(q,lson);
else update(q,rson);
push_up(rt);
}
void update(int ql,int qr,int v,int rt,int l,int r)//区间更新
{
if(ql>r||qr<l) return;
if(ql<=l && qr>=r) {lazy[rt]+=v,minv[rt]-=v;return;}
if(lazy[rt]) push_down(rt);
int mid=(l+r)>>1;
update(ql,qr,v,lson);update(ql,qr,v,rson);
push_up(rt);
}
}tree;
int ans[MAXN];
int main()
{
rd(n);
tree.build(1,1,n);
for(int i=1;i<=n;++i)
{
int tmp=tree.Querymin(0,1,1,n);
ans[tmp]=i;
tree.update(tmp,1,1,n);
if(tmp!=n) tree.update(tmp+1,n,i,1,1,n);
}
for(int i=1;i<=n;++i) printf("%d ",ans[i]);
cout<<endll;
//stop;
return 0;
} 
京公网安备 11010502036488号