Runtime Error 到现在连样例也跑不出来！！！
调试了一晚上快要死了……
知道错在哪里但是不会改，代码先扔在这里吧。看来不能太依赖模板啊orz……
1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 6 using namespace std; 7 8 struct Node 9 { 10 Node *ch[2]; 11 int v; //节点编号 12 int s; //节点域 13 int flip; 14 Node( int v ):v(v) 15 { 16 ch[0] = ch[1] = NULL; 17 s = 1; 18 flip = 0; 19 } 20 int cmp( int x ) const 21 { 22 int t = ( ch[0] == NULL ) ? 0 : ch[0]->s; 23 if ( t >= x ) return 0; 24 if ( t + 1 == x ) return -1; 25 return 1; 26 } 27 void maintain() 28 { 29 s = 1; 30 if ( ch[0] != NULL ) s += ch[0]->s; 31 if ( ch[1] != NULL ) s += ch[1]->s; 32 return; 33 } 34 void pushDown() 35 { 36 if ( flip ) 37 { 38 flip = 0; 39 swap( ch[0], ch[1] ); 40 if ( ch[0] != NULL ) ch[0]->flip = !ch[0]->flip; 41 if ( ch[1] != NULL ) ch[1]->flip = !ch[1]->flip; 42 } 43 } 44 }; 45 46 struct number 47 { 48 int val; 49 int i; 50 }; 51 52 const int MAXN = 100010; 53 54 int n; 55 number num[MAXN]; 56 int SA[MAXN]; 57 58 void Rotate( Node* &o, int d ) //d=0 左旋 d=1 右旋 59 { 60 Node *k = o->ch[ d ^ 1 ]; 61 o->ch[ d ^ 1 ] = k->ch[d]; 62 k->ch[d] = o; 63 o = k; 64 o->ch[d]->maintain(); 65 o->maintain(); 66 return; 67 } 68 69 void splay( Node* &o, int k ) 70 { 71 o->pushDown(); 72 int d = o->cmp(k); 73 if ( d == 1 ) 74 { 75 if ( o->ch[0] != NULL ) 76 k -= o->ch[0]->s; 77 --k; 78 } 79 if ( d != -1 ) 80 { 81 Node *p = o->ch[d]; 82 p->pushDown(); 83 int d2 = p->cmp(k); 84 int k2 = k; 85 if ( d2 == 1 ) 86 { 87 if ( p->ch[0] != NULL ) 88 k2 -= p->ch[0]->s; 89 --k2; 90 } 91 if ( d2 != -1 ) 92 { 93 splay( p->ch[d2], k2 ); 94 if ( d == d2 ) Rotate( o, d ^ 1 ); 95 else Rotate( o->ch[d], d ); 96 } 97 Rotate( o, d ^ 1 ); 98 } 99 return; 100 } 101 102 void build( Node* &o, int l, int r ) 103 { 104 int m = ( l + r ) >> 1; 105 106 o = new Node( m ); 107 if ( l < m ) build( o->ch[0], l, m - 1 ); 108 if ( r > m ) build( o->ch[1], m + 1, r ); 109 o->maintain(); 110 111 return; 112 } 113 114 void DFS( Node *cur ) 115 { 116 cur->pushDown(); 117 if ( cur->ch[0] ) DFS( cur->ch[0] ); 118 //if ( cur->v && cur->v != n + 1 ) 119 printf( "num=%d id=%d ", SA[cur->v], cur->v ); 120 if ( cur->ch[1] ) DFS( cur->ch[1] ); 121 return; 122 } 123 124 bool cmp( number a, number b ) 125 { 126 if ( a.val == b.val ) return a.i < b.i; 127 return a.val < b.val; 128 } 129 130 int Search( Node *o, int x ) 131 { 132 int res = 0; 133 while ( o != NULL ) 134 { 135 o->pushDown(); 136 int d; 137 if ( x == o->v ) d = -1; 138 else if ( x < o->v ) d = 0; 139 else d = 1; 140 141 printf("search=%d ", o->v ); 142 143 if ( d == -1 ) 144 { 145 if ( o->ch[0] != NULL ) 146 res += o->ch[0]->s; 147 ++res; 148 return res; 149 } 150 else 151 { 152 if ( o->v == 5 && x == 2 ) 153 { 154 printf("%d ", o->ch[1]->v ); 155 puts("@@@"); 156 } 157 if ( d == 1 ) 158 { 159 if ( o->ch[0] != NULL ) 160 res += o->ch[0]->s; 161 ++res; 162 } 163 o = o->ch[d]; 164 } 165 } 166 return -1; 167 } 168 169 Node *root; 170 171 Node *Merge( Node *left, Node *right ) 172 { 173 splay( left, left->s ); 174 left->ch[1] = right; 175 left->maintain(); 176 return left; 177 } 178 179 void RemoveRoot() 180 { 181 Node *tmp = root; 182 root = Merge( root->ch[0], root->ch[1] ); 183 delete tmp; 184 return; 185 } 186 187 int main() 188 { 189 while ( scanf( "%d", &n ), n ) 190 { 191 for ( int i = 1; i <= n; ++i ) 192 { 193 scanf("%d", &num[i].val ); 194 num[i].i = i; 195 } 196 197 root = NULL; 198 build( root, 1, n ); 199 sort( num + 1, num + n + 1, cmp ); 200 201 for ( int i = 1; i <= n; ++i ) SA[ num[i].i ] = num[i].val; 202 //DFS( root ); 203 for ( int i = 1; i <= n; ++i ) 204 { 205 int id = Search( root, num[i].i ); 206 printf( "num = %d %d %d ", num[i].val, num[i].i, id ); 207 splay( root, id ); 208 DFS(root); 209 if ( i ) putchar(' '); 210 211 int tmp; 212 if ( root->ch[0] ) tmp = i + root->ch[0]->s; 213 else tmp = i; 214 printf( "%d ", tmp ); 215 216 root->ch[0]->flip ^= 1; 217 218 RemoveRoot(); 219 } 220 puts(""); 221 } 222 return 0; 223 }