BZOJ-3211: 花神游历各国（线段树）

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3211

跟上帝造题的七分钟2那道题完全一样，就不多说了。。。练手题。。。期末考快到了，是不是该滚去学习了。。。

代码：

d1160924ab18972b3ae7c5ace4cd7b899f510af3.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std ;
 
#define MAXN 100100
#define L( t ) ( t << 1 ) 
#define R( t ) ( ( t << 1 ) ^ 1 )
#define update( t ) S[ t ] = S[ L( t ) ] + S[ R( t ) ] , flag[ t ] = flag[ L( t ) ] & flag[ R( t ) ]
#define check( ch ) ( ch >= '0' && ch <= '9' )
#define mid( l , r ) ( ( l + r ) >> 1 )
#define ll long long
 
void getint( int &t ) {
    int ch ; for ( ch = getchar(  ) ; ! check( ch ) ; ch = getchar(  ) ) ;
    t = ch - '0' ;
    for ( ch = getchar(  ) ; check( ch ) ; ch = getchar(  ) ) t *= 10 , t += ch - '0' ;
}
 
void putint( ll t ) {
    if ( ! t ) putchar( '0' ) ; else {
        int ans[ 40 ] ; ans[ 0 ] = 0 ;
        for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;
        for ( int i = ans[ 0 ] ; i ; -- i ) putchar( '0' + ans[ i ] ) ;
    }
    putchar( '\n' ) ;
}
 
int left[ MAXN * 4 ] , right[ MAXN * 4 ] , a[ MAXN ] , n , m ;
ll S[ MAXN * 4 ] ;
bool flag[ MAXN * 4 ] ;
 
void build( int l , int r , int t ) {
    left[ t ] = l , right[ t ] = r ;
    if ( l == r ) {
        S[ t ] = a[ l ] , flag[ t ] = a[ l ] <= 1 ;
        return ;
    }
    build( l , mid( l , r ) , L( t ) ) , build( mid( l , r ) + 1 , r , R( t ) ) ;
    update( t ) ;
}
 
void change( int l , int r , int t ) {
    if ( flag[ t ] ) return ;
    if ( left[ t ] == right[ t ] ) {
        S[ t ] = int( sqrt( S[ t ] ) ) ;
        flag[ t ] = S[ t ] <= 1 ;
        return ;
    }
    if ( r <= mid( left[ t ] , right[ t ] ) ) change( l , r , L( t ) ) ; else
    if ( l > mid( left[ t ] , right[ t ] ) ) change( l , r , R( t ) ) ; else {
        change( l , mid( left[ t ] , right[ t ] ) , L( t ) ) , change( mid( left[ t ] , right[ t ] ) + 1 , r , R( t ) ) ;
    }
    update( t ) ;
}
 
ll sum( int l , int r , int t ) {
    if ( l == left[ t ] && r == right[ t ] ) return S[ t ] ;
    if ( r <= mid( left[ t ] , right[ t ] ) ) return sum( l , r , L( t ) ) ; else
    if ( l > mid( left[ t ] , right[ t ] ) ) return sum( l , r , R( t ) ) ; else
    return sum( l , mid( left[ t ] , right[ t ] ) , L( t ) ) + sum( mid( left[ t ] , right[ t ] ) + 1 , r , R( t ) ) ;
}
 
int main(  ) {
    getint( n ) ; for ( int i = 0 ; i ++ < n ; ) getint( a[ i ] ) ;
    build( 1 , n , 1 ) ;
    getint( m ) ;
    while ( m -- ) {
        int x , l , r ; getint( x ) , getint( l ) , getint( r ) ;
        if ( x == 1 ) putint( sum( l , r , 1 ) ) ; else change( l , r , 1 ) ;
    }
    return 0 ; 
}