保龄求调
查看原帖
保龄求调
374756
忘怜城羡楼主2024/2/27 21:55
#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,sum;
	void clear(){
		maxe=s2=s3=sum=0;
		mine=1e9+7;
		return ;
	}
}tree[MAXN<<3];
void update(int p)
{
	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].sum=(tree[p*2].sum+tree[p*2+1].sum)%mod;
	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;
}
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;
	ans.sum=(ansl.sum+ansr.sum)%mod;
	return ans;
}
void change(int p,int l,int r,int x,int v)
{
	if(l==r)
	{
		tree[p].maxe=tree[p].mine=tree[p].sum=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);
	update(p);
	return ;
}
void build(int p,int l,int r)
{
	if(l==r)
	{
		tree[p].maxe=tree[p].mine=tree[p].sum=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);
	update(p);
	return ;
}
int sum2(int n)
{
	return n*(n+1)%mod/2*(2*n+1)%mod/3;
}
int sum3(int n)
{
	return n*(n+1)%mod/2*n%mod*(n+1)%mod/2%mod;
}
signed main()
{
	freopen("P3792.in","r",stdin);
	freopen("P3792.out","w",stdout);
	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&&(sum3(x.maxe)-sum3(x.mine-1)+mod)%mod==x.s3&&(x.maxe-x.mine+1)*(x.mine+x.maxe)/2%mod==x.sum)
				printf("damushen\n");
			else
				printf("yuanxing\n");
		}
	}
	return 0;
}
2024/2/27 21:55
加载中...