P4145 上帝造题的七分钟 2 / #6281. 数列分块入门 5

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
#define ll long long
const int N = 1e5 + 1 ;
const int M = 1e5 + 1 ;
ll n , m , T ;
ll a [ N ] ;
ll block [ N ] ;
ll sum [ N ] , vis [ N ] ;
void check ( int b )
{
    if ( vis [ b ] ) return ;
    if ( sum [ b ] == min ( n , b * T ) - ( b - 1 ) * T )
        vis [ b ] = 1;
}
void Sqrt ( int x , int y )
{
    if ( block [ x ] == block [ y ] )
    {
        if ( vis [ block [ x ] ] == 1 )
            return ;
        for ( int i = x ; i <= y ; i ++ )
        {
            sum [ block [ x ] ] -= a [ i ] ;
            a [ i ] = sqrt ( a [ i ] ) ;
            sum [ block [ x ] ] += a [ i ] ;
        }
        check ( block [ x ] ) ;
        return ;
    }
    if ( vis [ block [ x ] ] == 0 )
    for ( int i = x ; i <= block [ x ] * T  ; i ++ )
        sum [ block [ i ] ] -= a [ i ] ,
        a [ i ] = sqrt ( a [ i ] ) ,
        sum [ block [ i ] ] += a [ i ] ;

    if ( vis [ block [ y ] ] == 0 )
    for ( int i = ( block [ y ] - 1 ) * T + 1 ; i <= y ; i ++ )
        sum [ block [ i ] ] -= a [ i ] ,
        a [ i ] = sqrt ( a [ i ] ) ,
        sum [ block [ i ] ] += a [ i ] ;

    for ( int j = block [ x ] + 1; j <= block [ y ] - 1 ; j ++ )
    {
        if ( vis [ j ] == 0 ) continue;
        for ( int i = ( j - 1 ) * T + 1 ; i <= j * T ; i ++ )
            sum [ block [ i ] ] -= a [ i ] ,
            a [ i ] = sqrt ( a [ i ] ) ,
            sum [ block [ i ] ] += a [ i ] ;
    }

    for ( int i = block [ x ] ; i <= block [ y ] ; i ++ )
        check ( i );
}
ll query ( int x , int y )
{
    ll ans = 0 ;
    if ( block [ x ] == block [ y ] )
    {
        for ( int i = x ; i <= y ; i ++ )
        {
            ans += a [ i ];
        }
        return ans ;
    }
    for ( int i = x ; i <= block [ x ] * T; i ++ )
    {
        ans += a [ i ] ;
    }
    for ( int i = ( block [ y ] - 1 ) * T + 1 ; i <= y ; i ++ )
    {
        ans += a [ i ] ;
    }
    for ( int i = block [ x ] + 1 ; i <= block [ y ] - 1 ; i ++ )
    {
        ans += sum [ i ] ;
    }
    return ans ;
}
int main()
{
    freopen ( "text.in" , "r" , stdin ) ;
    cin >> n ;
    T = sqrt ( n ) ;
    for ( int i = 1 ; i <= n ; i ++ )
    {
        cin >> a [ i ] ;
        block [ i ] = ( i - 1 ) / T + 1 ;
        sum [ block [ i ] ] += a [ i ] ;
    }
    cin >> m ;
    for ( int i = 1 ; i <= m ; i ++ )
    {
        int op , l , r ;
        cin >> op >> l >> r ;
        if ( l > r ) swap ( l , r ) ;
        if ( op == 0 )
        {
            Sqrt ( l , r ) ;
        }
        else
        {
            cout << query ( l , r ) << endl ;
        }
    }
    return 0 ;
}