【HDU】5367 digger【动态线段树】

本文主要是介绍【HDU】5367 digger【动态线段树】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：【HDU】5367 digger

$my~~code:$

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std ;typedef long long LL ;#define clr( a , x ) memset ( a , x , sizeof a )const int MAXN = 50005 ;
const int INF = 0x3f3f3f3f ;struct Node {int sum , lsum , rsum ;int lnum , rnum ;int lf , rf ;int ls , rs ;int l , r , len ;int add ;void init ( int _l , int _r ) {add = sum = lnum = rnum = lf = rf = ls = rs = 0 ;l = _l ;r = _r ;lsum = rsum = len = r - l + 1 ;}
} ;Node T[MAXN * 60] ;
int root , cur ;
int n , m ;void check ( int& o , int l , int r ) {if ( o ) return ;o = ++ cur ;T[o].init ( l , r ) ;if ( l == 1 ) T[o].lf = INF ;if ( r == n ) T[o].rf = INF ;
}void pushup ( int o ) {int m = ( T[o].l + T[o].r ) >> 1 ;check ( T[o].ls , T[o].l , m ) ;check ( T[o].rs , m + 1 , T[o].r ) ;int ls = T[o].ls , rs = T[o].rs ;T[o].sum = T[ls].sum + T[rs].sum ;T[o].lnum = T[ls].lnum ;T[o].rnum = T[rs].rnum ;T[o].lsum = T[ls].lsum ;T[o].rsum = T[rs].rsum ;T[o].lf = T[ls].lf ;T[o].rf = T[rs].rf ;if ( T[ls].rnum == T[rs].lnum ) {if ( T[ls].rf < T[ls].rnum && T[rs].lf < T[rs].lnum ) {T[o].sum += T[ls].rsum + T[rs].lsum ;}if ( T[ls].rsum == T[ls].len ) {T[o].lf = T[rs].lf ;T[o].lsum += T[rs].lsum ;}if ( T[rs].lsum == T[rs].len ) {T[o].rf = T[ls].rf ;T[o].rsum += T[ls].rsum ;}} else {if ( T[ls].lsum == T[ls].len ) {T[o].lf = T[rs].lnum ;}if ( T[ls].rnum > T[ls].rf && T[ls].rnum > T[rs].lnum ) {T[o].sum += T[ls].rsum ;}if ( T[rs].rsum == T[rs].len ) {T[o].rf = T[ls].rnum ;}if ( T[rs].lnum > T[rs].lf && T[rs].lnum > T[ls].rnum ) {T[o].sum += T[rs].lsum ;}}
}void upd ( int o , int addv ) {T[o].add += addv ;T[o].lnum += addv ;T[o].rnum += addv ;T[o].lf += addv ;T[o].rf += addv ;
}void pushdown ( int o ) {int m = ( T[o].l + T[o].r ) >> 1 ;if ( T[o].add ) {check ( T[o].ls , T[o].l , m ) ;check ( T[o].rs , m + 1 , T[o].r ) ;upd ( T[o].ls , T[o].add ) ;upd ( T[o].rs , T[o].add ) ;T[o].add = 0 ;}
}void update ( int L , int R , int v , int& o , int l , int r ) {check ( o , l , r ) ;if ( L <= l && r <= R ) {upd ( o , v ) ;return ;}pushdown ( o ) ;int m = ( l + r ) >> 1 ;if ( L <= m ) update ( L , R , v , T[o].ls , l , m ) ;if ( m <  R ) update ( L , R , v , T[o].rs , m + 1 , r ) ;pushup ( o ) ;
}void show ( int o , int l , int r ) {if ( o == 0 ) {for ( int i = l ; i <= r ; ++ i ) {printf ( "%d " , 0 ) ;}return ;} else if ( !T[o].ls && !T[o].rs ) {for ( int i = l ; i <= r ; ++ i ) {printf ( "%d " , T[o].lnum ) ;}return ;}pushdown ( o ) ;int m = ( l + r ) >> 1 ;show ( T[o].ls , l , m ) ;show ( T[o].rs , m + 1 , r ) ;pushup ( o ) ;
}void solve () {int l , r , v ;root = cur = 0 ;int ans = 0 ;for ( int i = 0 ; i < m ; ++ i ) {scanf ( "%d%d%d" , &l , &r , &v ) ;l ^= ans ;r ^= ans ;v ^= ans ;if ( l > r ) swap ( l , r ) ;update ( l , r , v , root , 1 , n ) ;ans = T[1].sum ;printf ( "%d\n" , T[1].sum ) ;//show ( 1 , 1 , n ) ;//printf ( "\n" ) ;//printf ( "root.lsum = %d , root.rsum = %d\n" , T[root].lsum , T[root].rsum ) ;//printf ( "root.lf = %d , root.rf = %d\n" , T[root].lf , T[root].rf ) ;}
}int main () {while ( ~scanf ( "%d%d%*d" , &n , &m ) ) solve () ;return 0 ;
}