洛谷P3870 [TJOI2009] 开关 （线段树）

简单的省选题......

打异或标记即可。

 1 #include<bits/stdc++.h>

 2 const int N=2e5+10;

 3 using namespace std;

 4 int n,m,a,b,c;

 5 struct node{

 6     int l,r,num,lazy;

 7 }t[N<<2];

 8 int read(){

 9     int x=0,f=1;char c=getchar();

10     while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}

11     while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();

12     return x*f;

13 }

14

15 void pushup(int k){

16     t[k].num=t[k<<1].num+t[k<<1|1].num;

17 }

18

19 void pushdown(int k){

20     if(t[k].lazy){

21         t[k<<1].num=t[k<<1].r-t[k<<1].l+1-t[k<<1].num;

22         t[k<<1|1].num=t[k<<1|1].r-t[k<<1|1].l+1-t[k<<1|1].num;

23         t[k<<1].lazy^=1;

24         t[k<<1|1].lazy^=1;

25         t[k].lazy=0;

26     }

27 }

28

29 void build(int k,int l,int r){

30     t[k].l=l,t[k].r=r;

31     if(l==r) return ;

32     int mid=(l+r)>>1;

33     build(k<<1,l,mid);build(k<<1|1,mid+1,r);

34 }

35

36 void change(int k,int l,int r){

37     if(t[k].l>=l && t[k].r<=r){

38         t[k].lazy^=1;

39         t[k].num=t[k].r-t[k].l+1-t[k].num;

40         return ;

41     }

42     pushdown(k);

43     int mid=(t[k].l+t[k].r)>>1;

44     if(l<=mid) change(k<<1,l,r);

45     if(r>mid) change(k<<1|1,l,r);

46     pushup(k);

47 }

48

49 int query(int k,int l,int r){

50     if(t[k].l>=l && t[k].r<=r) return t[k].num;

51     pushdown(k);

52     int ans=0;

53     int mid=(t[k].l+t[k].r)>>1;

54     if(l<=mid) ans+=query(k<<1,l,r);

55     if(r>mid) ans+=query(k<<1|1,l,r);

56     return ans;

57 }

58

59 int main(){

60     n=read(),m=read();

61     build(1,1,n);

62     while(m--){

63         c=read(),a=read(),b=read();

64         if(c==0) change(1,a,b);

65         else cout<<query(1,a,b)<<endl;

66     }

67 }

洛谷P3870 [TJOI2009] 开关 （线段树）的相关教程结束。