P3792保龄求助/kk
  • 板块灌水区
  • 楼主忘怜城羡
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/2/27 20:22
  • 上次更新2024/2/27 22:04:22
查看原帖
P3792保龄求助/kk
374756
忘怜城羡楼主2024/2/27 20:22
#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int MAXN=5e5+7,mod=1e9+7;
int a[MAXN];
struct node{
	int maxe,mine,s2,s3;
	void clear(){
		maxe=s2=s3=0;
		mine=1e9+7;
		return ;
	}
}tree[MAXN<<2];
node query(int p,int l,int r,int x,int y)
{
	if(x<=l&&r<=y)
		return tree[p];
	int mid=(l+r)>>1;
	node ansl,ansr,ans;
	ansl.clear();
	ansr.clear();
	if(x<=mid)
		ansl=query(p*2,l,mid,x,y);
	if(mid<y)
		ansr=query(p*2+1,mid+1,r,x,y);
	ans.maxe=max(ansl.maxe,ansr.maxe);
	ans.mine=min(ansl.mine,ansr.mine);
	ans.s2=(ansl.s2+ansr.s2)%mod;
	ans.s3=(ansl.s3+ansr.s3)%mod;
	return ans;
}
void change(int p,int l,int r,int x,int v)
{
	if(l==r)
	{
		tree[p].maxe=tree[p].mine=v;
		tree[p].s2=v*v%mod;
		tree[p].s3=tree[p].s2*v%mod;
		return ;
	}
	int mid=(l+r)>>1;
	if(x<=mid)
		change(p*2,l,mid,x,v);
	else 
		change(p*2+1,mid+1,r,x,v);
	tree[p].maxe=max(tree[p*2].maxe,tree[p*2+1].maxe);
	tree[p].mine=min(tree[p*2].mine,tree[p*2+1].mine);
	tree[p].s2=(tree[p*2].s2+tree[p*2+1].s2)%mod;
	tree[p].s3=(tree[p*2].s3+tree[p*2+1].s3)%mod;
	return ;
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		tree[p].maxe=tree[p].mine=a[l];
		tree[p].s2=a[l]*a[l]%mod;
		tree[p].s3=tree[p].s2*a[l]%mod;
		return ;
	}
	int mid=(l+r)>>1;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	tree[p].maxe=max(tree[p*2].maxe,tree[p*2+1].maxe);
	tree[p].mine=min(tree[p*2].mine,tree[p*2+1].mine);
	tree[p].s2=(tree[p*2].s2+tree[p*2+1].s2)%mod;
	tree[p].s3=(tree[p*2].s3+tree[p*2+1].s3)%mod;
	return ;
}
int sum2(int n)
{
	return (n+1)*(2*n+1)%mod*n/6;
}
int sum3(int n)
{
	return ((n+1)*n%mod/2)*((n+1)*n%mod/2)%mod;
}
signed main()
{
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i(1);i<=n;++i)
		scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int opt,l,r;
		scanf("%lld%lld%lld",&opt,&l,&r);
		if(opt==1)
			change(1,1,n,l,r);
		else
		{
			node x=query(1,1,n,l,r);
			if(x.maxe-x.mine+1==r-l+1&&(sum2(x.maxe)-sum2(x.mine-1)+mod)%mod==x.s2&&(sum3(x.maxe)-sum3(x.mine-1)+mod)%mod==x.s3)
				printf("damushen\n");
			else
				printf("yuanxing\n");
		}
	}
	return 0;
}
2024/2/27 20:22
加载中...