洛谷P3870开关题解

「爱情、让人受尽委屈。」 2021-10-01 03:52 505阅读 0赞

我们先看题面，一看是一个区间操作，再看一下数据范围，就可以很轻松地想到是用一个数据结构来加快区间查询和修改的速度，所以我们很自然的就想到了线段树。

但是这个题还跟普通的线段树不一样，这个题可以说要思考一下，我们可以知道一个区间内如果要修改的话那假如说原来有x个灯开着，那一次操作之后就变成了这个区间的长度减去x个灯。因此我们可以把懒标记确认为是否要下放因为这是棵**线段**树，每一个节点都表示一个区间，那一次修改可能会修改多次这个区间所以如果这次区间修改了，那就不用修改了。

其他就跟平常的线段树一样了。

代码：

#include<iostream>
    #include<cstdio>
    #include<bits/stdc++.h> 
    #define ll long long
    #define ls left,mid,root<<1
    #define rs mid+1,right,root<<1|1
    using namespace std;
    int ans[1000010],n,m,lazy[1000100];
    void pushup(ll root)
    {
        ans[root]=ans[root<<1]+ans[root<<1|1];
    }
    void pushdown(ll root,ll mid,ll left,ll right)
    {
      if(lazy[root])
      {
        lazy[root<<1]^=1;
        lazy[root<<1|1]^=1;
        ans[root<<1]=(mid-left+1)-ans[root<<1];
        ans[root<<1|1]=(right-mid)-ans[root<<1|1];
        lazy[root]=0;
      }
    }
    ll query(ll l,ll r,ll left,ll right,ll root)//区间查询，l，r是要查询的区间，left，right，是当前区间
    {
      ll res1=0,res2=0;
      if(l<=left&&r>=right)
      {
        return ans[root];
      }
      ll mid=(left+right)>>1;
      pushdown(root,mid,left,right);
      if(l<=mid)
      res1=query(l,r,ls);
      if(r>=mid+1)
      res2=query(l,r,rs);
      return res1+res2;
    }
    void update(ll l,ll r,ll left,ll right,ll root)
    {
      if(l<=left&&r>=right)
      {
        lazy[root]^=1;
        ans[root]=(right-left+1)-ans[root];
        return;
      }
      ll mid=(left+right)>>1;
      pushdown(root,mid,left,right);
      if(l<=mid)
      update(l,r,ls);
      if(r>=mid+1)
      update(l,r,rs);
      pushup(root);
    }
    int main()
    {
      scanf("%d%d",&n,&m);
      for(int i=1;i<=m;i++)    
      {
          int flag;
          int x,y;
          scanf("%d",&flag);
          scanf("%d%d",&x,&y);
          if(flag)
          printf("%d\n",query(x,y,1,n,1));
          else
          update(x,y,1,n,1);
      }
    }

转载于:https://www.cnblogs.com/liuwenyao/p/9264947.html