链接:Miku
--------------------------------
%%%并感谢yyq大佬
--------------------------------
很显然可以用线段树操作
--------------------------------
这次的lazy指的是这个区间需不需要被反转,然后显然,一个区间反转后亮的灯泡的值就是区间灯泡总量-原来亮的值
但是如果一个区间被反转了偶数次,其实就相当于没动过,所以我们在处理懒标记的时候需要特判
----------------------------------
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n,m; long long sum[400005], lazy[400005]; int f,x,y; long long k; void pushdown(int x, int L, int R){ if (lazy[x] != 0){ int mid = (L + R) >> 1; lazy[x << 1] =(lazy[x<<1]+1)%2; lazy[x << 1 | 1] = (lazy[x<<1|1]+1)%2; sum[x << 1] = (mid - L + 1)-sum[x<<1]; sum[x << 1 | 1] = (R - mid)-sum[x<<1|1]; lazy[x] = 0; } return; } void pushup(int x){ sum[x] = sum[x << 1] + sum[x << 1 | 1]; return; } void update(int x, int l, int r, int L, int R){ if (L <= l && r <= R){ lazy[x] = (lazy[x]+1)%2; sum[x] = r - l + 1 - sum[x]; return; } int mid = (l + r) >> 1; pushdown(x, l, r); if (L <= mid) update(x << 1, l, mid, L, R); if (R > mid) update(x << 1 | 1, mid + 1, r, L, R); pushup(x); } long long query(int x, int l, int r, int L, int R){ if (L <= l && r <= R){ return sum[x]; } int mid = (l + r) >> 1; pushdown(x, l, r); long long ans = 0; if (L <= mid) ans += query(x << 1, l, mid, L, R); if (R > mid) ans += query(x << 1 | 1, mid + 1, r, L, R); return ans; } int main(){ scanf("%d% d",&n,&m); for(int i=1;i<=m;++i){ scanf("%d",&f); if(f==0){ scanf("%d%d",&x,&y); update(1, 1, n, x, y); } else{ scanf("%d%d",&x,&y); printf("%lld\n", query(1, 1, n, x, y)); } } return 0; }Ac'