萌新の疑问
查看原帖
萌新の疑问
544773
JoeZ009楼主2023/3/1 22:38

为什么这个代码能过:

#include<bits/stdc++.h>
using namespace std;
const int N=8e5+10;
struct Tree{
	int l,r;
	int sum;
	bool lazy;
}tr[N];

int n,m;

void pushup(int u) {
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	return;
} 
void pushdown(int u) {
	if(tr[u].lazy) {
		tr[u<<1].lazy=!tr[u<<1].lazy,tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
		tr[u<<1|1].lazy=!tr[u<<1|1].lazy,tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
		tr[u].lazy=0;
	}
	return;
}

void build(int u,int l,int r) {
	if(l==r)tr[u]={l,r,0,0};
	else {
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
	return;
}

void change(int u,int l,int r) {
	if(l<=tr[u].l&&tr[u].r<=r)tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum,tr[u].lazy=!tr[u].lazy;
	else {
		pushdown(u);
		int mid=tr[u].r+tr[u].l>>1;
		if(l<=mid)change(u<<1,l,r);
		if(r>mid)change(u<<1|1,l,r);
		pushup(u);
	}
	return;
}

int ask(int u,int l,int r) {
	pushdown(u);
	if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
	else {
		int res=0,mid=tr[u].r+tr[u].l>>1;
		if(l<=mid)res+=ask(u<<1,l,r);
		if(r>mid)res+=ask(u<<1|1,l,r);
		return res;
	}
}

int main() {
	cin>>n>>m;
	build(1,1,n);
	while(m--) {
		bool op;
		cin>>op;
		int l,r;
		cin>>l>>r;
		if(op)cout<<ask(1,l,r)<<endl;
		else change(1,l,r);
	}
	return 0;
}

但这个不行:

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
struct Tree{
	int l,r;
	int sum;
	bool lazy;
}tr[N];

int n,m;

void pushup(int u) {
	tr[u].sum=tr[u<<1].sum+tr[u<<1|1].sum;
	return;
} 
void pushdown(int u) {
	if(tr[u].lazy) {
		tr[u<<1].lazy=!tr[u<<1].lazy,tr[u<<1].sum=tr[u<<1].r-tr[u<<1].l+1-tr[u<<1].sum;
		tr[u<<1|1].lazy=!tr[u<<1|1].lazy,tr[u<<1|1].sum=tr[u<<1|1].r-tr[u<<1|1].l+1-tr[u<<1|1].sum;
		tr[u].lazy=0;
	}
	return;
}

void build(int u,int l,int r) {
	if(l==r)tr[u]={l,r,0,0};
	else {
		tr[u]={l,r};
		int mid=l+r>>1;
		build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(u);
	}
	return;
}

void change(int u,int l,int r) {
	if(l<=tr[u].l&&tr[u].r<=r)tr[u].sum=tr[u].r-tr[u].l+1-tr[u].sum,tr[u].lazy=!tr[u].lazy;
	else {
		pushdown(u);
		int mid=tr[u].r+tr[u].l>>1;
		if(l<=mid)change(u<<1,l,r);
		if(r>mid)change(u<<1|1,l,r);
		pushup(u);
	}
	return;
}

int ask(int u,int l,int r) {
	pushdown(u);
	if(l<=tr[u].l&&tr[u].r<=r)return tr[u].sum;
	else {
		int res=0,mid=tr[u].r+tr[u].l>>1;
		if(l<=mid)res+=ask(u<<1,l,r);
		if(r>mid)res+=ask(u<<1|1,l,r);
		return res;
	}
}

int main() {
	cin>>n>>m;
	build(1,1,n);
	while(m--) {
		bool op;
		cin>>op;
		int l,r;
		cin>>l>>r;
		if(op)cout<<ask(1,l,r)<<endl;
		else change(1,l,r);
	}
	return 0;
}

差别只有N的值,AC的是8e5+108e5+10,RE的是4e5+104e5+10

可题目中的n105n≤10^5

线段树开4e54e5不是足够的吗

2023/3/1 22:38
加载中...