Splay
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int MAXN = 2e5 + 3;
int ch[MAXN][2] , val[MAXN] , cnt[MAXN] , siz[MAXN] , fa[MAXN];
int root , ncnt;
int chk( int x ){
return ch[fa[x]][1] == x;
}
void pushup( int x ){
siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + cnt[x];
}
void rorate( int x ){
int f = fa[x] , ff = fa[f] , w = chk( x );
ch[f][w] = ch[x][w^1];
fa[ch[x][w^1]] = f;
ch[ff][chk(f)] = x;
fa[x] = ff;
ch[x][w^1] = f;
fa[f] = x;
pushup( f );pushup( x );
}
void splay( int x , int goal ){
while( fa[x] != goal ){
int f = fa[x] , ff = fa[f];
if( ff != goal ){
if( chk( x) == chk(f ) ) rorate( f );
else
rorate( x );
}
rorate( x );
}
if( !goal ) root = x;
}
void find_( int x ){
if( !root ) return ;
int cur = root;
while( ch[cur][val[cur] < x] && val[cur] != x ){
cur = ch[cur][val[cur] < x];
}
splay( cur , 0 );
}
void insert_( int x ){
int cur = root , p = 0;
while( cur && val[cur] != x ){
p = cur;
cur = ch[cur][val[cur] < x];
}
if( cur ){
cnt[cur] ++;
}
else{
cur = ++ncnt;
if( p ) ch[p][x>val[p]] = cur;
ch[cur][0] = ch[cur][1] = 0;
val[cur] = x;cnt[cur] = 1;
siz[cur] = 1;fa[cur] = p;
}
splay( cur , 0 );
}
int kth( int k ){
int cur = root;
while( true ){
if( siz[ch[cur][0]] >= k && ch[cur][0] ){
cur = ch[cur][0];
}
else if( siz[ch[cur][0]] + cnt[cur] < k ){
k -= siz[ch[cur][0]] + cnt[cur];
cur = ch[cur][1];
}
else
return cur;
}
}
int pre( int x ){
find_( x );
if( val[root] < x ) return root;
int cur = ch[root][0];
while( ch[cur][1] ){
cur = ch[cur][1];
}
return cur;
}
int succ( int x ){
find_( x );
if( val[root] > x ) return root;
int cur = ch[root][1];
while( ch[cur][0] ){
cur = ch[cur][0];
}
return cur;
}
void delete_( int x ){
int pree = pre( x ) ,suc = succ( x );
splay( pree , 0 );
splay( suc , pree );
int cur = ch[suc][0];
if( cnt[cur] > 1 ){
cnt[cur] --;
splay( cur , 0 );
}
else
ch[suc][0] = 0;
}
int n;
int main()
{
scanf( "%d" , &n );
insert_(0x3f3f3f3f);
insert_(0xcfcfcfcf);
while( n -- ){
int opt , x;
scanf( "%d%d" , &opt , &x );
if( opt == 1 )
insert_( x );
else if( opt == 2 )
delete_( x );
else if( opt == 3 ){
find_( x );
printf( "%d\n" , siz[ch[root][0]] );
}
else if( opt == 4 ){
printf( "%d\n" , val[kth( x + 1 )] );
}
else if( opt == 5 )
printf( "%d\n" , val[pre(x)] );
else if( opt == 6 )
printf( "%d\n" , val[succ(x)] ) ;
}
return 0;
}
Treap
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cstdlib>
using namespace std;
const int MAXN = 1e5 + 3;
int n , siz[MAXN] , v[MAXN] , rd[MAXN] , num[MAXN];
int son[MAXN][2] , ncnt , root = 0;
void pushup( int x ){
siz[x] = siz[son[x][0]] + siz[son[x][1]] + num[x];
}
void rorate( int &x , int d ){
int k = son[x][d^1];
son[x][d^1] = son[k][d];
son[k][d]= x;
pushup( x );
pushup( k );
x = k;
}
void insert_( int &p , int x ){
if( !p ){
p = ++ncnt;
siz[p] = num[p] = 1;
son[p][0] = son[p][1] = 0;
v[p] = x;
rd[p] = rand();
return ;
}
if( v[p] == x ){
siz[p] ++;
num[p] ++;
return ;
}
int d = v[p] < x;
insert_( son[p][d] , x );
if( rd[p] < rd[son[p][d]] ) rorate( p , d ^ 1 );
pushup( p );
}
void del( int &p , int x ){
if( !p ) return ;
if( v[p] > x )
del( son[p][0] , x );
else if( v[p] < x )
del( son[p][1] , x );
else{
if( son[p][0] && !son[p][1] ){
rorate( p , 1 );
del( son[p][1] , x );
}
else if( son[p][1] && !son[p][0] ){
rorate( p , 0 );
del( son[p][0] , x );
}
else if( son[p][0] && son[p][1] ){
if( rd[son[p][0]] > rd[son[p][1]] ){
rorate( p , 1 );
del( son[p][1] , x);
}
else{
rorate( p , 0 );
del( son[p][0] , x );
}
}
else{
num[p] -- ;siz[p] --;
if( !num[p] ) p = 0;
}
}
pushup( p );
}
int rank_( int p , int x ){
if( !p )return 0;
if( v[p] == x )
return siz[son[p][0]] + 1;
if( v[p] > x )
return rank_( son[p][0] , x );
else
return siz[son[p][0]] + num[p] + rank_( son[p][1] , x );
}
int find_( int p , int x ){
if( !p ) return 0;
if( siz[son[p][0]] >= x ) return find_( son[p][0] , x );
if( siz[son[p][0]] + num[p] >= x )
return v[p];
return find_( son[p][1] , x - siz[son[p][0]] - num[p] );
}
int pree( int p , int x ){
if( !p ) return -0x3f3f3f3f;
if( v[p] >= x )
return pree( son[p][0] , x );
return max( v[p] , pree( son[p][1] , x ) );
}
int succ( int p , int x ){
if( !p ) return 0x3f3f3f3f;
if( v[p] <= x )
return succ( son[p][1] , x );
return min( v[p] , succ( son[p][0] , x ) );
}
int main()
{
scanf( "%d" , &n );
while( n -- ){
int x , y;
scanf( "%d%d" , &x , &y );
if( x == 1 )
insert_( root , y );
else if( x == 2 )
del( root , y );
else if( x ==3 )
printf( "%d\n" , rank_( root , y ) );
else if( x == 4 )
printf( "%d\n" , find_( root , y ) );
else if( x == 5 )
printf( "%d\n" , pree( root , y ) );
else
printf( "%d\n" , succ( root , y ) );
}
return 0;
}
BIT_jzx
发布了68 篇原创文章 · 获赞 7 · 访问量 3821
私信
关注