思路 懒标记法 记stop[rt] 表示 rt这个线段树节点的下方儿子们需要被更新几次 记住是下方 量纲不要乱 否则写的一堆渣代码
我的代码里面black是维护黑灯的数量 其实做烦了 如果是维护白灯数量更简单
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define lrt rt<<1
#define rrt rt<<1|1
#define getmid int mid=(l+r)/2
using namespace std;
const int maxn=; int n,m,black[maxn*],stop[maxn*]; void pushdown(int l,int r,int rt)
{
getmid;
stop[lrt]+=stop[rt];
stop[rrt]+=stop[rt];
if(stop[rt]%==)
{
black[lrt]=mid-l+-black[lrt];
black[rrt]=r-mid-black[rrt];
}
stop[rt]=;
} void bud(int l,int r,int rt)
{
if(l==r) {
black[rt]=;
return;
}
getmid;
bud(lson);
bud(rson);
black[rt]=black[lrt]+black[rrt];
} int query(int l,int r,int rt,int a,int b)
{
pushdown(l,r,rt);
if(a<=l && b>=r)
{
return black[rt];
} getmid;
int ans=;
if(a<=mid) ans=query(lson,a,b);
if(b>mid) ans=ans+query(rson,a,b);
return ans;
} void update(int l,int r,int rt,int a,int b)
{
pushdown(l,r,rt);
if(a<=l && b>=r)
{
black[rt]=r-l+-black[rt];
stop[rt]++;
return;
}
getmid;
if(a<=mid) {update(lson,a,b);}
if(b>mid) {update(rson,a,b);}
black[rt]=black[lrt]+black[rrt];
} int main()
{
//freopen("lites.in","r",stdin);
//freopen("lites.out","w",stdout);
scanf("%d%d",&n,&m);
bud(,n,); for(int i=,a,b,c;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
if(a==)
{
update(,n,,b,c);
}
else
{
cout<<c-b+-query(,n,,b,c)<<endl;;
}
} return ;
}