BZOJ1230 [Usaco2008 Nov]lites 开关灯

时间:2022-04-07 16:18:53

区间not,求区间1的个数。。。线段树裸题

然而窝并不会线段树

我们可以对序列分块,每个块记录0/1的个数和tag表示又没有区间not过就好了

 /**************************************************************
Problem: 1230
User: rausen
Language: C++
Result: Accepted
Time:796 ms
Memory:1608 kb
****************************************************************/ #include <cstdio>
#include <cmath>
#include <algorithm> using namespace std;
const int N = 1e5 + ;
const int SZ = ; int n, m;
int a[N];
int sz, b[N], st[SZ], cnt[SZ][], tag[SZ], cnt_block; inline int read() {
static int x;
static char ch;
x = , ch = getchar();
while (ch < '' || '' < ch)
ch = getchar();
while ('' <= ch && ch <= '') {
x = x * + ch - '';
ch = getchar();
}
return x;
} inline void pre() {
int i;
sz = sqrt(n);
if (!sz) sz = ;
for (i = ; i <= n; ++i) {
if (i % sz == || sz == ) st[++cnt_block] = i;
b[i] = cnt_block, ++cnt[cnt_block][];
}
st[cnt_block + ] = n + ;
} inline void push_tag(int B) {
static int i;
if (!tag[B]) return;
for (i = st[B]; i < st[B + ]; ++i)
a[i] = !a[i];
swap(cnt[B][], cnt[B][]);
tag[B] = ;
} inline void change(int x, int y) {
static int i, t1, t2;
t1 = b[x], t2 = b[y];
for (i = t1 + ; i < t2; ++i) tag[i] = !tag[i];
if (t1 == t2)
for (push_tag(t1), i = x; i <= y; ++i)
--cnt[t1][a[i]], a[i] = !a[i], ++cnt[t1][a[i]];
else {
for (push_tag(t1), i = x; i < st[t1 + ]; ++i)
--cnt[t1][a[i]], a[i] = !a[i], ++cnt[t1][a[i]];
for (push_tag(t2), i = st[t2]; i <= y; ++i)
--cnt[t2][a[i]], a[i] = !a[i], ++cnt[t2][a[i]];
}
} inline int query(int x, int y) {
static int i, t1, t2, res;
t1 = b[x], t2 = b[y], res = ;
for (i = t1 + ; i < t2; ++i)
res += cnt[i][!tag[i]];
if (t1 == t2)
for (push_tag(t1), i = x; i <= y; ++i) res += a[i];
else {
for (push_tag(t1), i = x; i < st[t1 + ]; ++i) res += a[i];
for (push_tag(t2), i = st[t2]; i <= y; ++i) res += a[i];
}
return res;
} int main() {
int i, oper, x, y;
n = read(), m = read();
pre();
for (i = ; i <= m; ++i) {
oper = read(), x = read(), y = read();
if (oper == ) change(x, y);
else printf("%d\n", query(x, y));
}
return ;
}