【POJ】3580 SuperMemo 【splay】

傳送門：【POJ】3580 SuperMemo

題目分析：這道題又——調了一天。。。。真是傷啊。。。。

題目不難，都是splay的基本操作，但是由于我代碼能力太差各種寫搓。。。尤其今天是敗在了删除一個節點上，寫了資料生成器才發現remove函數徹底寫錯了。。。。T u T。。一天就這麼過去了。。。

這題沒給資料範圍，其實int就夠了，最大值别設太小就行，一般0x3f3f3f3f夠了。還有就是其中将一個區間循環的操作需要注意，不僅循環次數很大需要取模，而且還可能給你來負的！

大概講解一下6個操作的解決方法：

1.ADD 旋轉出區間[L,R]（即l-1為根結點，r+1為根結點的右節點，此時區間[L,R]，為根結點的右節點的子樹），然後對子樹的根打上标記。和線段樹一樣，lazy标記呗。

2.REVERSE 同樣旋轉出區間[L,R]，對[L,R]子樹的根的标記取反。

3.REVOLVE 其實就是得到一個取模後的T，然後将[L,R-T]插入到已經删除了這個區間的位置L-1+T的右端，即将L-1+T旋轉到根，再将L+T旋轉為根的右節點，然後将區間[L,R-T]變為根結點的右節點的左節點即可。

4.INSERT 建立一個節點，然後用類似操作3的方法插入。

5.DELETE 将要删除的數所在的位置pos作為一個區間[pos,pos]旋轉出來，然後像切樹一樣切掉就行了。

6.MIN 隻要在pushup以及pushdown維護一下子樹的最小值，然後用旋轉區間的方法旋轉出區間[L,R]，直接傳回這個區間子樹的根結點的資訊即可。

代碼如下：

