hdu 3911 线段树＋区间合并

模板题

#include 
#include 
#include 
#include 
#define MAX 100007using namespace std;int n,m;
int a[MAX];struct Tree
{int l , r , lmx[2] , rmx[2] , mx[2] , lazy;
}tree[MAX<<2];void push_up ( int u )
{for ( int i = 0 ; i < 2 ; i++ ){tree[u].lmx[i] = tree[u<<1].lmx[i];tree[u].rmx[i] = tree[u<<1|1].rmx[i];tree[u].mx[i] = max ( tree[u<<1].mx[i] , tree[u<<1|1].mx[i] );if ( tree[u<<1].lmx[i] == tree[u<<1].r - tree[u<<1].l + 1 )tree[u].lmx[i] = tree[u<<1].lmx[i] + tree[u<<1|1].lmx[i];if ( tree[u<<1|1].rmx[i] == tree[u<<1|1].r - tree[u<<1|1].l + 1 )tree[u].rmx[i] = tree[u<<1].rmx[i] + tree[u<<1|1].rmx[i];tree[u].mx[i] = max ( tree[u].mx[i] , tree[u<<1].rmx[i] + tree[u<<1|1].lmx[i] );}
}void push_down ( int u )
{int lazy = tree[u].lazy;if ( lazy&1 ){tree[u].lazy = 0;tree[u<<1].lazy += lazy;tree[u<<1|1].lazy += lazy;swap ( tree[u<<1].lmx[0] , tree[u<<1].lmx[1] );swap ( tree[u<<1].rmx[0] , tree[u<<1].rmx[1] );swap ( tree[u<<1].mx[0] , tree[u<<1].mx[1] );swap ( tree[u<<1|1].lmx[0] , tree[u<<1|1].lmx[1] );swap ( tree[u<<1|1].rmx[0] , tree[u<<1|1].rmx[1] );swap ( tree[u<<1|1].mx[0] , tree[u<<1|1].mx[1] );}
}void build ( int u , int l , int r )
{tree[u].l = l , tree[u].r = r;tree[u].lazy = 0;if ( l == r ){int c = a[l];tree[u].lmx[c] = tree[u].rmx[c] = tree[u].mx[c] = 1;tree[u].lmx[c^1] = tree[u].rmx[c^1] = tree[u].mx[c^1] = 0;return;}int mid = l + r >> 1;build ( u<<1 , l , mid );build ( u<<1|1 , mid+1 , r );push_up ( u );
}void update ( int u , int left , int right )
{int l = tree[u].l , r = tree[u].r;if ( left <= l && r <= right ){tree[u].lazy++;swap ( tree[u].lmx[0] , tree[u].lmx[1] );swap ( tree[u].rmx[0] , tree[u].rmx[1] );swap ( tree[u].mx[0] , tree[u].mx[1] );return;}push_down ( u );int mid = l + r >> 1;if ( left <= mid && right >= l )update ( u<<1 , left , right );if ( left <= r && right > mid )update ( u<<1|1 , left , right );push_up ( u );
}struct Ret
{int mx,lmx,rmx,l,r;Ret ( ) { }Ret ( int a , int b , int c , int d  , int w ) : mx ( a ) , lmx ( b ) , rmx ( c ) , l ( d ) , r ( w ) { }
};Ret query ( int u , int left , int right )
{int l = tree[u].l , r = tree[u].r;if ( left <= l && r <= right )return Ret ( tree[u].mx[1] , tree[u].lmx[1] , tree[u].rmx[1] , tree[u].l , tree[u].r );int mid = l + r >> 1;push_down ( u );if ( mid < left ) return query ( u<<1|1 , left , right );else if ( right <= mid ) return query ( u<<1 , left , right );else{Ret ret1 = query ( u<<1 , left , right );Ret ret2 = query ( u<<1|1 , left , right );Ret ret;ret.l = ret1.l , ret.r = ret2.r;ret.mx = max ( ret1.mx , ret2.mx );ret.lmx = ret1.lmx;ret.rmx = ret2.rmx;if ( ret1.lmx == ret1.r - ret1.l + 1 )ret.lmx = ret1.lmx + ret2.lmx;if ( ret2.rmx == ret2.r - ret2.l + 1 )ret.rmx = ret2.rmx + ret1.rmx;ret.mx = max ( ret.mx , ret1.rmx + ret2.lmx );return ret;}}int main ( )
{while ( ~scanf ( "%d" , &n ) ){for ( int i = 1 ; i <= n ; i++ ) scanf ( "%d" , &a[i] );scanf ( "%d" , &m );int f,l,r;build ( 1, 1 ,n );for ( int i = 0 ; i < m ; i++ ){scanf ( "%d%d%d" , &f , &l , &r );if ( f ) update ( 1 , l , r );else printf ( "%d\n" , query ( 1 , l , r ).mx );}}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！