设 last[x] 表示使 bi = x 的最大的 i，即 bi 中 x 最后出现的位置.
这样问题就转换为 bi = min last[x]<i−ci{x}，也就是满足 last[x] < i−ci 的最小的 x，其中 1 ≤x≤n+ 1,x∈N∗. 可以用线段树维护 last[1..(n+ 1)] 每个区间的最小值. 查询的时候给定一个值 v = i−ci，从最大的区间往下查找， 如果左子区间的最小值大于等于 v，则递归查找右子区间； 否则递归查找左子区间. 当区间长度为 1 时，此区间的左 (右) 端点就是答案，返回之. 得到 bi 后，更新 last[bi] = i，再进行后面的计算. 注意初始时 last[1] = 0，其他 last 值全为小于 0 的值.
以上引用自UESTC 傅大爷 的题解
//389MS 31804KB
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int MAX=1e6+5;
const int INF=0x3f3f3f3f;
int c[MAX];
int tree[MAX*4];
void read(int &x)
{
int f=1;x=0;char s=getchar();
while (s<'0'||s>'9'){if (s=='-')f=-1;s=getchar();}
while (s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
void update(int r,int L,int R,int pos,int val)
{
if (L==R)
{
tree[r]=val;
return ;
}
int mid=(L+R)>>1;
if (pos<=mid) update (r*2,L,mid,pos,val);
else update (r*2+1,mid+1,R,pos,val);
tree[r]=tree[r*2]>tree[r*2+1]?tree[r*2+1]:tree[r*2];
}
int query(int r,int L,int R,int top)
{
if (L==R) return L;
int mid=(L+R)>>1,ans;
if (tree[r*2]<top) ans=query(r*2,L,mid,top);
else ans=query(r*2+1,mid+1,R,top);
return ans;
}
int main ()
{
int n;
read(n);
for (int k=1;k<=n;k++)
read(c[k]);
memset(tree,-1,sizeof(tree));
update(1,1,n+1,1,0);
for (int k=1;k<=n;k++)
{
int x=query(1,1,n+1,k-c[k]);
update(1,1,n+1,x,k);
printf ("%d ",x);
}
return 0;
}