P3870 [TJOI2009] 开关
思路：可以用线段树来维护区间中亮灯的个数，区间修改用加上懒标记就好
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1e5 + 10;
struct SegmentTree{
int l, r;
LL sum, add;
#define l(x) tree[x].l
#define r(x) tree[x].r
#define sum(x) tree[x].sum
#define add(x) tree[x].add
}tree[4 * N];
int n, m;
void build(int p, int l, int r)
{
l(p) = l, r(p) = r;
if(l == r) {sum(p) = 0; return;}
int mid = (l + r) >> 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
sum(p) = sum(p << 1) + sum(p << 1 | 1);
}
//懒标记下传
void spread(int p)
{
//节点p
if(add(p))
{
sum(p << 1) = r(p << 1) - l(p << 1) + 1 - sum(p<<1);//更新左子节点信息
sum(p << 1 | 1) = r(p << 1 | 1) - l(p << 1 | 1) + 1 - sum(p << 1 | 1);//更新右子节点信息
add(p << 1) = ~add(p << 1);//给左子节点打延迟标记
add(p << 1 | 1) = ~add(p << 1 | 1);//给右子节点打延迟标记
add(p) = 0; //清楚p的标记
}
}
void change(int p, int l, int r)
{
if(l <= l(p) && r >= r(p))
{
sum(p) = r(p) - l(p) + 1 - sum(p);
add(p) = ~add(p);
return;
}
spread(p);
int mid = (l(p) + r(p)) >> 1;
if(l <= mid) change(p << 1, l, r);
if(r > mid) change(p << 1 | 1, l, r);
sum(p) = sum(p << 1) + sum(p << 1 | 1);
}
long long ask(int p, int l, int r)
{
if(l <= l(p) && r >= r(p)) return sum(p);
spread(p);
int mid = (l(p) + r(p)) >> 1;
long long val = 0;
if(l <= mid) val += ask(p << 1, l , r);
if(r > mid) val += ask(p << 1 | 1, l, r);
return val;
}
void solve()
{
cin >> n >> m;
build(1, 1, n);
while(m --)
{
int op, l, r, d;
cin >> op >> l >> r;
if(op == 0) change(1, l, r);
else cout << ask(1, l, r) << endl;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
// freopen("1.in", "r", stdin);
solve();
return 0;
}