AC后的疑问
查看原帖
AC后的疑问
546542
wylnh楼主2024/1/6 20:24

蒟蒻求助:第25行为啥 modify 退出条件是 sg[u].l==sg[u].r ?

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+10;
ll n,p,m,a[N];
struct Segment{
	ll l,r,v,sq;
}sg[N<<2];
void pushup(ll u){
	sg[u].v=sg[u<<1].v+sg[u<<1|1].v;
	sg[u].sq=max(sg[u<<1].sq,sg[u<<1|1].sq);
}
void build(ll u,ll l,ll r){
	sg[u]={l,r,0,0};
	if(l==r){
		sg[u].v=sg[u].sq=a[l];
		return;
	}
	ll mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(ll u,ll l,ll r){
	if(sg[u].l==sg[u].r){//就是这里
		sg[u].sq=sqrt(sg[u].sq);
		sg[u].v=sqrt(sg[u].v);
		return;
	}
	ll mid=sg[u].l+sg[u].r>>1;
	if(l<=mid&&sg[u<<1].sq>1)
		modify(u<<1,l,r);
	if(r>mid&&sg[u<<1|1].sq>1)
		modify(u<<1|1,l,r);
	pushup(u);
}
ll query(ll u,ll l,ll r){
	if(sg[u].l>=l&&sg[u].r<=r)
		return sg[u].v;
	ll mid=sg[u].l+sg[u].r>>1;
	ll ans=0;
	if(l<=mid)
		ans+=query(u<<1,l,r);
	if(r>mid)
		ans+=query(u<<1|1,l,r);
	return ans;
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
    }
	build(1,1,n);
	cin>>m;
	ll k,l,r;
	while(m--){
		cin>>k>>l>>r;
		if(l>r)
			swap(l,r);
		if(k==0)
			modify(1,l,r);
		else
			cout<<query(1,l,r)<<"\n";
	}
	
	return 0;
}
2024/1/6 20:24
加载中...