[NOI2005]维修数列
中文题，题意不解释。。 平衡树模板，做法不解释。。就看你模板是否够硬了。。 先来发伸展树：#include#include #include using namespace std ; const int maxn = 1000502 ; const int INF = 1111111111 ; int size[maxn] , fa[maxn] , son[2][maxn] ; int sum[maxn] , col[maxn] , val[maxn] , re[maxn] ; int mm[maxn] , rm[maxn] , lm[maxn] , num[maxn] ; int sta[maxn] , top ; int tot , n ; int fun() { char ch; int flag=1,a=0; while(ch=getchar()) { if((ch>='0'&&ch<='9')||ch=='-')break; } if(ch=='-')flag=-1; else a=ch-'0'; while(ch=getchar()) { if(ch>='0'&&ch<='9')a=10*a+ch-'0'; else break; } return flag*a; } int max ( int a , int b ) { return a > b a : b ; } void push_up(int x){ int l=son[0][x],r=son[1][x]; size[x]=size[l]+size[r]+1; sum[x]=sum[l]+sum[r]+val[x]; lm[x]=max(lm[l],sum[l]+val[x]+max(0,lm[r])); rm[x]=max(rm[r],sum[r]+val[x]+max(0,rm[l])); mm[x]=max(0,rm[l])+val[x]+max(0,lm[r]); mm[x]=max(mm[l],max(mm[r],mm[x])); } void up_rev ( int rt ) { if ( !rt ) return ; swap ( son[0][rt] , son[1][rt] ) ; swap ( lm[rt] , rm[rt] ) ; col[rt] ^= 1 ; } void up_mak ( int rt , int v ) { if ( !rt ) return ; re[rt] = val[rt] = v ; sum[rt] = val[rt] * size[rt] ; mm[rt] = lm[rt] = rm[rt] = ( val[rt] > 0 sum[rt] : val[rt] ) ; } void push_down ( int rt ) { int ls = son[0][rt] , rs = son[1][rt] ; if ( col[rt] ) { up_rev ( ls ) ; up_rev ( rs ) ; col[rt] = 0 ; } if ( re[rt] != INF ) { up_mak ( ls , re[rt] ) ; up_mak ( rs , re[rt] ) ; re[rt] = INF ; } } void down ( int x ) { if ( !x ) return ; down ( fa[x] ) ; push_down ( x ) ; } void rot ( int x , int c ) { int y = fa[x] , z = fa[y] ; push_down ( y ) , push_down ( x ) ; son[!c][y] = son[c][x] ; if ( son[c][x] ) fa[son[c][x]] = y ; son[c][x] = y , fa[y] = x ; fa[x] = z ; if ( z ) { if ( y == son[0][z] ) son[0][z] = x ; else son[1][z] = x ; } push_up ( y ) ; } void splay ( int x , int to ) { while ( fa[x] != to ) { if ( fa[fa[x]] == to ) rot ( x , x == son[0][fa[x]] ) ; else { int y = fa[x] , z = fa[y] ; if ( x == son[0][y] ) { if ( y == son[0][z] ) rot ( y , 1 ) , rot ( x , 1 ) ; else rot ( x , 1 ) , rot ( x , 0 ) ; } else { if ( y == son[1][z] ) rot ( y , 0 ) , rot ( x , 0 ) ; else rot ( x , 0 ) , rot ( x , 1 ) ; } } } push_up ( x ) ; } int find ( int k , int rt ) { push_down ( rt ) ; int cnt = 0 ; if ( son[0][rt] ) cnt += size[son[0][rt]] ; if ( cnt + 1 == k ) return rt ; if ( cnt >= k ) return find ( k , son[0][rt] ) ; return find ( k - cnt - 1 , son[1][rt] ) ; } void init ( int p ) { size[p] = 1 ; son[0][p] = son[1][p] = fa[p] = 0 ; mm[p] = lm[p] = rm[p] = -INF ; val[p] = -INF , re[p] = INF , col[p] = 0 ; } int new_node () { tot ++ ; init ( tot ) ; return tot ; } int build ( int l , int r ) { if ( l > r ) return 0 ; int m = ( l + r ) >> 1 ; int p = new_node () ; if ( m != 0 && m != n + 1 ) val[p] = num[m] ; son[0][p] = build ( l , m - 1 ) ; if ( son[0][p] ) fa[son[0][p]] = p ; son[1][p] = build ( m + 1 , r ) ; if ( son[1][p] ) fa[son[1][p]] = p ; push_up ( p ) ; return p ; } void reuse ( int rt ) { sta[++top] = rt ; if ( son[0][rt] ) reuse ( son[0][rt] ) ; if ( son[1][rt] ) reuse ( son[1][rt] ) ; init ( rt ) ; } int add[maxn] ; int insert ( int rt ) { int pos , t , i , last ; pos = fun () ; t = fun() ; if ( t <= 0 ) return rt ; pos ++ ; int temp = find ( pos , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( pos + 1 , rt ) ; splay ( temp , rt ) ; for ( i = 1 ; i <= t ; i ++ ) { add[i] = ( top sta[top--] : new_node () ) ; val[add[i]] = fun () ; } son[1][add[t]] = temp , fa[temp] = add[t] ; push_up ( add[t] ) ; for ( i = t - 1 ; i >= 1 ; i -- ) { son[1][add[i]] = add[i+1] ; fa[add[i+1]] = add[i] ; push_up ( add[i] ) ; } son[1][rt] = add[1] , fa[add[1]] = rt ; push_up ( rt ) ; return rt ; } int del ( int rt ) { int pos , t ; pos = fun () ; t = fun () ; if ( t <= 0 ) return rt ; pos ++ ; int temp = find ( pos - 1 , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( pos + t , rt ) ; splay ( temp , rt ) ; reuse ( son[0][temp] ) ; son[0][temp] = 0 ; push_up ( temp ) ; push_up ( rt ) ; return rt ; } int make ( int rt ) { int pos , t , fix ; pos = fun () ; t = fun () ; fix = fun () ; if ( t <= 0 ) return rt ; pos ++ ; int temp = find ( pos - 1 , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( pos + t , rt ) ; splay ( temp , rt ) ; int x = son[0][temp] ; up_mak ( x , fix ) ; push_up ( temp ) ; push_up ( rt ) ; return rt ; } int rev ( int rt ) { int pos , t ; pos = fun () ; t = fun () ; if ( t <= 1 ) return rt ; pos ++ ; int temp = find ( pos - 1 , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( pos + t , rt ) ; splay ( temp , rt ) ; int x = son[0][temp] ; up_rev ( x ) ; push_up ( temp ) ; push_up ( rt ) ; return rt ; } int get ( int rt ) { int pos , t ; pos = fun () ; t = fun () ; if ( t <= 0 ) { puts ( "0" ) ; return rt ; } pos ++ ; int temp = find ( pos - 1 , rt ) ; splay ( temp , 0 ) ; rt = temp ; temp = find ( pos + t , rt ) ; splay ( temp , rt ) ; printf ( "%d\n" , sum[son[0][temp]] ) ; return rt ; } int max_sum ( int rt ) { printf ( "%d\n" , mm[rt] ) ; return rt ; } char op[111] ; int main () { int m , i ; // freopen ( "sequence8.in" , "r" , stdin ) ; // freopen ( "ans1.txt" , "w" , stdout ) ; while ( scanf ( "%d%d" , &n , &m ) != EOF ) { tot = top = 0 ; init ( 0 ) ; size[0] = sum[0] = 0 ; for ( i = 1 ; i <= n ; i ++ ) { num[i] = fun () ; } int root = build ( 0 , n + 1 ) ; while ( m -- ) { scanf ( "%s" , op ) ; if ( op[2] == 'S' ) root = insert ( root ) ; else if ( op[2] == 'L' ) root = del ( root ) ; else if ( op[2] == 'K' ) root = make ( root ) ; else if ( op[2] == 'V' ) root = rev ( root ) ; else if ( op[2] == 'T' ) root = get ( root ) ; else root = max_sum ( root ) ; } } }
再来一发treap
#include#include #include #include