社区讨论

为什么线段树暴力区间修改能过,暴力区间查询不能过

P4145上帝造题的七分钟 2 / 花神游历各国参与者 4已保存回复 5

讨论操作

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

当前回复
5 条
当前快照
1 份
快照标识符
@mhjcue2h
此快照首次捕获于
2025/11/04 00:29
4 个月前
此快照最后确认于
2025/11/04 00:29
4 个月前
查看原帖
#11 TLE
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M=100009;
ll n,m,a[M],k,l,r;
struct SegmentTree{
	ll l,r,add,cnt;
} t[4*M];
void build(ll p,ll l,ll r){
	t[p].l=l,t[p].r=r;
	if(l==r) return;
	ll mid=(l+r)>>1;
	build(p<<1,l,mid);
	build((p<<1)|1,mid+1,r);
}
void spread(ll p){
	if(t[p].add!=0){
		t[p<<1].add+=t[p].add; t[(p<<1)|1].add+=t[p].add;
		t[p<<1].cnt+=t[p].add; t[(p<<1)|1].cnt+=t[p].add;
		t[p].add=0;
	}
}
void change(ll p,ll l,ll r){
	if(t[p].l>=l&&t[p].r<=r){
		t[p].add++; t[p].cnt++; return;
	}
	if(t[p].cnt>=6) return;
	spread(p);
	ll mid=(t[p].l+t[p].r)>>1;
	if(l<=mid) change(p<<1,l,r);
	if(r>mid) change((p<<1)|1,l,r);
}
ll ask(ll p,ll l,ll r){
	if(t[p].l>=l&&t[p].r<=r){
		if(t[p].cnt>=6) return t[p].r-t[p].l+1;
		if(t[p].l==t[p].r){
			while(t[p].add>0) a[t[p].l]=sqrt(a[t[p].l]),t[p].add--;
			return a[t[p].l];
		}
		spread(p);
		ll mid=(t[p].l+t[p].r)>>1;
		return ask(p<<1,l,r)+ask((p<<1)|1,l,r);
	}
	spread(p);
	ll mid=(t[p].l+t[p].r)>>1,val=0;
	if(l<=mid) val+=ask(p<<1,l,r);
	if(r>mid) val+=ask((p<<1)|1,l,r);
	return val;
}
int main(){
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	scanf("%lld",&m);
	while(m--){
		scanf("%lld%lld%lld",&k,&l,&r); if(l>r) swap(l,r);
		if(!k) change(1,l,r);
		else printf("%lld\n",ask(1,l,r));
	}
	return 0;
}

回复

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

正在加载回复...