线段树 十分 求调 悬关
查看原帖
线段树 十分 求调 悬关
901471
five_rice_water楼主2024/8/7 10:52
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5+5;
int n,m,tree[N<<2],tag[N<<2];
void pushup(int rt){
	tree[rt]=tree[rt<<1]+tree[rt<<1|1];
}
void pushdown(int l,int r,int rt){
	if(tag[rt]%2==1){
		tag[rt<<1]+=tag[rt];
		tag[rt<<1|1]+=tag[rt];
		tag[rt<<1]%=2;
		tag[rt<<1|1]%=2;
		int mid = (l+r)>>1;
		if(tag[rt<<1])tree[rt<<1]=(mid-l+1)-tree[rt<<1];
		if(tag[rt<<1|1])tree[rt<<1|1]=(r-mid)-tree[rt<<1|1];
		tag[rt]=0;
	}
}
void update(int l,int r,int rt,int L,int R){
	if(L<=l&&r<=R){
		tree[rt]=(r-l+1)-tree[rt];
		tag[rt]++;
		tag[rt]%=2;
		return;
	}
	pushdown(l,r,rt);
	int mid = (l+r)>>1;
	if(L<=mid) update(l,mid,rt<<1,L,R);
	if(mid<R) update(mid+1,r,rt<<1|1,L,R);
	pushup(rt);
}
int query(int l,int r,int rt,int L,int R){
	if(L<=l&&r<=R) return tree[rt];
	pushdown(l,r,rt);
	int mid = (l+r)>>1;
	int sum = 0;
	if(L<=mid) sum+=query(l,mid,rt<<1,L,R);
	if(mid<R) sum+=query(mid+1,r,rt<<1|1,L,R);
	return sum;
}
signed main(){
	cin>>n>>m;
	while(m--){
		int x,y,z;
		cin>>x>>y>>z;
		if(x==0) {
			update(1,n,1,y,z);
		}		
		else{
			cout<<query(1,n,1,y,z)<<endl;
		}
//		for(int i = 1; i<=(n<<2); i++){
//			cout<<tree[i]<<" ";
//		} 
//		cout<<endl;
//		for(int i = 1; i<=(n<<2); i++){
//			cout<<tag[i]<<" ";
//		}
//		cout<<"---------\n";
	}
	return 0;
}

我感觉没问题啊 调了几遍还是10分 只对了第二个点

2024/8/7 10:52
加载中...