codevs1690开关灯

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#define maxn 100010

using namespace std;

int n,m,num;

struct node

{

    int lc,rc;

    int l,r;

    int sum,bj;

}t[maxn*+];

void Build(int ll,int rr)

{

    int k=++num;

    t[k].l=ll;t[k].r=rr;

    if(ll==rr)return;

    t[k].lc=num+;

    Build(ll,(ll+rr)/);

    t[k].rc=num+;

    Build((ll+rr)/+,rr);

}

void update(int k)

{

    t[t[k].lc].sum=abs(t[t[k].lc].r-t[t[k].lc].l+-t[t[k].lc].sum);

    t[t[k].rc].sum=abs(t[t[k].rc].r-t[t[k].rc].l+-t[t[k].rc].sum);

    t[t[k].lc].bj=!t[t[k].lc].bj;

    t[t[k].rc].bj=!t[t[k].rc].bj;

    t[k].bj=;

}

void change(int k,int ll,int rr)

{

    if(ll<=t[k].l&&rr>=t[k].r)

      {

          t[k].bj=!t[k].bj;

          t[k].sum=abs(t[k].r-t[k].l+-t[k].sum);

          return;

      }

    if(t[k].bj)update(k);

    int mid=(t[k].l+t[k].r)/;

    if(rr<=mid)change(t[k].lc,ll,rr);

    else if(ll>mid)change(t[k].rc,ll,rr);

    else

      {

          change(t[k].lc,ll,mid);

          change(t[k].rc,mid+,rr);

      }

    t[k].sum=t[t[k].lc].sum+t[t[k].rc].sum;

}

int find(int k,int ll,int rr)

{

    if(ll<=t[k].l&&rr>=t[k].r)return t[k].sum;

    if(t[k].bj)update(k);

    int ans=;

    int mid=(t[k].l+t[k].r)/;

    if(rr<=mid)ans+=find(t[k].lc,ll,rr);

    else if(ll>mid)ans+=find(t[k].rc,ll,rr);

    else ans+=find(t[k].lc,ll,mid)+find(t[k].rc,mid+,rr);

    return ans;

}

int main()

{

    scanf("%d",&n);

    Build(,n);

    scanf("%d",&m);

    int x,y,z;

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

      {

          scanf("%d",&x);

          if(x==)

            {

                scanf("%d%d",&y,&z);

                change(,y,z);

          }

        if(x==)

            {

                scanf("%d%d",&y,&z);

                printf("%d\n",find(,y,z));

          }

      }

    return ;

}