2750.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2750  User Id:fzk 
Memory:8236K  Time:1389MS
Language:C++  Result:Accepted

Source 

#include "stdio.h"
#include "memory.h"

const int SIZE = ( 1<<18 );
const int LEAF = ( 1<<17) - 1;

int sum[SIZE],l_max[SIZE],r_max[SIZE],l_min[SIZE], r_min[SIZE], min_e[SIZE], 
	s_max[SIZE], s_min[SIZE], pn, n;

inline int max( int a, int b ) {
	return a>b?a:b;
}

inline int min( int a, int b ) {
	return a<b?a:b;
}

void modify( int c ) {
	int c1 = c*2+1, c2 = c*2+2;
	sum[c] = sum[c1] + sum[c2];
	l_max[c] = max( l_max[c1], sum[c1]+l_max[c2] );
	r_max[c] = max( r_max[c2], sum[c2]+r_max[c1] );
	l_min[c] = min( l_min[c1], sum[c1]+l_min[c2] );
	r_min[c] = min( r_min[c2], sum[c2]+r_min[c1] );
	s_max[c] = max( max( s_max[c1], s_max[c2] ), r_max[c1]+l_max[c2] );
	s_min[c] = min( min( s_min[c1], s_min[c2] ), r_min[c1]+l_min[c2] );
	min_e[c] = min( min_e[c1], min_e[c2] );
}

void modify_leaf( int c, int v ) {
	sum[c] = v;
	s_max[c] = l_max[c] = r_max[c] = max( 0, sum[c] );
	s_min[c] = l_min[c] = r_min[c] = min( 0, sum[c] );
	min_e[c] = ( c < LEAF+n ? sum[c] : 999999 );
}

void creat( int l, int r, int c ) {
	if( c >= LEAF ) {
		modify_leaf( c, sum[c] ); 
	}
	else {
		creat( l, (l+r)/2, c*2+1 );
		creat( (l+r)/2+1, r, c*2+2 );
		modify( c );
	}
}

int k, v;
void change( int l, int r, int c ) {
	int h = (l+r)/2;
	if( l == r ) {
		if( sum[c] > 0 && v <= 0 )
			pn--;
		else if( sum[c]<=0 && v > 0 )
			pn++;
		modify_leaf( c, v );
	}
	else if( k <= h ) {
		change( l, h, c*2+1 );
		modify( c );
	}
	else {
		change( h+1, r, c*2+2 );
		modify( c );
	}
}

void init() {
	int i;

	memset( sum, 0, sizeof sum );
	pn = 0;

	scanf( "%d", &n );
	for( i=LEAF; i<LEAF+n; i++ ) {
		scanf( "%d", sum+i );
		if( sum[i] > 0 )
			pn++;
	}
	creat( 0, LEAF, 0 );
}

int get_ans( ) {
	if( pn == n )
		return sum[0] - min_e[0];
	return max( s_max[0], sum[0]-s_min[0] );
}

int main( ) {
	int m;

	init( );
	scanf( "%d", &m );

	while( m-- ) {
		scanf( "%d %d", &k, &v );
		k--;
		change( 0, LEAF, 0 );
		printf( "%d\n", get_ans( ) );
	}	

	return 0;
}