@[mikechu](/space/show?uid=121260) 楼叉楼的平衡树要吗
```cpp
#include <iostream>
#include <stdio.h>
#define MAXN 100010
#define update( cur ) if ( cur -> left ->size ) cur -> size = cur -> left ->size + cur -> right -> size , cur -> value = cur -> right -> value
#define new_Node( s , v , a , b ) ( & ( * st[ cnt++ ] = Node( s , v , a ,b ) ) )
#define merge( a , b ) new_Node( a -> size + b -> size , b -> value , a , b )
#define ratio 4
using namespace std;
int n , cnt , s , a;
struct Node
{
int size , value;
Node * left , * right;
Node( int s , int v , Node * a , Node * b ) : size( s ) , value( v ) , left( a ) ,right( b ) {}
Node() {}
} * root , * father , * st[ MAXN << 1] , t[ MAXN << 1 ] , * null;
inline void maintain( Node * cur )
{
if( cur -> left -> size > cur -> right -> size * ratio) cur -> right = merge( cur -> left -> right , cur -> right ) , st[ --cnt ] = cur -> left , cur -> left = cur -> left ->left;
if( cur -> right -> size > cur -> left -> size * ratio) cur -> left = merge( cur -> left , cur -> right -> left ) , st[ --cnt ] = cur -> right , cur -> right = cur -> right -> right;
}
int find( int x , Node * cur)
{
if ( cur -> size == 1 ) return cur -> value;
return x > cur -> left -> size ? find( x - cur -> left -> size , cur -> right ) : find( x , cur -> left );
}
int rank( int x , Node * cur )
{
if (cur -> size == 1 ) return 1;
return x > cur -> left -> value ? rank( x , cur -> right ) + cur -> left -> size : rank( x , cur -> left );
}
void insert( int x , Node * cur )
{
if ( cur -> size == 1 ) cur -> left = new_Node( 1 , min( cur -> value , x ) , null , null ) , cur -> right = new_Node( 1 , max( cur -> value , x ) , null , null );
else insert( x , x > cur -> left -> value ? cur -> right : cur -> left );
update( cur ) , maintain( cur );
}
void erase( int x , Node * cur )
{
if ( cur -> size == 1 ) * father = cur == father -> left ? * father -> right : * father -> left;
else father = cur , erase( x , x > cur -> left -> value ? cur -> right : cur -> left );
update( cur ) , maintain( cur );
}
int main()
{
cin >> n;
for( register int i = 0 ; i < MAXN << 1 ; i++ ) st[i] = & t[i];
null = new_Node( 0 , 0 , 0 , 0 );
root = new_Node( 1 , 2147483647 , null , null );
while( n-- )
{
cin >> s >> a;
if( s == 1 ) insert( a , root );
else if( s == 2 ) erase( a , root );
else if( s == 3 ) cout << rank( a , root ) << endl;
else if( s == 4 ) cout << find( a , root ) << endl;
else if( s == 5 ) cout << find( rank( a , root ) - 1 , root ) << endl;
else cout << find( rank( a + 1 , root ) , root ) << endl;
}
return 0;
}
```
by 引领天下 @ 2019-03-03 17:41:43
e...我看不懂指针
我都定义的结构体
另外，我只是想知道怎么错了
by mikechu @ 2019-03-03 21:20:53