想用分块过这道题,结果连样例都过不了
这是我的代码(刚学分块,可能有弱智问题,有误望指出):
#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;
}