P3870 [TJOI2009] 开关（线段树）

线段树）"/>

P3870 [TJOI2009] 开关（线段树）

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