萌新初学线段树,代码求调
查看原帖
萌新初学线段树,代码求调
421265
eastcloud楼主2022/5/3 22:14
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
struct Node{
	int l,r,val,add;
}tree[400040];
void se(int l,int r,int num){
	tree[num].l=l;
	tree[num].r=r;
	if(l!=r){
		int mid=(l+r)/2;
		se(l,mid,2*num);
		se(mid+1,r,2*num+1);
	}
}
void push_down(int num){
	if(tree[num].add){
		if(tree[num*2].add==0)tree[num*2].add=1;
		else tree[num*2].add=0;
		if(tree[num*2+1].add==0)tree[num*2+1].add=1;
		else tree[num*2+1].add=0;
		tree[num*2].val=(tree[num*2].r-tree[num*2].l+1)-tree[num*2].val;
		tree[num*2+1].add=(tree[num*2+1].r-tree[num*2+1].l+1)-tree[num*2+1].val;
		tree[num].add=0;
	}
}
void chan(int l,int r,int num){
	if(tree[num].l>=l && tree[num].r<=r){
		tree[num].val=(tree[num].r-tree[num].l+1)-tree[num].val;
		if(tree[num].add==0)tree[num].add=1;
		else tree[num].add=0;
		return;
	}
	push_down(num);
	int mid=(tree[num].l+tree[num].r)/2;
	if(l<=mid) chan(l,r,num*2);
	if(r>mid) chan(l,r,num*2+1);
	tree[num].val=tree[2*num].val+tree[num*2+1].val;
}
int ask(int l,int r,int num){
	if(tree[num].l>=l && tree[num].r<=r)return tree[num].val;
	int tot=0;
	push_down(num);
	int mid=(tree[num].l+tree[num].r)/2;
	if(l<=mid)tot+=ask(l,r,num*2);
	if(r>mid)tot+=ask(l,r,num*2+1);
	return tot;
}
int main(){
	int n,m,x,l,r;
	cin>>n>>m;
	se(1,n,1);
	for(int i=1;i<=m;i++){
		cin>>x>>l>>r;
		if(x==0) chan(l,r,1);
		else cout<<ask(l,r,1)<<endl;
	}
    return 0;
}

样例输出 2 1

2022/5/3 22:14
加载中...