Codeforces 182 C. Optimal Sum

問題

数列a[i]が与えられる。
この数列のうち、最大k個の符号を好きに変えることができる。

このとき、連続するlen個の区間の和の絶対値| Σ[j = i to i + len - 1]a[j] | の最大値を求めよ。

制約条件

n≦10^5
a[i]≦10000
k≦n

方針

符号をマイナスからプラスに変えるだけを許したときの最大値をa[i]と、-a[i]について求めればよい。

これは、区間の中でマイナスのもののうち、小さいものから貪欲にk個マイナスの符号をつければよく、
集合のk番目の値を効率的に取り出す＆集合の更新を効率的にやるには、平衡二分木などを使えば良い。

ソースコード

avl_treeはspaghetti sourceの。

int a[100000];

void run()
{
	int len, n, k;
	cin >> n >> len;
	rep(i, n) cin >> a[i];
	cin >> k;
	
	ll ans = -1ll << 60;
	rep(it, 2){
		avl_tree<int> tree;
		
		ll sum = 0;
		int sz = 0;
		rep(i, n){
			
			if(i >= len){
				sum -= a[i-len];
				if(k && a[i-len] < 0){
					if(sz < k || a[i-len] <= tree.rank(k-1)->key){
						sum += 2 * a[i-len];
						if(sz >= k+1) sum -= 2 * tree.rank(k)->key;
					}
					sz--;
					tree.erase(a[i-len]);
				}
			}
			
			sum += a[i];
			if(k && a[i] < 0){
				if(sz < k || a[i] <= tree.rank(k-1)->key){
					sum -= 2 * a[i];
					if(sz >= k) sum += 2 * tree.rank(k-1)->key;
				}
				sz++;
				tree.insert(a[i]);
			}
			if(i >= len - 1) ans = max(ans, sum);
		}
		if(it == 0) rep(i, n) a[i] *= -1;
	}
	cout << ans << endl;
}