codevs 1690 开关灯 线段树水题

没什么好说的,标记put表示开关是否开着。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
int sum[N<<];
bool put[N<<];
void pushdown(int l,int r,int rt)
{
if (put[rt])
{
put[rt]=;
put[rt<<]=!put[rt<<];
put[rt<<|]=!put[rt<<|];
int mid=(l+r)>>;
sum[rt<<]=mid-l+-sum[rt<<];
sum[rt<<|]=r-mid-sum[rt<<|];
}
}
void add(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
{
sum[rt]=r-l+-sum[rt];
put[rt]=!put[rt];
return;
}
int mid=(l+r)>>;
pushdown(l,r,rt);
if (L<=mid) add(L,R,l,mid,rt<<);
if (R>mid) add(L,R,mid+,r,rt<<|);
sum[rt]=sum[rt<<]+sum[rt<<|];
}
int quest(int L,int R,int l,int r,int rt)
{
if (L<=l&&r<=R)
return sum[rt];
int mid=(l+r)>>,ans=;
pushdown(l,r,rt);
if (L<=mid) ans+=quest(L,R,l,mid,rt<<);
if (R>mid) ans+=quest(L,R,mid+,r,rt<<|);
return ans;
}
int main()
{
int i,n,m,x,y,z;
scanf("%d %d\n",&n,&m);
memset(sum,,sizeof(sum));
memset(put,,sizeof(put));
for (i=;i<=m;++i)
{
scanf("%d %d %d\n",&x,&y,&z);
if (x==) add(y,z,,n,);
else printf("%d\n",quest(y,z,,n,));
}
return ;
}

这样就可以了。

上一篇:Python中join()函数方法


下一篇:ssd存储的SLC、MLC、TLC闪存芯片颗粒有什么区别?