线段树灵活运用--2018 UESTC Training for Data Structures 一棵像样的线段树

设 xem 表示集合中最小的未出现的正整数， 如 xem{}=1，xem{1,3,4}=2
定义
bi=xem{bi−ci,bi−ci+1,...,bi−1},i=1,2,...,n
特别的，b0=1
给定 n 和 c1,c2,...,cn，请你计算出 b1,b2,...,bn
Input
第一行一个整数 n (1≤n≤106)n (1≤n≤106).
第二行 n个用空格分隔的整数 c1,c2,...,cn， 保证 1≤ci≤i 
Output
输出一行 n 个用空格分隔的整数， 依次为 b1,b2,...,bn

Sample Input
6
1 2 3 1 3 4
Sample Output

2 3 4 1 2 5

这道题想了好久 一开始想着动态维护每个后缀的mex值 不过发现好像很难做到 无奈看了下别人的做法才知道原来可以这样做：先观察下样例 根据题意发现其实b【i】求的实质就是从1数到n 第一个不位于（i-c【i】，i-1）的数就是答案了 在转化一下 就是在1到n中选一个尽可能小的数 若他在【b【0】，b【i-1】】中最后一个出现的位置j假设比i-c【i】小的话 那这个x就是答案了 那么我们就可以用一棵线段树来维护1-n中每个数最后一次出现的位置的最小值 每次查询的时候就那i-c【i】来比较 左半区的最小值比i-c【i】小的话 就继续查询左半区 否则查询右半区（因为左半区是1到n>>1|1肯定比右半区小） 然后更新的话就把对应的值改成他当前的位置就好了

AC代码：

#include <set>
#include <map>
#include <list>
#include <deque>
#include <cmath>
#include <queue>
#include <stack>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <cstring>
#include <fstream>
#include <iostream>
#include <algorithm>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;

const int maxn=1e6+5;
int mn[maxn<<2];
int c[maxn];
int b[maxn];

void pushup(int rt)
{
    mn[rt]=min(mn[rt<<1],mn[rt<<1|1]);
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        if(l==1) mn[rt]=0;
        else mn[rt]=-1;
        return;
    }
    int m=l+(r-l)/2;
    build(l,m,rt<<1);
    build(m+1,r,rt<<1|1);
    pushup(rt);
}
void update(int pos,int be,int l,int r,int rt)
{
    if(l==r)
    {
        mn[rt]=be;
        return;
    }
    int m=l+(r-l)/2;
    if(pos<=m) update(pos,be,l,m,rt<<1);
    else update(pos,be,m+1,r,rt<<1|1);
    pushup(rt);
}
int query(int l,int r,int rt,int tr)
{
    if(l==r)
    {
        return l;
    }
    int m=l+(r-l)/2;
    if(mn[rt<<1]<tr) return query(l,m,rt<<1,tr);
    else return query(m+1,r,rt<<1|1,tr);
}
int main()
{
    int n;
    scanf("%d",&n);
    build(1,n,1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&c[i]);
        int ans=query(1,n,1,i-c[i]);
        printf("%d",ans);
        if(i!=n) printf(" ");
        update(ans,i,1,n,1);
    }
    return 0;
}