/** * @author SCaffrey (srius.caffrey@gmail.com) * @date 2015-12-05 19:11:31 * @copyright MIT */ #include // NOLINT #include // NOLINT #include // NOLINT #include // NOLINT #include // NOLINT #include // NOLINT #define x1 x11 #define y1 y11 #define f(x, y, z) for (int x = (y), __ = (z); x < __; ++x) #define g(x, y, z) for (int x = (y), __ = (z); x <= __; ++x) #define fd(x, y, z) for (int x = (y), __ = (z); x > __; --x) #define gd(x, y, z) for (int x = (y), __ = (z); x >= __; --x) #ifdef WIN32 #define LLD "%I64d" #define LLU "%I64u" #else #define LLD "%lld" #define LLU "%llu" #endif typedef long long LL;// NOLINT typedef long double real; const double INF = 1e100; const int oo = ~0u >> 2; const double pi = acos(-1.0); const double EPS = 1e-8; const int MAXN = 100033; int T, n; int a[MAXN]; int s[MAXN]; std::set S; struct node{ int l, r, md; int has; node *ls, *rs; inline node(int ll = 0, int rr = 0):l(ll), r(rr), md(ll + (rr - ll >> 1)) { if (ll == rr) { has = 0; ls = rs = NULL; return; } ls = new node(ll, md); rs = new node(md + 1, rr); has = 0; } inline void upd(int x) { if (l == r) { has = 1; return; } ++has; if (x <= md) ls->upd(x); else rs->upd(x); } inline int get(int ll, int rr) { if (ll == l && rr == r) return has; if (ll > md) return rs->get(ll, rr); if (rr <= md) return ls->get(ll, rr); return ls->get(ll, md) + rs->get(md + 1, rr); } inline void del() { if (ls) ls->del(); if (rs) rs->del(); delete this; } }; std::vector ans; struct Treap { int size; int key,fix; Treap *ch[2]; Treap(int key) { size=1; fix=rand(); this->key=key; ch[0]=ch[1]=NULL; } int compare(int x) const { if(x==key) return -1; return xsize; if(ch[1]!=NULL) size+=ch[1]->size; } }; void Rotate(Treap* &t,int d) { Treap *k=t->ch[d^1]; t->ch[d^1]=k->ch[d]; k->ch[d]=t; t->Maintain(); //必须先维护t,再维护k,因为此时t是k的子节点 k->Maintain(); t=k; } void Insert(Treap* &t,int x) { if(t==NULL) t=new Treap(x); else { //int d=t->compare(x); //如果值相等的元素只插入一个 int d=x < t->key ? 0:1; //如果值相等的元素都插入 Insert(t->ch[d],x); if(t->ch[d]->fix > t->fix) Rotate(t,d^1); } t->Maintain(); } //一般来说,在调用删除函数之前要先用Find()函数判断该元素是否存在 void Delete(Treap* &t,int x) { int d=t->compare(x); if(d==-1) { Treap *tmp=t; if(t->ch[0]==NULL) { t=t->ch[1]; delete tmp; tmp=NULL; } else if(t->ch[1]==NULL) { t=t->ch[0]; delete tmp; tmp=NULL; } else { int k=t->ch[0]->fix > t->ch[1]->fix ? 1:0; Rotate(t,k); Delete(t->ch[k],x); } } else Delete(t->ch[d],x); if(t!=NULL) t->Maintain(); } bool Find(Treap *t,int x) { while(t!=NULL) { int d=t->compare(x); if(d==-1) return true; t=t->ch[d]; } return false; } int Kth(Treap *t,int k) { if(t==NULL||k<=0||k>t->size) return -1; if(t->ch[0]==NULL&&k==1) return t->key; if(t->ch[0]==NULL) return Kth(t->ch[1],k-1); if(t->ch[0]->size>=k) return Kth(t->ch[0],k); if(t->ch[0]->size+1==k) return t->key; return Kth(t->ch[1],k-1-t->ch[0]->size); } int Rank(Treap *t,int x) { int r; if(t->ch[0]==NULL) r=0; else r=t->ch[0]->size; if(x==t->key) return r+1; if(xkey) return Rank(t->ch[0],x); return r+1+Rank(t->ch[1],x); } void DeleteTreap(Treap* &t) { if(t==NULL) return; if(t->ch[0]!=NULL) DeleteTreap(t->ch[0]); if(t->ch[1]!=NULL) DeleteTreap(t->ch[1]); delete t; t=NULL; } void Print(Treap *t) { if(t==NULL) return; Print(t->ch[0]); // cout<key<ch[1]); } int main() { #ifdef LOCAL freopen("a.in", "r", stdin); freopen("a.out", "w", stdout); #endif scanf("%d", &T); while (T--) { S.clear(); ans.clear(); scanf("%d", &n); int sz = n; // g(i, 1, n) S.insert(i); Treap *root=NULL; g(i, 1, n) Insert(root, i); // root = new node(1, n); g(i, 1, n) scanf("%d", s + i); gd(i, n, 2) s[i] -= s[i - 1]; gd(i, n, 2) { int cur = Kth(root, sz - s[i]); Delete(root, cur); ans.push_back(cur); --sz; /*int cur = s[i], ti = 0, num = 0; // int num = *S.lower_bound(cur); for (std::set::iterator it = S.begin(); it != S.end(); ++it) { if (++ti == sz - cur) { // printf("`%d %d %d %d`\n", ti, sz, cur, *it); --sz; num = *it; S.erase(it); break; } } ans.push_back(num); */ // printf("%d ", num); } ans.push_back(root->key); // ans.push_back(*S.begin()); gd(i, int(ans.size()) - 1, 0) { printf("%d", ans[i]); if (i) putchar(' '); } puts(""); // printf("%d\n", *S.begin()); // root->del(); } #ifdef LOCAL fclose(stdin); fclose(stdout); #endif return 0; }