刚学分块的萌新求助
查看原帖
刚学分块的萌新求助
456419
Commandant楼主2022/2/18 22:15

想用分块过这道题,结果连样例都过不了

这是我的代码(刚学分块,可能有弱智问题,有误望指出):

#include <cmath>
#include <iostream>
using namespace std;

const int maxn = 1e5 + 10;
int n, m;
int a[maxn], sum[320], tag[320], bel[maxn], st[320], ed[320];

int main() {
    cin >> n >> m;
    int siz = sqrt(n);
    for (int i = 1; i <= siz; i++) {
        st[i] = n / siz * (i - 1) + 1;
        ed[i] = n / siz * i;
    }
    ed[siz] = n;
    for (int i = 1; i <= siz; i++) {
        for (int j = st[i]; j <= ed[i]; j++) {
            bel[j] = i;
        }
    }

    while (m--) {
        int c, l, r;
        cin >> c >> l >> r;
        if (c == 0) {
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    a[i] = 1 - a[i];
                    if (a[i]) {
                        sum[bel[i]]++;
                    } else {
                        sum[bel[i]]--;
                    }
                }
            } else {
                for (int i = l; i <= ed[bel[l]]; i++) {
                    a[i] = 1 - a[i];
                    if (a[i]) {
                        sum[bel[i]]++;
                    } else {
                        sum[bel[i]]--;
                    }
                }
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    tag[i] = 1 - tag[i];
                }
                for (int i = st[bel[r]]; i <= r; i++) {
                    a[i] = 1 - a[i];
                    if (a[i]) {
                        sum[bel[i]]++;
                    } else {
                        sum[bel[i]]--;
                    }
                }
            }
        } else if (c == 1) {
            int ans = 0;
            if (bel[l] == bel[r]) {
                for (int i = l; i <= r; i++) {
                    int now = (tag[i] ? 1 - a[i] : a[i]);
                    if (now) {
                        ans++;
                    }
                }
            } else {
                for (int i = l; i <= ed[l]; i++) {
                    int now = (tag[i] ? 1 - a[i] : a[i]);
                    if (now) {
                        ans++;
                    }
                }
                for (int i = bel[l] + 1; i < bel[r]; i++) {
                    if (tag[i]) {
                        ans += (ed[i] - st[i] + 1) - sum[i];
                    } else {
                        ans += sum[i];
                    }
                }
                for (int i = st[r]; i <= r; i++) {
                    int now = (tag[i] ? 1 - a[i] : a[i]);
                    if (now) {
                        ans++;
                    }
                }
            }
            cout << ans << endl;
        }
    }
    return 0;
}
2022/2/18 22:15
加载中...