求助大佬,样例没过还超空间,题解怎么看也看不对
查看原帖
求助大佬,样例没过还超空间,题解怎么看也看不对
748250
haoguhao楼主2023/1/11 19:20
#include<bits/stdc++.h>
using namespace std;
int n,m,opt,x,y;
const int MAXN=100003;
struct node{
	int l,r,add,sum;
	inline int len() {	return r-l+1;	} 
	inline int mid() {	return (l+r)>>1;}
}ans[MAXN*4];
inline int ls(int x){return x<<1;}
inline int rs(int x){x<<1|1;}
void push_up(int p){ans[p].sum+=ans[ls(p)].sum+ans[rs(p)].sum;}
void build(int p,int l,int r){
	ans[p].l=l;ans[p].r=r;ans[p].add=0;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r);
//	push_up(p);
}
void push_down(int p){
	if(ans[p].add==1){
		ans[ls(p)].add^=1;
		ans[rs(p)].add^=1;
		ans[ls(p)].sum=ans[ls(p)].len()-ans[ls(p)].sum;
		ans[rs(p)].sum=ans[rs(p)].len()-ans[rs(p)].sum;
		ans[p].add=0;
	}
}
void update(int l,int r,int p){
	if(l<=ans[p].l && ans[p].r<=r){
		ans[p].sum=ans[p].len()-ans[p].sum;
		ans[p].add^=1;
		return;
	}
	push_down(p);
	int mid=ans[p].mid();
	if(l<=mid) update(l,r,ls(p));
	if(r>mid) update(l,r,rs(p));
	push_up(p);
}
int query(int l,int r,int p){
	if(l<=ans[p].l && ans[p].r<=r) return ans[p].sum;
	push_down(p);
	int res=0;
	int mid=ans[p].mid();
	if(l<=mid) res+=query(l,r,ls(p));
	if(r>mid) res+=query(l,r,rs(p));
	return res;
} 
int main(){
	scanf("%d%d",&n,&m);
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%d",&opt);
		if(opt==0){
			scanf("%d%d",&x,&y);
			update(x,y,1);
		}
		else{
			scanf("%d%d",&x,&y);
			cout<<query(x,y,1)+1<<endl;
		}
	}
}
2023/1/11 19:20
加载中...