學 Fhq 就是為了盡量不去寫某毒瘤數(shù)據(jù)結(jié)構(gòu),所以自然要來杠一杠某數(shù)據(jù)結(jié)構(gòu)的經(jīng)典操作:區(qū)間反轉(zhuǎn)

聽起來玄乎,但只需要一個小 trick 就行了:把原來的區(qū)間以下標作為權(quán)值建成 Treap , 這樣整棵 Treap 的中序遍歷就是原區(qū)間.

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

一個基本的思路是將區(qū)間 Split 為 [1,l-1],[l,r],[r+1,n] 三部分,對中間的 [l,r] 進行反轉(zhuǎn)

反轉(zhuǎn)的具體操作是從根到葉子把每個節(jié)點的左右兒子互換

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

所以,我們必須考慮去減少我們的操作次數(shù).

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

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

(這里有個小細節(jié),最后輸出前,別忘了把所有的 tag 全部下傳到底)

那么什么時候去下傳 tag 呢 ? 聰明的你肯定也已經(jīng)想到了,對,就是在 merge 和 Split 兩個函數(shù)中,優(yōu)先下傳 tag

建樹的時候,其實應(yīng)該是以使用笛卡爾樹的方式建樹為佳,但我太懶了,就直接 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 ;
}

轉(zhuǎn)載于:https://www.cnblogs.com/Equinox-Flower/p/10785292.html

總結(jié)

以上是生活随笔為你收集整理的FhqTreap的区间翻转的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。