2 条题解

  • 0
    @ 2025-10-8 17:03:22
    #include <bits/stdc++.h>
    using namespace std;
    #define lc(p) (p<<1)
    #define rc(p) (p<<1|1)
    const int N=2e5+10;
    struct trnode{
        int l,r,s,lazy;
    }tr[N<<2];
    void pushup(int p)
    {
        tr[p].s=tr[lc(p)].s+tr[rc(p)].s;
    }
    void pushdown(int p)
    {
        if(tr[p].lazy)
        {
            tr[lc(p)].lazy^=1;
           
            tr[lc(p)].s=(tr[lc(p)].r-tr[lc(p)].l+1-tr[lc(p)].s);
    
            tr[rc(p)].lazy^=1;
    
            tr[rc(p)].s=(tr[rc(p)].r-tr[rc(p)].l+1-tr[rc(p)].s);
    
            tr[p].lazy=0;
        }
    }
    void bt(int p,int l,int r)
    {
        tr[p]={l,r,0,0};
        if(l==r)return;
        int m=(l+r)>>1;
        bt(lc(p),l,m);bt(rc(p),m+1,r);
    }
    void change(int p,int l,int r)
    {
        if(r<tr[p].l||tr[p].r<l)return;
        if(l<=tr[p].l&&tr[p].r<=r)
        {
            tr[p].lazy^=1;
            tr[p].s=(tr[p].r-tr[p].l+1-tr[p].s);
            return;
        }
        pushdown(p);
        change(lc(p),l,r);
        change(rc(p),l,r);
        pushup(p);
    }
    int query(int p,int l,int r)
    {
        if(r<tr[p].l||tr[p].r<l) return 0;
        if(l<=tr[p].l&&tr[p].r<=r) return tr[p].s;
        pushdown(p);
        return query(lc(p),l,r)+query(rc(p),l,r);
    }
    
    int main()
    {
        int n,m;scanf("%d%d",&n,&m);
        bt(1,1,n);
        for(int i=1,L,R;i<=m;i++)
        {
            int c;scanf("%d%d%d",&c,&L,&R);
            if(!c) change(1,L,R);
            else   printf("%d\n",query(1,L,R));
        }
        return 0;
    }
    
    • 0
      @ 2025-10-8 17:03:12
      #include <bits/stdc++.h>
      using namespace std;
      #define lc(p) (p<<1)
      #define rc(p) (p<<1|1)
      const int N=2e5+10;
      struct trnode{
          int l,r,s,lazy;
      }tr[N<<2];
      void pushup(int p)
      {
          tr[p].s=tr[lc(p)].s+tr[rc(p)].s;
      }
      void pushdown(int p)
      {
          if(tr[p].lazy)
          {
              tr[lc(p)].lazy^=1;
             
              tr[lc(p)].s=(tr[lc(p)].r-tr[lc(p)].l+1-tr[lc(p)].s);
      
              tr[rc(p)].lazy^=1;
      
              tr[rc(p)].s=(tr[rc(p)].r-tr[rc(p)].l+1-tr[rc(p)].s);
      
              tr[p].lazy=0;
          }
      }
      void bt(int p,int l,int r)
      {
          tr[p]={l,r,0,0};
          if(l==r)return;
          int m=(l+r)>>1;
          bt(lc(p),l,m);bt(rc(p),m+1,r);
      }
      void change(int p,int l,int r)
      {
          if(r<tr[p].l||tr[p].r<l)return;
          if(l<=tr[p].l&&tr[p].r<=r)
          {
              tr[p].lazy^=1;
              tr[p].s=(tr[p].r-tr[p].l+1-tr[p].s);
              return;
          }
          pushdown(p);
          change(lc(p),l,r);
          change(rc(p),l,r);
          pushup(p);
      }
      int query(int p,int l,int r)
      {
          if(r<tr[p].l||tr[p].r<l) return 0;
          if(l<=tr[p].l&&tr[p].r<=r) return tr[p].s;
          pushdown(p);
          return query(lc(p),l,r)+query(rc(p),l,r);
      }
      
      int main()
      {
          int n,m;scanf("%d%d",&n,&m);
          bt(1,1,n);
          for(int i=1,L,R;i<=m;i++)
          {
              int c;scanf("%d%d%d",&c,&L,&R);
              if(!c) change(1,L,R);
              else   printf("%d\n",query(1,L,R));
          }
          return 0;
      }
      • 1

      C25_3*【线段树】[USACO08NOV] Light Switching G | [TJOI2009] 开关

      信息

      ID
      2883
      时间
      2000ms
      内存
      16MiB
      难度
      6
      标签
      递交数
      44
      已通过
      15
      上传者