题意:对应每个 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; }