11525 - Permutation

 
训练指南P248：  
不过刚开始这题理解错了，不是找大于val的没有使用过的值，而是找从1开始没有使用过的第val+1个数，并把这个数输出才对  
//#pragma comment(linker, "/STACK:1024000000,1024000000")  
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
  
#define INF 0x3fffffff  
#define N 50010  
#define M (50010 << 2)  
#define LL long long  
#define mod 95041567  
  
using namespace std;  
  
struct Node{  
    int set, sum;  
};  
  
Node p[M];  
int flag, cnt;  
  
void maintain(int rt){  
    if(p[rt].set) return ;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    p[lc].set = p[rc].set = p[rt].set;  
}  
  
void build(int rt, int l, int r){  
    p[rt].set = 0;  
    int mid = (r - l) / 2 + l;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    if(l == r){  
        p[rt].sum = 1;  
        return;  
    }  
    build(lc, l, mid);  
    build(rc, mid + 1, r);  
    p[rt].sum = p[lc].sum + p[rc].sum;  
}  
  
void update(int rt, int l, int r, int val){  
  //  printf(" %d %d %d %d %d\n", l, r, p[rt].sum, p[rt].set, cnt);  
    if(p[rt].set == 1) return;  
    int mid = (r - l) / 2 + l;  
    int lc = rt << 1;  
    int rc = lc + 1;  
    if(l == r){  
        p[rt].set = 1;  
        p[rt].sum = 0;  
        if(flag) printf(" %d", l);  
        else printf("%d", l), flag = 1;  
        cnt = 1;  
        return;  
    }  
    maintain(rt);  
    if(!cnt && val <= p[lc].sum && p[lc].set != 1) update(lc, l, mid, val);  
    if(!cnt && val - p[lc].sum <= p[rc].sum && p[rc].set != 1) update(rc, mid + 1, r, val - p[lc].sum);  
    if(p[lc].set == p[rc].set && p[lc].set != -1) p[rt].set = p[lc].set;  
    else if(p[lc].set == -1 || p[rc].set == -1) p[rt].set = -1;  
    else if(p[lc].set + p[rc].set == 1) p[rt].set = -1;  
    p[rt].sum = p[lc].sum + p[rc].sum;  
   // printf(" %d %d %d %d %d\n", l, r, p[rt].sum, p[rt].set, cnt);  
}  
  
int main() {  
   // freopen("in.txt", "r", stdin);  
    int t, n, val;  
    scanf("%d", &t);  
    while(t --){  
        scanf("%d", &n);  
        build(1, 1, n);  
        flag = 0;  
        for(int i = 0; i < n; ++ i){  
            scanf("%d", &val);  
     //       printf("val = %d ", val);  
            cnt = 0;  
            update(1, 1, n, val + 1);  
        //    puts("");  
        }  
        puts("");  
    }  
    return 0;  
}