/*
	本算法需要兩個虛拟節點：0、n+1
	算法基本函數功能：
	clear ()                                        初始化 
	newNode ( int v , SplayNode* f )                建立節點并指派v以及令其父親為f
	init ( int n , int num[] )                      初始化
	rotate ( SplayNode* o , int d )                 左右旋，d=0表示左旋，d=1表示右旋
	splay ( SplayNode* o , SplayNode* f )           伸展o直到o的父節點為f為止
	select ( int k , SplayNode* f )                 選擇第k個元素并将其旋轉到其父節點為f為止（不計虛拟節點）
	SplayNode* get ( int l , int r )                傳回區間[l,r]為子樹的根:即将l-1旋轉到根，将r+1旋轉為l-1的右節點
	void split ( int l , int r , SplayNode* &o )    将區間[l,r]剪切到o
	void merge ( int pos , SplayNode* o )           将o插入到pos後端：即将pos旋轉到根，pos+1旋轉為pos的右節點
	void cut ( int l , int r , int pos )            剪出區間[l,r]并插入到pos的後端
	void reverse ( int l , int r )                  翻轉區間[l,r]
	void revolve ( int l , int r , int T )          剪出區間[l,R-T]，然後在删除了該區間後的位置l-1+T後端插入該區間
	void getMin ( int l , int r )                   傳回區間[l,r]最小值
	void add ( int l , int r , int v )              對區間[l,r]内的所有數加上v
	void insert ( int pos , int v )                 在pos的後端插入值為v的新節點
	void remove ( int pos )                         删除位置為pos的節點
	void print ( SplayNode* o )                     輸出資訊
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 233333 ;
const int INF = 0x3f3f3f3f ;

struct SplayNode {
	SplayNode *c[2] , *f ;
	int s ;
	int v ;
	bool rev ;
	int addv ;
	int minv ;
	
	void add ( int val ) {
		v += val ;
		addv += val ;
		minv = min ( v , minv ) ;
	}
	
	void pushup () {
		s = c[0] -> s + c[1] -> s + 1 ;
		minv = min ( c[0] -> minv , c[1] -> minv ) ;
		minv = min ( minv , v ) ;
	}
	
	void pushdown () {
		if ( rev ) {
			swap ( c[0] , c[1] ) ;
			c[0] -> rev ^= 1 ;
			c[1] -> rev ^= 1 ;
			rev = 0 ;
		}
		if ( addv ) {
			if ( ~c[0] -> v ) {
				c[0] -> v += addv ;
				c[0] -> addv += addv ;
				c[0] -> minv += addv ;
			}
			if ( ~c[1] -> v ) {
				c[1] -> v += addv ;
				c[1] -> addv += addv ;
				c[1] -> minv += addv ;
			}
			addv = 0 ;
		}
	}
} Tnull , *null = &Tnull ;

struct Splay {
	SplayNode node[MAXN] , *cur ;
	SplayNode *root ;
	
	void clear () {
		null -> s = 0 ;
		null -> v = -1 ;
		null -> minv = INF ;
		cur = node ;
		root = null ;
	}
	
	SplayNode* newNode ( int v , SplayNode* f ) {
		cur -> v = v ;
		cur -> s = 1 ;
		cur -> rev = 0 ;
		cur -> addv = 0 ;
		cur -> minv = v ;
		cur -> c[0] = cur -> c[1] = null ;
		cur -> f = f ;
		return cur ++ ;
	}
	
	void rotate ( SplayNode* o , bool d ) {
		SplayNode* p = o -> f ;
		p -> pushdown () ;
		o -> pushdown () ;
		p -> c[!d] = o -> c[d] ;
		if ( o -> c[d] != null ) o -> c[d] -> f = p ;
		o -> f = p -> f ;
		if ( p -> f != null ) {
			if ( p == p -> f -> c[0] ) p -> f -> c[0] = o ;
			else p -> f -> c[1] = o ;
		}
		o -> c[d] = p ;
		p -> f = o ;
		p -> pushup () ;
		if ( root == p ) root = o ;
	}
	
	void splay ( SplayNode* o , SplayNode* f ) {
		while ( o -> f != f ) {
			SplayNode* p = o -> f ;
			if ( p -> f == f ) {
				if ( o == p -> c[0] ) rotate ( o , 1 ) ;
				else				  rotate ( o , 0 ) ;
			} else {
				if ( p == p -> f -> c[0] ) {
					if ( o == p -> c[0] ) rotate ( p , 1 ) , rotate ( o , 1 ) ;
					else				  rotate ( o , 0 ) , rotate ( o , 1 ) ;
				} else {
					if ( o == p -> c[1] ) rotate ( p , 0 ) , rotate ( o , 0 ) ;
					else				  rotate ( o , 1 ) , rotate ( o , 0 ) ;
				}
			}
		}
		o -> pushup () ;
	}
	
	void select ( int k , SplayNode* f ) {
		SplayNode* o = root ;
		++ k ;
		while ( o != null ) {
			o -> pushdown () ;
			int s = o -> c[0] -> s ;
			if ( k == s + 1 ) break ;
			if ( k <= s ) o = o -> c[0] ;
			else {
				k -= s + 1 ;
				o = o -> c[1] ;
			}
		}
		splay ( o , f ) ;
	}
	
	SplayNode* get ( int l , int r ) {
		select ( l - 1 , null ) ;
		select ( r + 1 , root ) ;
		return root -> c[1] -> c[0] ;
	}
	
	void split ( int l , int r , SplayNode* &o ) {
		o = get ( l , r ) ;
		o -> f = null ;
		root -> c[1] -> c[0] = null ;
		root -> c[1] -> pushup () ;
		root -> pushup () ;
	}
	
	void merge ( int pos , SplayNode* o ) {
		get ( pos + 1 , pos ) ;
		o -> f = root -> c[1] ;
		root -> c[1] -> c[0] = o ;
		root -> c[1] -> pushup () ;
		root -> pushup () ;
		splay ( o , null ) ;
	}
	
	void cut ( int l , int r , int pos ) {
		SplayNode* o ;
		split ( l , r , o ) ;
		merge ( pos , o ) ;
	}
	
	void reverse ( int l , int r ) {
		SplayNode* o = get ( l , r ) ;
		o -> rev ^= 1 ;
		splay ( o , null ) ;
	}
	
	void revolve ( int l , int r , int T ) {
		cut ( l , r - T , l - 1 + T ) ;
	}
	
	void add ( int l , int r , int v ) {
		SplayNode* o = get ( l , r ) ;
		o -> add ( v ) ;
		splay ( o , null ) ;
	}
	
	void insert ( int pos , int v ) {
		get ( pos + 1 , pos ) ;
		SplayNode* o = newNode ( v , root -> c[1] ) ;
		root -> c[1] -> c[0] = o ;
		root -> c[1] -> pushup () ;
		root -> pushup () ;
	}
	
	void remove ( int pos ) {
		get ( pos , pos ) ;
		root -> c[1] -> c[0] = null ;
		root -> c[1] -> pushup () ;
		root -> pushup () ;
	}
	
	int getMin ( int l , int r ) {
		SplayNode* o = get ( l , r ) ;
		return o -> minv ;
	}
	
	void init ( int n , int num[] ) {
		clear () ;
		FOR ( i , 0 , n + 1 ) {
			SplayNode* o = newNode ( num[i] , null ) ;
			o -> c[0] = root ;
			root -> f = o ;
			root = o ;
			root -> pushup () ;
		}
	}
	
	void print ( SplayNode* o ) {
		if ( o -> c[0] != null ) print ( o -> c[0] ) ;
		printf ( "左兒子v:%d----自己v:%d----右兒子v:%d\n" , o -> c[0] -> v , o -> v , o -> c[1] -> v ) ;
		if ( o -> c[1] != null ) print ( o -> c[1] ) ;
	}
} T ;

int n , p ;
int num[MAXN] ;
char s[10] ;
int x , y , v ;

void solve () {
	num[0] = num[n + 1] = INF ;
	FOR ( i , 1 , n ) scanf ( "%d" , &num[i] ) ;
	T.init ( n , num ) ;
	scanf ( "%d" , &p ) ;
	while ( p -- ) {
		scanf ( "%s" , s ) ;
		if ( s[0] == 'A' ) {
			scanf ( "%d%d%d" , &x , &y , &v ) ;
			T.add ( x , y , v ) ;
		} else if ( s[0] == 'R' && s[3] == 'E' ) {
			scanf ( "%d%d" , &x , &y ) ;
			T.reverse ( x , y ) ;
			
		} else if ( s[0] == 'R' && s[3] == 'O' ) {
			scanf ( "%d%d%d" , &x , &y , &v ) ;
			v %= y - x + 1 ;
			if ( v < 0 ) v += y - x + 1 ;
			T.revolve ( x , y , v ) ;
		} else if ( s[0] == 'I' ) {
			scanf ( "%d%d" , &x , &v ) ;
			T.insert ( x , v ) ;
		} else if ( s[0] == 'D' ) {
			scanf ( "%d" , &x ) ;
			T.remove ( x ) ;
		} else {
			scanf ( "%d%d" , &x , &y ) ;
			printf ( "%d\n" , T.getMin ( x , y ) ) ;
		}
	}
}

int main () {
	while ( ~scanf ( "%d" , &n ) ) solve () ;
	return 0 ;
}
           

為友善調試，另附小資料生成器：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stdlib.h>
#include <time.h>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int R = 100 ;

int main () {
	srand ( time ( NULL ) ) ;
	int n , x , y , q , ch ;
	freopen ( "poj3580.txt" , "w" , stdout ) ;
	REP ( Q , 0 , 10 ) {
		n = rand () % 100 + 1 ;
		printf ( "%d\n" , n ) ;
		REP ( i , 0 , n ) printf ( "%d " , rand () % R + 1 ) ;
		printf ( "\n" ) ;
		q = rand () % 100 + 1 ;
		printf ( "%d\n" , q ) ;
		while ( q -- ) {
			ch = rand () % 6 + 1 ;
			if ( ch == 1 ) {
				x = rand () % n + 1 ;
				while ( ( y = rand () % n + 1 ) < x ) ;
				printf ( "ADD %d %d %d\n" , x , y , rand () % R + 1 ) ;
			} else if ( ch == 2 ) {
				x = rand () % n + 1 ;
				while ( ( y = rand () % n + 1 ) < x ) ;
				printf ( "REVERSE %d %d\n" , x , y ) ;
			} else if ( ch == 3 ) {
				x = rand () % n + 1 ;
				while ( ( y = rand () % n + 1 ) < x ) ;
				printf ( "REVOLVE %d %d %d\n" , x , y , rand () % R + 1 ) ;
			} else if ( ch == 4 ) {
				printf ( "INSERT %d %d\n" , rand () % n + 1 , rand () % R + 1 ) ;
				++ n ;
			} else if ( ch == 5 ) {
				printf ( "DELETE %d\n" , rand () % n + 1 ) ;
				-- n ;
			} else {
				x = rand () % n + 1 ;
				while ( ( y = rand () % n + 1 ) < x ) ;
				printf ( "MIN %d %d\n" , x , y ) ;
			}
		}
	}
	return 0 ;
}