【 선분 수 】 스위치 (luogu 3870)

스위치
luogu 3870
제목 의 대의:
n 개의 등 이 있 습 니 다. 한 구간 에 있 는 모든 등 (켜 기, 끄 기, 켜 기, 조작 0) 을 누 르 거나 한 구간 에 몇 개의 등 이 켜 져 있 는 지 물 어보 거나 (조작 2) 조작 에 따라 출력 합 니 다.
샘플 입력 \ # 1:

4 5
0 1 2
0 2 4
1 2 3
0 2 4
1 1 4

출력 샘플 \ # 1:

1
2

문제 풀이 방향:
선분 트 리 를 사용 하고 스위치 등 을 켜 면 매번 1 을 더 하고 2 를 더 하 며 전체 구간 이 있 으 면 구간 길이 로 불 이 켜 진 수 를 줄 이 는 것 이다.
코드:

#include
using namespace std;
int n,m,u,x,y;
struct rec
{
     
    int l,r,num,lazy;
}tree[400500];
void make(int dep)//  
{
     
    if (tree[dep].l==tree[dep].r) return;
    int mid=(tree[dep].l+tree[dep].r)>>1;
    tree[dep*2].l=tree[dep].l,tree[dep*2].r=mid;
    tree[dep*2+1].l=mid+1,tree[dep*2+1].r=tree[dep].r;
    make(dep*2);
    make(dep*2+1);
    return;
}
void pass(int dep)//    
{
     
    if (tree[dep].lazy)
      {
     
      	tree[dep*2].lazy^=1;//  
        tree[dep*2+1].lazy^=1;
        tree[dep*2].num=tree[dep*2].r-tree[dep*2].l+1-tree[dep*2].num;//  
        tree[dep*2+1].num=tree[dep*2+1].r-tree[dep*2+1].l+1-tree[dep*2+1].num;
        tree[dep].lazy=0;
      }
}
void change(int dep,int l,int r)
{
     
    if (tree[dep].l==l&&tree[dep].r==r)//  
      {
     
      	tree[dep].num=tree[dep].r-tree[dep].l+1-tree[dep].num;//  
      	tree[dep].lazy^=1;
      	return;
      }
    if (tree[dep].l>=tree[dep].r) return;
    pass(dep);
    int mid=(tree[dep].l+tree[dep].r)>>1;
    if (r<=mid)//    
      {
     
      	change(dep*2,l,r);
      	tree[dep].num=tree[dep*2].num+tree[dep*2+1].num;
      	return;
      }
    if (l>mid)
      {
     
      	change(dep*2+1,l,r);
      	tree[dep].num=tree[dep*2].num+tree[dep*2+1].num;
      	return;
      }
    change(dep*2,l,mid);
    change(dep*2+1,mid+1,r);
    tree[dep].num=tree[dep*2].num+tree[dep*2+1].num;
    return;
}
int find(int dep,int l,int r)//  
{
     
    if (tree[dep].l==l&&tree[dep].r==r) return tree[dep].num;
    if (tree[dep].l>=tree[dep].r) return 0;
    pass(dep);
    int mid=(tree[dep].l+tree[dep].r)>>1;
    if (r<=mid) return find(dep*2,l,r);
    if (l>mid) return find(dep*2+1,l,r);
    return find(dep*2,l,mid)+find(dep*2+1,mid+1,r);
}
int main()
{
     
    scanf("%d %d",&n,&m);
    tree[1].l=1;
    tree[1].r=n;
    make(1);
    for (int i=1;i<=m;++i)
      {
     
      	scanf("%d %d %d",&u,&x,&y);
      	if (!u) change(1,x,y);//  1
      	else printf("%d
",find(1,x,y));
      }
}