chyx's Blog

typedef pair<int,int> pii;
template<class T> void inline checkMax(T& a, T b){if(a < b) a = b;};
#define Rep(i,n) for(int n_ = (n), i = 0; i< n_; ++i)
#define two(x) (1<<(x))
const int MAXN = two(17); // 128 * 1024
pii max_value[MAXN*2];
int C[MAXN*2];
int M = 1;
void add(int a, int b, int c){
	a+=M; b+=M;
	//           [1]
	//     [2]         [3]
	//  [4]   [5]   [6]   [7]
	// [] [] [] [] [] [] [] [] 
	bool meet = false;
	for(; a || b ; a/=2, b/=2){
		if( a / 2 != b / 2 ){ // 懒标记
			if( (a ^ 1) < a )C[a^1] -= c;
			if( b < (b ^ 1) )C[b^1] -= c;
		}
		if( a == b ){ // 跳出
			if(!meet)C[a] += c;
			meet = true;
		}
#define newv(a) pii(max_value[a].first + C[a], max_value[a].second)
		max_value[a/2] = max( newv(a), newv(a^1) );
		max_value[b/2] = max( newv(b), newv(b^1) );
	}
}
pii get(int a, int b){
	a+=M; b+=M;
	pii maxa(max_value[a]), maxb(max_value[b]);
	for(;a || b ; a/=2, b/=2){
		maxa.first += C[a];
		maxb.first += C[b];
		if( a / 2 != b / 2 ){
			if( a < (a ^ 1) )checkMax( maxa, newv(a^1) );
			if( (b ^ 1) < b )checkMax( maxb, newv(b^1) );
		}
	}
	return max(maxa, maxb);
}