UVa 1402 런타임 오류 트리

  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 }