社区讨论

求助QAQ(玄2关)

P2846[USACO08NOV] Light Switching G参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lyzipg5u
此快照首次捕获于
2024/07/24 15:23
2 年前
此快照最后确认于
2024/07/24 16:09
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
struct Node{
	int js=0,len=0;
	bool bj;
}a[800000];
void New_Tree(int p,int l,int r){
	a[p].len=r-l+1;
	a[p].js=0;
	a[p].bj=0;
	if(a[p].len==1){
		return;
	}
	int mid=l+r>>1;
	New_Tree(p*2+1,mid+1,r);
	New_Tree(p*2,l,mid);
}
void work(int p,int l,int r,int x,int y){
	int mid=l+r>>1;
	if(x<=l&&y>=r){
		a[p].bj=!a[p].bj;
		return;
	}
	if(x>mid){
		work(p*2+1,mid+1,r,x,y);
	}
	else if(y<=mid){
		work(p*2,l,mid,x,y);
	}
	else{
		work(p*2,l,mid,x,y);
		work(p*2+1,mid+1,r,x,y);
	}
}
void push_down(int p){
	a[2*p].bj=!a[2*p].bj;
	a[2*p+1].bj=!a[2*p+1].bj;
}
void push_up(int p){
	if(a[2*p].bj){
		a[2*p].bj=!a[2*p].bj;
		a[2*p].js=a[2*p].len-a[2*p].js;
		push_down(2*p);
	}
	if(a[2*p+1].bj){
		a[2*p+1].bj=!a[2*p+1].bj;
		a[2*p+1].js=a[2*p+1].len-a[2*p+1].js;
		push_down(2*p+1);
	}
	if(a[p].len>1){
		a[p].js=a[2*p].js+a[2*p+1].js;
	}
}
int ans(int p,int l,int r,int x,int y){
	if(a[p].bj){
		a[p].bj=!a[p].bj;
		a[p].js=a[p].len-a[p].js;
		push_down(p);
	}
	if(x<=l&&y>=r){
		return a[p].js;
	}
	int mid=l+r>>1;
	if(x>mid){
		return ans(p*2+1,mid+1,r,x,y);
	}
	else if(y<=mid){
		return ans(p*2,l,mid,x,y);  
	}
	else{
		return ans(p*2,l,mid,x,y)+ans(p*2+1,mid+1,r,x,y);
	}
	push_up(p);
}
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	New_Tree(1,1,n);
	for(int i=1;i<=m;i++){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(op==0){
			work(1,1,n,x,y);
		}
		else{
			printf("%d\n",ans(1,1,n,x,y));
		}
	}
	return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...