BZOJ-3038: 上帝造题的七分钟2（线段树）

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

（这几天学连通性DP学得快吐了。。。写到水数据结构转转心情把。。。）

线段树是搞不了段开平方的，但是由于每个数最多开五六次平方就成了1，所以直接暴力修改，然后线段树维护即可。

代码：

fc1f4134970a304ee1e76585d3c8a786c8175c8c.jpg.png

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
 
using namespace std ;
 
#define ll long long 
#define MAXN 100010
#define check( ch ) ( ch >= '0' && ch <= '9' )
 
void getint( ll &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 ) {
    int ans[ 40 ] ; ans[ 0 ] = 0 ;
    for ( ; t ; t /= 10 ) ans[ ++ ans[ 0 ] ] = t % 10 ;
    for ( ; ans[ 0 ] ; ans[ 0 ] -- )putchar( '0' + ans[ ans[ 0 ] ] ) ;
    putchar( '\n' ) ;
}
 
struct node {
    int l , r ;
    bool flag ; 
    ll sum ;
} T[ MAXN * 4 ] ;
 
void update( int t ) {
    T[ t ].flag = T[ t << 1 ].flag & T[ ( t << 1 ) ^ 1 ].flag ;
    T[ t ].sum = T[ t << 1 ].sum + T[ ( t << 1 ) ^ 1 ].sum ;
}
 
ll a[ MAXN ] , n , m ;
 
void Build( int l , int r , int t ) {
    T[ t ].l = l , T[ t ].r = r ;
    if ( l == r ) {
        T[ t ].sum = a[ l ] ; 
        T[ t ].flag = a[ l ] == 1 ;
        return ;
    }
    Build( l , ( l + r ) >> 1 , t << 1 ) ;
    Build( ( ( l + r ) >> 1 ) + 1 , r , ( t << 1 ) ^ 1 ) ;
    update( t ) ;
}
 
ll Sum( int l , int r , int t ) {
    if ( l == T[ t ].l && r == T[ t ].r ) return T[ t ].sum ;
    int mid = ( T[ t ].l + T[ t ].r ) >> 1 ;
    if ( r <= mid ) return Sum( l , r , t << 1 ) ;
    if ( l > mid ) return Sum( l , r , ( t << 1 ) ^ 1 ) ;
    return Sum( l , mid , t << 1 ) +Sum( mid + 1 , r , ( t << 1 ) ^ 1 ) ;
}
 
void Change( int l , int r , int t ) {
    if ( T[ t ].flag ) return ;
    if ( T[ t ].l == T[ t ].r ) {
        T[ t ].sum =sqrt( T[ t ].sum ) ;
        T[ t ].flag = T[ t ].sum == 1 ;
        return ;
    }
    int mid = ( T[ t ].l + T[ t ].r ) >> 1 ;
    if ( r <= mid )Change( l , r , t << 1 ) ; else
    if ( l > mid )Change( l , r , ( t << 1 ) ^ 1 ) ; else
    Change( l , mid , t << 1 ) ,Change( mid + 1 , r , ( t << 1 ) ^ 1 ) ;
    update( t ) ;
}
 
int main(  ) {
    getint( n ) ; 
    for ( int i = 0 ; i ++ < n ; )getint( a[ i ] ) ;
    Build( 1 , n , 1 ) ;
    getint( m ) ;
    while ( m -- ) {
        ll k , l , r ; 
        getint( k ) ,getint( l ) ,getint( r ) ;
        if ( l > r )swap( l , r ) ;
        if ( k ) {
            putint(Sum( l , r , 1 ) ) ;
        } else Change( l , r , 1 ) ;
    }
    return 0 ;
}