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)); */ } }