HDUnbsp;3473nbsp;Minimumnbsp;Sum(划分树)

 

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define MAX 100008

int map [ MAX ];
int od [ MAX ];
int val [ 20 ][ MAX ], left [ 20 ][ MAX ];
__int64 num;
__int64 ssum [ MAX ], sum [ 20 ][ MAX ];

int cmp( const void * a , const void *b)
{
    return ( int)( map [ *( int *) a ] - map [ *( int *)b ]);
}

void Build( int l , int r , int d)
{
    if( l == r ){ sum [ d ][ l ] = map [ od [ val [ d ][ l ]]]; return ;}
    int i , mid =( l + r) >> 1;
    int p = 0;
    __int64 sum_tmp = 0;
    for( i = l; i <= r; i ++)
    {
        if( val [ d ][ i ] <= mid)
        {
            val [ d + 1 ][ l +p ] = val [ d ][ i ];
            left [ d ][ i ] =++p;
            sum_tmp += map [ od [ val [ d ][ i ]]];
            sum [ d ][ i ] = sum_tmp;
        }
        else
        {
            left [ d ][ i ] =p;
            val [ d + 1 ][ mid + 1 + i - l -p ] = val [ d ][ i ];
            sum [ d ][ i ] = sum_tmp;
        }
    }
    Build( l , mid , d + 1);
    Build( mid + 1 , r , d + 1);
}

__int64 search( int s , int e , int k , int l , int r , int d)
{
    if( l == r) return l;
    int mid =( l + r) >> 1 ,ss , ee;
    __int64 ts;
    if(s == l) ts = sum [ d ][ e ];
    else ts = sum [ d ][ e ] - sum [ d ][s - 1 ];
    ss =s == l ? 0 : left [ d ][s - 1 ];
    ee = left [ d ][ e ];
    if( ee -ss >= k)
        return search( l +ss , l + ee - 1 , k , l , mid , d + 1);
    else
    {
        num += ts;
        return search( mid + 1 +s - l -ss , mid + 1 + e - l - ee , k - ee +ss , mid + 1 , r , d + 1);
    }
}

__int64 SUM( int l , int r , int ans , int k)
{
    __int64 mapsum;
    mapsum = ssum [ r ] - ssum [ l - 1 ];
    mapsum = mapsum - 2 * num + ( 2 * k + l - r - 3) * ans;
    return mapsum;
}

int main()
{
    int n , m , i;
    __int64 ncase , ans = 0;
    int s , t;
    scanf( "%I64d" , & ncase);
    while( ncase --)
    {
        scanf( "%d" , &n);
        ssum [ 0 ] = 0;
        for( i = 1; i <=n; i ++)
        {
            scanf( "%d" , & map [ i ]), od [ i ] = i;
            ssum [ i ] = ssum [ i - 1 ] + map [ i ];
        }
        qsort( od + 1 ,n , sizeof( od [ 0 ]), cmp);
        for( i = 1; i <=n; i ++)
            val [ 0 ][ od [ i ]] = i;
        Build( 1 ,n , 0);
        scanf( "%d" , & m);
        printf( "Case #%I64d: \n " , ++ ans);
        while( m --)
        {
            num = 0;
            scanf( "%d%d" , &s , & t);
            s ++; t ++;
            printf( "%I64d \n " , SUM(s , t , map [ od [ search(s , t ,( t -s) / 2 + 1 , 1 ,n , 0 )]],( t -s) / 2 + 1));
        }
        printf( " \n ");
    }
    return 0;
}