BZOJ-3217: ALOEXT（treap套trie）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3217

这题一看就是treap或替罪羊树套trie，然后我就很愉快的码了300+treap代码，然后光荣TLE，然后继续常数优化，愉快的刷了一版的ＴＬＥ后找@lz1 大神要了份神代码对着改了半天,最后发现指针版的居然要比数组模拟快上一半左右(再也不相信数组了...QaQ),然后这才总算A掉了...（然后就居然rank2了额。。。）

cf1b9d16fdfaaf51e54ccc478e5494eef11f7a9e.jpg.png
77094b36acaf2edd5e5e04118f1001e93801939f.jpg.png
738b4710b912c8fc8c30bb35fe039245d7882102.jpg.png

吃饱了没事做，顺便附上一个自己YY的treap套树的复杂度证明吧：

由于treap是平衡的，所以O( h ) = O( log n ) ,这里为了方便，暂且将treap当成一棵满二叉树处理：

对于每次删除，期望旋转O（1）的证明：

如果删除的节点在第i层（从1标号到h），那么其旋转次数为（h-i），删除的节点在第i层的概率为( 2^( i - 1 ) ) / ( 2^h - 1 )，近似认为成( 2 ^( i - 1 ) ) / ( 2^h ) = 1 / ( 2^( h - i + 1 ) )，那么期望的旋转次数为：

503d269759ee3d6de29dc93341166d224e4adeeb.jpg.png

即期望旋转次数不大于2次。

对于每次旋转，假如时间代价为所旋转节点的子树大小，那么其总期望代价为：

203fb80e7bec54e7348f53e6bb389b504ec26ae2.jpg.png

因此treap套树的复杂度是期望log n的。

代码：

#include <cstdio>

#include <cstring>

#include <cstdlib>

 

const int maxn = 110000 ;

 

inline void swap( int &x , int &y ) {

    int z = x ; x = y ; y = z ;

}

 

inline int max( int x , int y ) {

    return x > y ? x : y ;

}

 

#define L( t ) t -> left

#define R( t ) t -> right

#define S( t ) t -> size

#define maxv 31000000

 

int p0[ 20 ] ;

 

struct node {

    node *left , *right ;

    int size ;

} trie[ maxv ] ;

 

typedef node* pt ;

 

pt nll = trie , sta[ maxv ] , vt = trie ;

int cnt = 0 ;

 

void Init_trie(  ) {

    L( nll ) = R( nll ) = nll , S( nll ) = 0 ;

}

 

pt getn(  ) {

    pt x = cnt ? sta[ cnt -- ] : ++ vt ;

    L( x ) = R( x ) = nll , S( x ) = 0 ;

    return x ;

}

 

void recycle( pt t ) {

    sta[ ++ cnt ] = t ;

    if ( L( t ) != nll ) recycle( L( t ) ) ;

    if ( R( t ) != nll ) recycle( R( t ) ) ;

}

 

inline void ins( int val , pt t ) {

    for ( int i = 19 ; i >= 0 ; -- i ) if ( val & p0[ i ] ) {

        if ( R( t ) == nll ) R( t ) = getn(  ) ;

        ++ S( ( t = R( t ) ) ) ;

    } else {

        if ( L( t ) == nll ) L( t ) = getn(  ) ;

        ++ S( ( t = L( t ) ) ) ;

    }

}

 

inline void del( int val , pt t ) {

    for ( int i = 19 ; i >= 0 ; -- i ) if ( val & p0[ i ] ) {

        if ( ! ( -- S( R( t ) ) ) ) {

            recycle( R( t ) ) ;

            R( t ) = nll ;

            return ;

        } else t = R( t ) ;

    } else {

        if ( ! ( -- S( L( t ) ) ) ) {

            recycle( L( t ) ) ;

            L( t ) = nll ;

            return ;

        } else t = L( t ) ;

    }

}

 

inline int query( int val , pt t ) {

    int rec = 0 ;

    for ( int i = 19 ; i >= 0 ; -- i ) {

        rec <<= 1 ;

        if ( val & p0[ i ] ) {

            if ( S( L( t ) ) ) rec ^= 1 , t = L( t ) ; else t = R( t ) ;

        } else {

            if ( S( R( t ) ) ) rec ^= 1 , t = R( t ) ; else t = L( t ) ;

        }

    }

    return rec ;

}

 

void merge( pt l , pt r , pt &t ) {

    t = getn(  ) ;

    S( t ) = S( l ) + S( r ) ;

    if ( S( L( l ) ) || S( L( r ) ) ) merge( L( l ) , L( r ) , L( t ) ) ;

    if ( S( R( l ) ) || S( R( r ) ) ) merge( R( l ) , R( r ) , R( t ) ) ;

}

 

#undef maxv

 

#define maintain recycle( T( k ) ) ; T( k ) = T( t ) , S( k ) = S( t ) , FM( k ) = FM( t ) , SM( k ) = SM( t ) ; t -> update(  ) ; t = k

#define maxv 301000

#define P( t ) t -> priority

#define FM( t ) t -> first_max

#define SM( t ) t -> second_max

