大家来找茬
查看原帖
大家来找茬
234582
zpl__hhd楼主2021/2/10 12:13
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int maxn=500010;
int n,m;
ll ans;
int ans1,ans2;
struct tree
{
	int w,l,r,ma,mi;
	ll p;
}t[maxn<<2];
inline void build(int k,int ll,int rr)
{
	t[k].l=ll;
	t[k].r=rr;
	if(ll==rr)
	{
		scanf("%d",&t[k].w);
		t[k].ma=t[k].w;
		t[k].mi=t[k].w;
		t[k].p=t[k].w*t[k].w;
		return ;
	}
	int mid=(ll+rr)>>1;
	build(k<<1,ll,mid);
	build(k<<1|1,mid+1,rr);
	t[k].w=t[k<<1].w+t[k<<1|1].w;
	t[k].p=t[k<<1].p+t[k<<1|1].p;
	t[k].mi=min(t[k<<1].mi,t[k<<1|1].mi);
	t[k].ma=max(t[k<<1].ma,t[k<<1|1].ma);
}
inline void add(int k,int x,int y)
{
	if(t[k].l==t[k].r)
	{
		t[k].w=y;
		t[k].mi=y;
		t[k].ma=y;
		t[k].p=y*y;
		return ;
	}
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=x)add(k<<1,x,y);
	else add(k<<1|1,x,y);
	t[k].w=t[k<<1].w+t[k<<1|1].w;
	t[k].p=t[k<<1].p+t[k<<1|1].p;
	t[k].mi=min(t[k<<1].mi,t[k<<1|1].mi);
	t[k].ma=max(t[k<<1].ma,t[k<<1|1].ma);
}
inline void check(int k,int a,int b)
{
	if(t[k].l>=a&&t[k].r<=b)
	{
		ans+=t[k].p;
		ans1=max(ans1,t[k].ma);
		ans2=min(ans2,t[k].mi);
		//cout<<"查询到:左右端点:"<<t[k].l<<" "<<t[k].r<<"最大"<<ans1<<"	最小"<<ans2<<endl;
		return;
	}
	int mid=(t[k].l+t[k].r)>>1;
	if(mid>=a)check(k<<1,a,b);
	if(mid<b)check(k<<1|1,a,b);
}
ll pfh(ll x)
{
	return x*(x+1)*(2*x+1);
}
int main()
{
	freopen("hh.in","r",stdin);
	freopen("hh.out","w",stdout);
	scanf("%d%d",&n,&m);
	build(1,1,n);	
	for(int i=1;i<=m;i++)
	{
		int g,a,b;
		scanf("%d%d%d",&g,&a,&b);
		if(g==1)
		add(1,a,b);
		else
		{
			ans=0;
			ans1=-2000000000;
			ans2=2000000000;
			check(1,a,b);
			ll k=pfh(ans1)-pfh(ans2-1);
			//cout<<ans<<"	"<<k<<"	"<<ans1-ans2<<"	"<<b-a<<"	";
			if((ans1-ans2+1)==(b-a+1)&&k*6==ans)
			cout<<"damushen"<<endl;
			else cout<<"yuanxing"<<endl;
		}
	}
}
2021/2/10 12:13
加载中...