求助!或许这就是线段树的极限了吧
查看原帖
求助!或许这就是线段树的极限了吧
130104
loris楼主2021/7/3 11:45

蒟蒻打的线段树,T了3个。这都无所谓,但是为什么最后5个点wa了,切都是too short on line one,求助。

#include<bits/stdc++.h>
using namespace std;
const int MM=400005;
int t[MM],mx[MM],a[MM],n,m,q,x,y;
void pushup(int now)
{
	t[now]=t[now<<1]+t[now<<1|1];
	mx[now]=max(t[now<<1],t[now<<1|1]);
}
int buildt(int now,int l,int r)
{
	if(l==r)
		return t[now]=a[l];
	else
		return t[now]=buildt(now<<1,l,(l+r)>>1)+buildt(now<<1|1,((l+r)>>1)+1,r);
}
int buildmx(int now,int l,int r)
{
	if(l==r)
		return mx[now]=a[l];
	else
		return mx[now]=max(buildmx(now<<1,l,(l+r)>>1),buildmx(now<<1|1,((l+r)>>1)+1,r)); 
}
int getmx(int now,int l,int r,int L,int R)
{
	if(l==r)
		return mx[now];
	if(L<=l&&r<=R)
		return mx[now];
	int mid=(l+r)>>1,tmp=-1;	
	if(L<=mid)
		tmp=max(tmp,getmx(now<<1,l,mid,L,R));
	if(R>mid)
		tmp=max(tmp,getmx(now<<1|1,mid+1,r,L,R));
	return tmp;
} 
void _sqrt(int now,int l,int r,int aim)
{
	if(l==r&&l==aim)
	{
		t[now]=sqrt(t[now]);
		mx[now]=sqrt(mx[now]);
		return;
	}
	int mid=(l+r)>>1;
	if(aim<=mid)
		_sqrt(now<<1,l,mid,aim);
	else
		_sqrt(now<<1|1,mid+1,r,aim);
	pushup(now);
}
int ask(int now,int l,int r,int L,int R)
{
	if(l==r)
		return t[now];
	if(L<=l&&r<=R)
		return t[now];
	int mid=(l+r)>>1;
	int tmp=0;
	if(L<=mid)
		tmp+=ask(now<<1,l,mid,L,R);
	if(R>mid)
		tmp+=ask(now<<1|1,mid+1,r,L,R);
	return tmp;
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	cin>>m;
	buildt(1,1,n);
	buildmx(1,1,n);
	for(int i=1;i<=m;i++)
	{
		cin>>q>>x>>y;
		if(x>y)
			swap(x,y);
		if(q==0)
			if(getmx(1,1,n,x,y)>1)
				for(int i=x;i<=y;i++)
				{
					a[i]=sqrt(a[i]);
					 _sqrt(1,1,n,i);
				}
		if(q==1)
			cout<<ask(1,1,n,x,y)<<endl;
	}
	return 0;
}
2021/7/3 11:45
加载中...