#define W( t ) t -> weight

#define T( t ) t -> root

 

const int inf = 0x7fffffff ;

 

void upd0( int &x , int &y , int z ) {

    if ( z > x ) {

        y = x ; x = z ;

    } else if ( z > y ) y = z ;

}

 

void upd1( int &x , int &y , int a , int b ) {

    if ( a > x ) {

        y = x > b ? x : b ;

        x = a ;

    } else if ( a > y ) y = a ;

}

 

struct Node {

    Node *left , *right ;

    int size , priority , weight , first_max , second_max ;

    node *root ;

    void update(  ) {

        size = left -> size + right -> size + 1 ;

        first_max = left -> first_max , second_max = left -> second_max ;

        upd1( first_max , second_max , right -> first_max , right -> second_max ) ;

        upd0( first_max , second_max , weight ) ;

        merge( left -> root , right -> root , root ) ;

        ins( weight , root ) ;

    }

} treap[ maxv ] ;

 

typedef Node* Pt ;

 

Pt Root = treap , Nll = treap , Vt = treap ;

 

void Init_treap(  ) {

    L( Nll ) = R( Nll ) = Nll , S( Nll ) = 0 , T( Nll ) = nll , P( Nll ) = FM( Nll ) = SM( Nll ) = W( Nll ) = - inf , srand( 19 ) ;

}

 

void Left( Pt &t ) {

    Pt k = R( t ) ; R( t ) = L( k ) ; L( k ) = t ;

    maintain ;

}

 

void Right( Pt &t ) {

    Pt k = L( t ) ; L( t ) = R( k ) ; R( k ) = t ;

    maintain ;

}

 

void Insert( int pos , int val , Pt &t ) {

    if ( t == Nll ) {

        t = ++ Vt ;

        L( t ) = R( t ) = Nll , S( t ) = 1 , P( t ) = rand(  ) , W( t ) = FM( t ) = val , SM( t ) = - inf , ins( val , T( t ) = getn(  ) ) ;

        return ;

    }

    ++ S( t ) , ins( val , T( t ) ) , upd0( FM( t ) , SM( t ) , val ) ;

    if ( pos <= S( L( t ) ) ) {

        Insert( pos , val , L( t ) ) ;

        if ( P( L( t ) ) > P( t ) ) Right( t ) ;

    } else {

        Insert( pos - S( L( t ) ) - 1 , val , R( t ) ) ;

        if ( P( R( t ) ) > P( t ) ) Left( t ) ;

    }

}

 

int Delete( int pos , Pt &t ) {

    int s = S( L( t ) ) , w ;

    if ( s == pos ) {

        w = W( t ) ;

        if ( L( t ) == Nll ) {

            recycle( T( t ) ) ; t = R( t ) ; return w ;

        } else if ( R( t ) == Nll ) {

            recycle( T( t ) ) ; t = L( t ) ; return w ;

        } else if ( P( L( t ) ) > P( R( t ) ) ) {

            Right( t ) ; w = Delete( pos - S( L( t ) ) - 1 , R( t ) ) ;

        } else {

            Left( t ) ; w = Delete( pos , L( t ) ) ;

        }

    } else if ( pos < s ) w = Delete( pos , L( t ) ) ; else w = Delete( pos - s - 1 , R( t ) ) ;

    del( w , T( t ) ) , -- S( t ) ;

    FM( t ) = FM( L( t ) ) , SM( t ) = SM( L( t ) ) ;

    upd0( FM( t ) , SM( t ) , W( t ) ) , upd1( FM( t ) , SM( t ) , FM( R( t ) ) , SM( R( t ) ) ) ;

    return w ;

}

 

int Change( int pos , int val , Pt t ) {

    int s = S( L( t ) ) , w ;

    if ( s == pos ) {

        w = W( t ) ; W( t ) = val ;

    } else if ( pos < s ) w = Change( pos , val , L( t ) ) ; else w = Change( pos - s - 1 , val , R( t ) ) ;

    ins( val , T( t ) ) ; del( w , T( t ) ) ;

    FM( t ) = FM( L( t ) ) , SM( t ) = SM( L( t ) ) ;

    upd0( FM( t ) , SM( t ) , W( t ) ) , upd1( FM( t ) , SM( t ) , FM( R( t ) ) , SM( R( t ) ) ) ;

    return w ;

}

 

Pt NODE[ maxn ] ;

int w[ maxn ] , cntn , cntw ;

 

void Query( int l , int r , Pt t ) {

    if ( ! l && r == S( t ) - 1 ) {

        NODE[ ++ cntn ] = t ; return ;

    }

    int s = S( L( t ) ) ;

    if ( r < s ) Query( l , r , L( t ) ) ; else

        if ( l > s ) Query( l - s - 1 , r - s - 1 , R( t ) ) ; else {

            w[ ++ cntw ] = W( t ) ;

            Query( l , s - 1 , L( t ) ) , Query( 0 , r - s - 1 , R( t ) ) ;

        }

}

 

