square869120Contest #2 H - Counting 1's (その 3)
一度で三度おいしい。
解法
すぎむ先生に教えてもらいました。クエリで平方分割する方法です。
@mayoko_ 反転クエリの両端 l, r を multiset S へ突っ込んでいくと、質問クエリに O(|S|) で答えることができます。|S| が √Q に達したら、ABC #035 C の要領で配列を O(N) で再計算し、S を空にします。全体で O((N+Q)√Q)
— すぎむ (@sugim48) 2016年4月25日
反転クエリ [l, r) を set S に詰め込んでおくと, 質問クエリには O(|S|) で答えられます。|S| は最大 N 個の要素を持つのでこれだと間に合いませんが, |S| がそこそこ大きくなるごとに bit を更新すると計算を抑えることが出来そうです。
実際, |S| の大きさが O(sqrt(Q)) になる程度で O(N) かけて bit を更新しておけば, 質問クエリは O(Q*sqrt(Q)), 更新クエリには O(N*sqrt(Q)) で応答できるので間に合います。
const int MAXN = 100010; int sum[MAXN], bit[MAXN]; int main() { cin.tie(0); ios::sync_with_stdio(false); int N, Q; cin >> N >> Q; set<int> S; while (Q--) { if (S.size() > 500) { vi v(S.begin(), S.end()); int sz = v.size(); for (int k = 0; k+1 < sz; k+=2) { for (int ptr = v[k]; ptr < v[k+1]; ptr++) bit[ptr] ^= 1; } for (int i = 0; i < N; i++) sum[i+1] = sum[i]+bit[i]; S.clear(); } int q, l, r; cin >> q >> l >> r; if (q==1) { if (S.find(l) == S.end()) S.insert(l); else S.erase(l); if (S.find(r) == S.end()) S.insert(r); else S.erase(r); } else { vi v(1); for (int el : S) v.push_back(el); v.push_back(N); int sz = v.size(); int ans = 0; for (int i = 0; i+1 < sz; i++) { int lp = max(l, v[i]), rp = min(r, v[i+1]); if (lp < rp) { int x = sum[rp]-sum[lp]; if (i%2) x = rp-lp-x; ans += x; } } cout << ans << endl; } } return 0; }