LuoguP2846[USACO08NOV]光开关Light Switching【线段树维护区间异或】By cellur925

题目大意，给你一串灯，按一下开关可以将灯的状态取反（开变成关，关变成开）。维护这个序列的两种操作：询问区间内有多少灯是开着的，区间按灯。

开始想的是分别维护区间内0的数量，1的数量，两个懒标记。后来真正写到维护懒标记的时候却感觉不太可行，因为你并不精确的知道区间内哪里是开着，哪里是关着的。

其实我们本质上就是在维护整个异或序列。因为把每个位置取反，实际上就是在进行异或运算。（0->1，1->0）。这样我们在区间修改的时候，只需要维护区间内1的个数，把它用区间长度减去原来的值便得到新值。而懒标记的维护，直接进行异或运算即可。因为懒标记实际上就是在告诉儿子节点怎么做，传递简单的修改无法维护的信息。所以直接异或即可。

这个问题还有一个加加加加加加强版，bzoj1858，有时间干掉他。

Code

 #include<cstdio>

 #include<algorithm>

 #define maxn 100090 

 using namespace std;

 int n,m;

 struct SegmentTree{

     int l,r,len;

     int val,lazy;

 }t[maxn*];

 void build(int p,int l,int r)

 {

     t[p].l=l,t[p].r=r,t[p].len=r-l+;

     if(l==r)

         return ;

     int mid=(l+r)>>;

     build(p*,l,mid);

     build(p*+,mid+,r);

 }

 void update(int p)

 {

     if(t[p].l==t[p].r) return ;

     if(!t[p].lazy) return ;

     t[p*].val=t[p*].len-t[p*].val;

     t[p*+].val=t[p*+].len-t[p*+].val;

     t[p*].lazy^=;

     t[p*+].lazy^=;

     t[p].lazy=;

 }

 void change(int p,int l,int r)

 {

     update(p);

     if(t[p].l==l&&t[p].r==r)

     {

         t[p].lazy^=;

         t[p].val=t[p].len-t[p].val;

         return ;

     }

     int mid=(t[p].l+t[p].r)>>;

     if(l>mid) change(p*+,l,r);

     else if(r<=mid) change(p*,l,r);

     else change(p*,l,mid),change(p*+,mid+,r);

     t[p].val=t[p*].val+t[p*+].val;

 }

 int ask(int p,int l,int r)

 {

     update(p);

     if(t[p].l==l&&t[p].r==r) return t[p].val;

     int mid=(t[p].l+t[p].r)>>;

     if(l>mid) return ask(p*+,l,r);

     else if(r<=mid) return ask(p*,l,r);

     else return ask(p*,l,mid)+ask(p*+,mid+,r);

 }

 int main()

 {

     scanf("%d%d",&n,&m);

     build(,,n);

     for(int i=;i<=m;i++)

     {

         int opt=,l=,r=;

         scanf("%d%d%d",&opt,&l,&r);

         if(opt==)

             change(,l,r);

         else if(opt==)

             printf("%d\n",ask(,l,r));

     }

     return ;

 }

巴特西

LuoguP2846[USACO08NOV]光开关Light Switching【线段树维护区间异或】By cellur925

最新文章

热门文章