FhqTreap的區間翻轉

學 Fhq 就是為了盡量不去寫某毒瘤資料結構,是以自然要來杠一杠某資料結構的經典操作:區間反轉

聽起來玄乎,但隻需要一個小 trick 就行了:把原來的區間以下标作為權值建成 Treap , 這樣整棵 Treap 的中序周遊就是原區間.

按照這種方法建樹,是進行區間操作的第一步.接下來我們考慮如何去在 \Theta ( \log_2^{n}) 的時間内完成這件事.

一個基本的思路是将區間 Split 為 [1,l-1],[l,r],[r+1,n] 三部分,對中間的 [l,r] 進行反轉

反轉的具體操作是從根到葉子把每個節點的左右兒子互換

顯然,這樣複雜度十分糟糕,甚至達到了暴力都比不上的 \Theta ( n \times \log_2^{n} )

是以,我們必須考慮去減少我們的操作次數.

這裡我們借鑒一下之前學習線段樹時的 trick : lazytag (我不信你都學平衡樹了還不會線段樹)

聰明的你應該已經想到了,對沒錯,就是通過打 lazytag 來減少我們的操作,想必原理也不用贅述

(這裡有個小細節,最後輸出前,别忘了把所有的 tag 全部下傳到底)

那麼什麼時候去下傳 tag 呢 ? 聰明的你肯定也已經想到了,對,就是在 merge 和 Split 兩個函數中,優先下傳 tag

建樹的時候,其實應該是以使用笛卡爾樹的方式建樹為佳,但我太懶了,就直接 insert 了

Code :

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#define siz(rt) ( rt == NULL ? 0 : rt->size )
#define Drt pair < Treap * , Treap * >

using std::pair ;

const int N = 1e5 + 5 ;

int n , m ;

struct Treap {
    Treap * son[2] ;
    int val , size , rank ;
    bool tag ;
    Treap (int val) : val ( val ) { size = 1 ; rank = rand () ; son[0] = son[1] = NULL ; tag = false ; }
    inline void maintain () {
        this->size = 1 ;
        if ( this->son[0] != NULL ) this->size += this->son[0]->size ;
        if ( this->son[1] != NULL ) this->size += this->son[1]->size ;
        return ;
    }
} * root = NULL ;

inline void pushdown ( Treap * rt ) {
    std::swap ( rt->son[0] , rt->son[1] ) ;
    if ( rt->son[0] != NULL ) rt->son[0]->tag ^= rt->tag ;
    if ( rt->son[1] != NULL ) rt->son[1]->tag ^= rt->tag ;
    rt->tag = false ; return ;
}

inline Drt Split ( Treap * rt , int k ) {
    if ( rt == NULL ) return Drt ( NULL , NULL ) ;
    if ( rt->tag ) pushdown ( rt ) ; Drt t ;
    if ( k <= siz ( rt->son[0] ) ) {
        t = Split ( rt->son[0] , k ) ; rt->son[0] = t.second ;
        rt->maintain () ; t.second = rt ;
    } else {
        t = Split ( rt->son[1] , k - siz ( rt->son[0] ) - 1 ) ;
        rt->son[1] = t.first ; rt->maintain () ; t.first = rt ;
    }
    return t ;
}

inline Treap * merge ( Treap * x , Treap * y ) {
    if ( x == NULL ) return y ; if ( y == NULL ) return x ;
    if ( x->rank < y->rank ) {
        if ( x->tag ) pushdown ( x ) ;
        x->son[1] = merge ( x->son[1] , y ) ;
        x->maintain () ; return x ;
    } else {
        if ( y->tag ) pushdown ( y ) ;
        y->son[0] = merge ( x , y->son[0] ) ;
        y->maintain () ; return y ;
    }
}

inline int Getrank ( Treap * rt , int key ) {
    if ( rt == NULL ) return 0 ;
    if ( key <= rt->val ) return Getrank ( rt->son[0] , key ) ;
    else return Getrank ( rt->son[1] , key ) + siz ( rt->son[0] ) + 1 ;
}

inline int Getkth ( Treap * & rt , int key ) {
    Drt x = Split ( rt , key - 1 ) ;
    Drt y = Split ( x.second , 1 ) ;
    Treap * node = y.first ;
    rt = merge ( x.first , merge ( node , y.second ) ) ;
    return node == NULL ? 0 : node->val ;
}

inline void insert ( Treap * & rt , int key ) {
    int k = Getrank ( rt , key ) ; Drt t = Split ( rt , k ) ;
    Treap * node = new Treap ( key ) ;
    rt = merge ( t.first , merge ( node , t.second ) ) ;
    return ;
}

inline void remove ( Treap * & rt , int key ) {
    int k = Getrank ( rt , key ) ; Drt x = Split ( rt , k - 1 ) ;
    Drt y = Split ( x.second , 1 ) ; delete y.first ;
    rt = merge ( x.first , y.second ) ; return ;
}

inline void reverse ( Treap * & rt , int l , int r ) {
    Drt x = Split ( rt , l - 1 ) ;
    Drt y = Split ( x.second , r - l + 1 ) ;
    y.first->tag = true ;
    rt = merge ( x.first , merge ( y.first , y.second ) ) ;
    return ;
}

inline void print ( Treap * rt ) {
    if ( rt == NULL ) return ;
    if ( rt->tag ) pushdown ( rt ) ;
    print ( rt->son[0] ) ;
    printf ("%d " , rt->val ) ;
    print ( rt->son[1] ) ;
}

int main () {
    srand ( time ( NULL ) ) ;
    scanf ("%d%d" , & n , & m ) ;
    for (int i = 1 ; i <= n ; ++ i) insert ( root , i ) ;
    while ( m -- ) {
        register int l , r ;
        scanf ("%d%d" , & l , & r ) ;
        reverse ( root , l , r ) ;
    }
    print ( root ) ; system ("pause") ; return 0 ;
}                

轉載于:https://www.cnblogs.com/Equinox-Flower/p/10785292.html