Manthan, Codefest 17F: Nagini

http://codeforces.com/contest/855/problem/F

平方分割強い(確信)

平方分割してブロックでまとめて解く。
もしブロック内に0が存在したら普通に更新。
0がなかったら反対側を見て、0ではない値をとるようだったら配列に値を入れてsortする。
ブロックの更新が来たら、配列を上から見ていって、順番に適切なところまで値を削除していく。するとならし計算でO(Q√NlogN)とかで求められるので間に合う。

コードはTourist氏のものを参考にした。っていうかほとんど写経になってしまったが。無駄がほとんどなくてすごすぎる。僕はめっちゃバグらせました。(半ギレ)

pushは要素ごとに更新を行うための前処理で、pullでブロックをまとめて更新するための前処理。

Query系のよくあるテクニックとしてほかにSegtreeとMoがありますが、適当にまとめておきます。

1.求めるものが線形結合可能
数列を持つ必要がないor数列を持つとしても数列に対して更新を行わない
→segtree
数列に対してなんらかの更新を行う必要がある
→square decomposition
2.求めるものが線形結合不可(例えば最頻値とか)
update queryがない
→Mo or その上位互換
update queryがある
→ムリw(adhocな解法になりそう)

const int BLOCK = 300;
const int CNT = MAX_N / BLOCK + 10;

int Q;
int A[2][MAX_N];
int B[2][CNT];
bool zeros[2][CNT];
vector<int> C[2][CNT];
int sz[2][CNT];
ll sum[CNT];

inline void update(int &a, int b) {
	if(a == 0 || b == 0) a = a + b;
	else a = min(a, b);
}

void push(int id) {
	for(int p = 0; p < 2; p++) {
		if(!B[p][id]) continue;
		for(int i = id * BLOCK; i < (id + 1) * BLOCK; i++) {
			update(A[p][i], B[p][id]);
		}
		B[p][id] = 0;
	}
}

void pull(int id) {
	rep(p, 0, 2) {
		bool ok = false;
		for(int i = id * BLOCK; i < (id + 1) * BLOCK; i++) {
			if(A[p][i] == 0) {
				ok = true;
				break;
			}
		}
		zeros[p][id] = ok;
		if(ok) continue;
		C[p][id].clear();
		for(int i = id * BLOCK; i < (id + 1) * BLOCK; i++) {
			if(A[1 - p][i] != 0) C[p][id].pb(A[p][i]);
		}
		sz[p][id] = sz(C[p][id]);
		sort(all(C[p][id]));
	}
	sum[id] = 0;
	for(int i = id * BLOCK; i < (id + 1) * BLOCK; i++) {
		if(A[0][i] && A[1][i]) {
			sum[id] += A[0][i] + A[1][i];
		}
	}
}

void update_block(int id, int p, int k) {
	int old = B[p][id];
	update(B[p][id], k);
	if(zeros[p][id]) {
		push(id);
		pull(id);
	}
	else {
		int extra = sz[p][id] - sz(C[p][id]);
		if(old > k) {
			sum[id] -= extra * 1LL * (old - k);
		}
		while(!C[p][id].empty() && C[p][id].back() > k) {
			sum[id] -= C[p][id].back() - k;
			C[p][id].pop_back();
		}
	}
}

ll get_block(int id) {
	return sum[id];
}

void solve() {
	rep(p, 0, 2) 
		rep(k, 0, CNT) zeros[p][k] = true;
	cin >> Q;
	while(Q--) {
		int t, l, r, k, p;
		cin >> t >> l >> r; l--; r--;
		int lid = l / BLOCK, rid = r / BLOCK;
		if(t == 1) {
			cin >> k;
			p = (k >= 0); k = abs(k);
			//debug(l, r, lid, rid, p, k, (lid + 1) * BLOCK, rid * BLOCK);
			push(lid); push(rid);
			while(l < r && l < (lid + 1) * BLOCK) {
				update(A[p][l], k);
				l++;
			}
			while(l < r && r > rid * BLOCK) {
				update(A[p][r - 1], k);
				r--;
			}
			pull(lid); pull(rid);
			for(int id = lid + 1; id < rid; id++) {
				update_block(id, p, k);
			}
		}
		else {
			ll ans = 0;
			push(lid); push(rid);
			while(l < r && l < (lid + 1) * BLOCK) {
				if(A[0][l] && A[1][l]) ans += A[0][l] + A[1][l];
				l++;
			}
			while(l < r && r > rid * BLOCK) {
				if(A[0][r - 1] && A[1][r - 1]) ans += A[0][r - 1] + A[1][r - 1];
				r--;
			}
			for(int id = lid + 1; id < rid; id++) {
				ans += get_block(id);
			}
			cout << ans << "\n";
			pull(lid); pull(rid);
		}
		/*
		rep(p, 0, 2) {
			debug(vi(A[p], A[p] + 10));
			debug(vi(B[p], B[p] + 3));
			debug(vector<vi>(C[p], C[p] + 3));
		}
		debug(vi(sum, sum + 3));
		*/
	}
}