刚学OI,线段树小问题
查看原帖
刚学OI,线段树小问题
1003136
aimoyudexianyu楼主2024/8/7 11:25

线段树按照题目数据范围开2e5+5会RE 开到3e5+5不会爆RE 学习了题解第一篇,题解第一篇代码开到2e5+5也会爆RE,大佬们帮看下哪里爆了,代码如下

#include<bits/stdc++.h>
#define ll int
#define rep(i,a,b) for(int i = a; i <= b; i++)
using namespace std;
inline void read(ll &a) {
	ll x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	a = x*f;
}
#define ls (k<<1)
#define rs ((k<<1)|1)
#define mid ((l+r)>>1)
ll n, m, a[200005];
ll tree[800005], tag[800005];
void push_up(ll k) {
	tree[k]=tree[ls]+tree[rs];
	return;
}
void push_down(ll k, ll len) {
	if(!tag[k]) return;
	tag[ls]^=1;
	tag[rs]^=1;
	tree[ls]=(len-(len>>1))-tree[ls];
	tree[rs]=(len>>1)-tree[rs];
	tag[k]=0;
	return;
}
void build(ll k, ll l, ll r) {
	if(l==r) {
		tree[k]=a[l];
		return;
	}
	build(ls, l, mid);
	build(rs, mid+1, r);
	push_up(k);
	return;
}
void change(ll k, ll l, ll r, ll tl, ll tr) {
	push_down(k, r-l+1);
	if(l>=tl&&r<=tr) {
		tag[k]^=1;
		tree[k]=r-l+1-tree[k];
		return;
	}
	if(tl<=mid) change(ls, l, mid, tl, tr);
	if(tr>mid) change(rs, mid+1, r, tl, tr);
	push_up(k);
	return;
}
ll ask(ll k, ll l, ll r, ll tl, ll tr) {
	if(l>=tl&&r<=tr) {
		return tree[k];
	}
	push_down(k, r-l+1);
	ll ans=0;
	if(tl<=mid) ans+=ask(ls, l, mid, tl, tr);
	if(tr>mid) ans+=ask(rs, mid+1, r, tl, tr);
	return ans;
}
int main() {
	cin >> n >> m;
	rep(i,1,n) scanf("%1lld",&a[i]);
	build(1,1,n);
	ll op, l, r;
	rep(i,1,m) {
		read(op), read(l), read(r);
		if(op==0) {
			change(1,1,n,l,r);
		} else {
			printf("%lld\n", ask(1,1,n,l,r));
		}
	}
	return 0;
}

感激不尽!!!

2024/8/7 11:25
加载中...