题目链接：点击打开链接
题意：
给出逆序数的值，求原序列（一个1-N的排列）
1, 2, 0, 1, 0 表示1的逆序数是1，2的逆序数是2，3的逆序数是0···
思路：
从最后一个数开始插，每次插到当前序列的第a[i]个数。。
splay模拟
== 这个方法比较直(wu)观(nao)，，别的方法并没有想出来。。
#include <cstdio>#include <iostream>#include <cstring>#include <queue>#include <algorithm>#include <map>#include <cmath>template <class T>inline bool rd(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1;}template <class T>inline void pt(T x) {if (x <0) {putchar('-');x = -x;}if(x>9) pt(x/10);putchar(x%10+'0');}using namespace std;inline int Mid(int a,int b){return (a+b)>>1;}#define N 100010#define L(x) tree[x].ch[0]#define R(x) tree[x].ch[1]#define Siz(x) tree[x].siz#define Father(x) tree[x].fa#define Max(x) tree[x].max#define Val(x) tree[x].val#define Pt(x) tree[x].pt()struct node{int ch[2], siz, fa;int max, val;void pt(){printf("val:%d max:%d siz:%d fa:%d child{%d,%d}\n", val,max,siz,fa,ch[0],ch[1]);}}tree[N*2];int tot, root;void Newnode(int &id, int val, int fa, int siz = 1){id = ++tot;L(id) = R(id) = 0;Father(id) = fa;Siz(id) = siz;Max(id) = Val(id) = val;}void push_up(int id){Siz(id) = Siz(L(id)) + Siz(R(id)) +1;Max(id) = max(Max(R(id)), Max(L(id)));Max(id) = max(Val(id), Max(id));}void push_down(int id){}void Rotate(int id, int kind){int y = Father(id);push_down(y); push_down(id); //heretree[y].ch[kind^1] = tree[id].ch[kind];Father(tree[id].ch[kind]) = y;if(Father(y))tree[Father(y)].ch[R(Father(y))==y] = id;Father(id) = Father(y);Father(y) = id;tree[id].ch[kind] = y;push_up(y);}void splay(int id, int goal){push_down(id);while(Father(id) != goal){int y = Father(id);if(Father(y) == goal)Rotate(id, L(y)==id);else{int kind = L(Father(y)) == y;if(tree[y].ch[kind] == id){Rotate(id, kind^1);Rotate(id, kind);}else{Rotate(y, kind);Rotate(id,kind);}}}push_up(id);if(goal == 0)root = id;}int Get_kth(int kth, int sor){//找到在sor后面的第k个数push_down(sor);int id = sor;while(Siz(L(id)) != kth){if(Siz(L(id)) > kth)id = L(id);else{kth -= (Siz(L(id))+1);id = R(id);}push_down(id);}return id;}void init(){Father(0) = L(0) = R(0) = Siz(0) = 0;Max(0) = 0;tot = 0;Newnode(root, 0, 0);Newnode(R(root), 0, root);push_up(root);}void debug(int x){printf("%d:\n", x);Pt(x);if(L(x)){printf("L:");debug(L(x));printf("return to %d:\n", x);}if(R(x)){printf("R:");debug(R(x));printf("return to %d:\n", x);}}void insert(int pos, int val){splay(1, 0);int u = Get_kth(pos, 1);//if(pos == 2){cout<<"=="; debug(root);}int v = Get_kth(pos+1, 1);//printf("在(%d,%d)之间:", u, v);Pt(u); Pt(v);puts("*****");splay(u, 0);splay(v, root);//if(pos == 2){cout<<"=="; debug(root);}Newnode(L(v), val, v);push_up(v);push_up(u);//printf("[%d,%d]\n", u, v);}int n;int a[100005];vector<int>G;void dfs(int u){if(L(u))dfs(L(u));G.push_back(Val(u));if(R(u))dfs(R(u));}int main() {while(cin>>n){init();//puts("init debug begin:");debug(root);for(int i = 1; i <= n; i++)rd(a[i]);bool ok = true;for(int i = n; i; i–){if(a[i]>n-i){ok = false; break;}insert(a[i] , i);//printf(" %d debug begin:", i);debug(root);}if(false == ok){ puts("No solution");continue; }G.clear();dfs(root);for(int i = 1; i < G.size() -1; i++)printf("%d%c", G[i], i+2==(int)G.size()?'\n':' ');}return 0;}/*170 1 1 1 0 4 1*/
经受雨，面对另一个轮回。