inline int Solve( int l , int r ) {

    cntn = cntw = 0 ;

    Query( l , r , Root ) ;

    int x = - inf , y = - inf , i , temp = 0 ;

    for ( i = 1 ; i <= cntw ; ++ i ) upd0( x , y , w[ i ] ) ;

    for ( i = 1 ; i <= cntn ; ++ i ) upd1( x , y , FM( NODE[ i ] ) , SM( NODE[ i ] ) ) ;

    for ( i = 1 ; i <= cntw ; ++ i ) temp = max( temp , y ^ w[ i ] ) ;

    for ( i = 1 ; i <= cntn ; ++ i ) temp = max( temp , query( y , T( NODE[ i ] ) ) ) ;

    return temp ;

}

 

int n , m , a[ maxn ] , ans = 0 ;

 

void build( int l , int r , Pt &t ) {

    t = ++ Vt ;

    int mid = ( l + r ) >> 1 ;

    W( t ) = a[ mid ] , S( t ) = 1 , P( t ) = rand(  ) ;

    if ( l < mid ) {

        build( l , mid - 1 , L( t ) ) ;

        if ( P( L( t ) ) > P( t ) ) swap( P( t ) , P( L( t ) ) ) ;

    } else L( t ) = Nll ;

    if ( r > mid ) {

        build( mid + 1 , r , R( t ) ) ;

        if ( P( R( t ) ) > P( t ) ) swap( P( t ) , P( R( t ) ) ) ;

    } else R( t ) = Nll ;

    t -> update(  ) ;

}

 

int ch ;

 

void getint( int &t ) {

    for ( ch = getchar(  ) ; ch < '0' || ch > '9' ; ch = getchar(  ) ) ;

    t = ch - '0' ;

    for ( ch = getchar(  ) ; ch >= '0' && ch <= '9' ; ch = getchar(  ) ) t = 10 * t + ch - '0' ;

}

 

int o[ 20 ] ;

   

inline void putint( int t ) {

    if ( ! t ) putchar( '0' ) ; else {

        o[ 0 ] = 0 ;

        for ( ; t ; t /= 10 ) o[ ++ o[ 0 ] ] = t % 10 ;

        while ( o[ 0 ] -- ) putchar( '0' + o[ o[ 0 ] + 1 ] ) ;

    }

    putchar( '\n' ) ;

}

 

int main(  ) {

    Init_trie(  ) , Init_treap(  ) ;

    p0[ 0 ] = 1 ;

    for ( int i = 1 ; i <= 19 ; ++ i ) p0[ i ] = p0[ i - 1 ] << 1 ;

    getint( n ) , getint( m ) ;

    for ( int i = 0 ; i ++ < n ; ) getint( a[ i ] ) ;

    build( 1 , n , Root ) ;

    int x , y  ;

    while ( m -- ) {

        for ( ch = getchar(  ) ; ch != 'I' && ch != 'D' && ch != 'C' && ch != 'F' ; ch = getchar(  ) ) ;

        if ( ch == 'I' ) {

            getint( x ) , getint( y ) ;

            x = ( x + ans ) % ( n ++ ) , y = ( y + ans ) % 1048576 ;

            Insert( x , y , Root ) ;

        } else if ( ch == 'D' ) {

            getint( x ) ;

            x = ( x + ans ) % ( n -- ) ;

            Delete( x , Root ) ;

        } else if ( ch == 'C' ) {

            getint( x ) , getint( y ) ;

            x = ( x + ans ) % n , y = ( y + ans ) % 1048576 ;

            Change( x , y , Root ) ;

        } else if ( ch == 'F' ) {

            getint( x ) , getint( y ) ;

            x = ( x + ans ) % n , y = ( y + ans ) % n ;

            if ( x > y ) swap( x , y ) ;

            printf( "%d\n" , ans = Solve( x , y ) ) ;

        }

    }

    return 0 ;

}
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,445评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,889评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,047评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,760评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,745评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,638评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,011评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,669评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,923评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,655评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,740评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,406评论 4赞 320
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,995评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,961评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,197评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,023评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,483评论 2赞 342

推荐阅读更多精彩内容

  • 关于B树的一些总结(一)
    B树的定义 一棵m阶的B树满足下列条件： 树中每个结点至多有m个孩子。 除根结点和叶子结点外，其它每个结点至少有m...
    文档随手记阅读 13,155评论 0赞 25
  • drbd指南
    feisky云计算、虚拟化与Linux技术笔记posts - 1014, comments - 298, trac...
    不排版阅读 3,813评论 0赞 5
  • 为什么要写作
    大卫·伊格曼在《生命的清单》里曾说：人的一生，要死去三次。第一次，当你的心跳停止，呼吸消逝，你在生物学上被宣告了死...
    戈德里克阅读 193评论 0赞 1
  • 2017-10-26
    潮起潮落，云卷云舒，待日暮西垂，只剩余晖中的点点星辰，或是天边那一轮残月
    天蓝的尘埃阅读 141评论 0赞 1
  • 每天每夜的点点滴滴
    和谐就是，哪怕放个屁，那个屁声都能作为笑点的梗，打趣的点～
    寓言兮阅读 148评论 0赞 0