Runtime Error 到现在连样例也跑不出来！！！
调试了一晚上快要死了……
知道错在哪里但是不会改，代码先扔在这里吧。看来不能太依赖模板啊orz……
1 #include2 #include 3 #include 4 #include 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\n", 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\n", 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 else151 {152 if ( o->v == 5 && x == 2 )153 {154 printf("%d\n", 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\n", 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\n\n", tmp );215 216 root->ch[0]->flip ^= 1;217 218 RemoveRoot();219 }220 puts("");221 }222 return 0;223 }