就30分啊,有dalao帮忙吗
查看原帖
就30分啊,有dalao帮忙吗
506524
wangzll楼主2022/11/23 13:39
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=1e5+10;
ll n,m,p,ch,x,y,t;
ll a[maxn],tree[maxn<<2];
struct node
{
	ll add,mul;
}lazy[maxn<<2];
void build(ll l,ll r,ll k)
{
	lazy[k].add=0,lazy[k].mul=1;
	if(l==r)
	{
		tree[k]=a[l]%p;
	}
	else
	{
		ll m=l+((r-l)>>1);
		build(l,m,k<<1);
		build(m+1,r,k<<1|1);
		tree[k]=(tree[k<<1]%p+tree[k<<1|1]%p)%p;
		//cout<<k<<" "<<tree[k]<<endl;
	}
}
void pushdown(ll l,ll r,ll k)
{
	ll m=l+((r-l)>>1);
	tree[k<<1]*=lazy[k].mul%p,tree[k<<1]%=p;
	tree[k<<1|1]*=lazy[k].mul%p,tree[k<<1|1]%=p;
	tree[k<<1]+=lazy[k].add%p*(m-l+1)%p,tree[k<<1]%=p;
	tree[k<<1|1]+=lazy[k].add%p*(r-m)%p,tree[k<<1|1]%=p; 
	lazy[k<<1].add+=lazy[k].add%p,lazy[k<<1].add%=p;
	lazy[k<<1|1].add+=lazy[k].add%p,lazy[k<<1|1].add%=p;
	lazy[k<<1].mul*=lazy[k].mul%p,lazy[k<<1].mul%=p;
	lazy[k<<1|1].mul*=lazy[k].mul%p,lazy[k<<1|1].mul%=p;
	lazy[k].add=0,lazy[k].mul=1;
}
void updata_mul(ll l,ll r,ll L,ll R,ll k,ll t)      
{
	if(L<=l&&r<=R)
	{
		tree[k]*=t%p,tree[k]%=p;
		lazy[k].mul*=t%p,lazy[k].mul%=p;
		lazy[k].add*=t%p,lazy[k].mul%=p;
	}
	else
	{
		pushdown(l,r,k);
		ll m=l+((r-l)>>1);
		if(L<=m)
		{
			updata_mul(l,m,L,R,k<<1,t);
		}
		if(R>m)
		{
			updata_mul(m+1,r,L,R,k<<1|1,t);
		}
		tree[k]=(tree[k<<1]%p+tree[k<<1|1]%p)%p;
	}
}
void updata_add(ll l,ll r,ll L,ll R,ll k,ll t)
{
	if(L<=l&&r<=R)
	{
		tree[k]+=t%p*(r-l+1)%p,tree[k]%=p;
		lazy[k].add+=t%p,lazy[k].add%=p;
	}
	else
	{
		pushdown(l,r,k);
		ll m=l+((r-l)>>1);
		if(L<=m)
		{
			updata_add(l,m,L,R,k<<1,t);
		}
		if(R>m)
		{
			updata_add(m+1,r,L,R,k<<1|1,t);
		}
		tree[k]=(tree[k<<1]%p+tree[k<<1|1]%p)%p;
	}
}

ll query(ll l,ll r,ll L,ll R,ll k)
{
	//cout<<k<<endl;
	if(L<=l&&r<=R)
	{
		//cout<<114514<<endl;
		return tree[k]%=p;
	}
	else
	{
		//cout<<1919810<<endl;
		//cout<<lazy[k].add<<" "<<lazy[k].mul<<endl;
		//cout<<(k<<1)<<" "<<(k<<1|1)<<endl;
		//cout<<tree[k<<1]<<" "<<tree[k<<1|1]<<endl;
		pushdown(l,r,k);
		//cout<<tree[k<<1]<<" "<<tree[k<<1|1]<<endl;
		ll m=l+((r-l)>>1);
		ll ans=0;
		if(L<=m)
		{
			ans+=query(l,m,L,R,k<<1);
			ans%=p;
		}
		if(R>m)
		{
			ans+=query(m+1,r,L,R,k<<1|1);
			ans%=p;
		}
		return ans%p;
	}
}
int main()
{
	scanf("%lld%lld%lld",&n,&m,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	} 
	build(1,n,1);
//	for(int i=1;i<=15;i++)
//	{
//		cout<<tree[i]<<" ";
//	}
//	cout<<endl;
	for(int i=1;i<=m;i++)
	{
		scanf("%lld%lld%lld",&ch,&x,&y);
		if(ch==1)
		{
			scanf("%lld",&t);
			updata_mul(1,n,x,y,1,t);
		}
		else if(ch==2)
		{
			scanf("%lld",&t);
			updata_add(1,n,x,y,1,t);
		}
		else
		{
			printf("%lld\n",query(1,n,x,y,1));
		}
//		cout<<endl;
//		for(int i=1;i<=15;i++)
//		{
//			cout<<tree[i]<<" ";
//		}
//		cout<<endl;
	}
	return 0;
}
2022/11/23 13:39
加载中...