square869120Contest #2 H - Counting 1's (その 3)

一度で三度おいしい。

問題

s8pc-2.contest.atcoder.jp

解法

すぎむ先生に教えてもらいました。クエリで平方分割する方法です。

@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;
}