这里是题目

Lazy Segment Tree

题目描述

给你一个长为 $N$ 的 01序列 $A=(A_1,A_2,⋯,A_N)$。

处理 $Q$ 个询问：第 $i$ 个询问用三个整数 $T_i, L_i, R_i$ 表示。

• $T_i = 1$：对于每个下标 $L_i \le j \le R_i$，把 $A_j$ 改为 $1-A_j$。

• $T_i = 2$：计算序列 $A_{L_i}, A_{L_i + 1}, \dots, A_{R_i}$ 的逆序数。

注：序列 $x_1, x_2, \dots, x_k$ 的逆序数是满足下述条件的整数对 $i, j$ 的数量。

• $1 \le i < j \le k$ 且 $x_i > x_j$。

限制

• $1 \le N \le 2\times 10^5$
• $0 \le A_i \le 1$
• $1 \le Q \le 2\times 10^5$
• $1 \le L_i \le R_i \le N$

输入格式

$N\quad Q$
$A_1 \quad A_2 \quad \dots \quad A_N$
$T_1\quad L_1\quad R_1$
$T_2\quad L_2\quad R_2$
$\vdots$
$T_Q \quad L_Q \quad R_Q$

输出格式

对于每个 $T_i = 2$ 的询问，输出答案。

样例 #1

样例输入 #1

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

样例输出 #1

2
0
1

这里是我的答案

#include<bits/stdc++.h>
using namespace std;
int n,m;
struct tree{
	long long v,v0,v1,l,r,tag;
};
int b[250001];
tree a[1000000];
void down(int k){
	if(a[k].tag==1){
		a[k*2].tag=1-a[k*2].tag;
		a[k*2].v=(a[k*2].r-a[k*2].l+1)*(a[k*2].r-a[k*2].l)/2-a[k*2].v;
   	    int vv0=a[k*2].v0;
   	    a[k*2].v0=a[k*2].v1;
   	    a[k*2].v1=vv0;
   	    a[k*2+1].tag=1-a[k*2+1].tag;
		a[k*2+1].v=(a[k*2+1].r-a[k*2+1].l+1)*(a[k*2+1].r-a[k*2+1].l)/2-a[k*2+1].v;
   	    vv0=a[k*2+1].v0;
   	    a[k*2+1].v0=a[k*2+1].v1;
   	    a[k*2+1].v1=vv0;
   	    a[k].tag=0;
	}
}
void bulid(int x,int l,int r){
	a[x].l=l;
	a[x].r=r;
	if(l==r){
		if(b[l]==1){
			a[x].v1+=1;
		}else{
			a[x].v0+=1;
		}
		a[x].v=0;
		return;
	}
	int mid=(l+r)/2;
	bulid(x*2,l,mid);
	bulid(x*2+1,mid+1,r);
	a[x].v0=a[x*2].v0+a[x*2+1].v0;
	a[x].v1=a[x*2].v1+a[x*2+1].v1;
	a[x].v=a[x*2].v+a[x*2+1].v+a[x*2].v1*a[x*2+1].v0;
	return;
}
void change(int x,int l,int r){
	if(l<=a[x].l&&a[x].r<=r){
   	    a[x].tag=1-a[x].tag;
   	    a[x].v=(a[x].r-a[x].l+1)*(a[x].r-a[x].l)/2-a[x].v;
   	    int vv0=a[x].v0;
   	    a[x].v0=a[x].v1;
   	    a[x].v1=vv0;
   	    return;
	}
	int mid=(l+r)/2;
	down(x);
	if(l<=mid){
		change(2*x,l,mid);
	}
	if(r>mid){
	   	change(2*x+1,mid+1,r);
	}
	return;
}
long long cha(int x,int l,int r){
	if(l<=a[x].l&&a[x].r<=r){
		return a[x].v;
	}
	down(x);
	int mid=(l+r)/2;
	int ans=0;
	if(l<=mid){
		ans+=cha(2*x,l,mid);
	}
	if(r>mid){
	   	ans+=cha(2*x+1,mid+1,r);
	}
	return ans;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>b[i];
	}
	bulid(1,1,n);
	for(int i=0;i<m;i++){
		int op,q,w;
		cin>>op>>q>>w;
		if(op==1){
			
			change(1,q,w);
		}else{
			cout<<cha(1,q,w)<<endl;
		}
	}
	return 0;
}

求助QwQ