维护序列

10129

题目描述

维护一个序列，有三个操作：(①)询问([l,r])区间内的所有数的和；(②)把区间([l,r])的数都乘上一个数；(③)把区间([l,r])的数都加上一个数。

思路

这道题就是货真价实的区间修改了。我们用两个(lazy)标记维护修改。对于一个区间([l,r])，乘上一个数相当于它们的和也乘上这个数，加上一个数(x)相当于把和加上((r-l+1)*x),维护这个标记即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct Segment
{
	ll l,r;
	ll sum,lazy1,lazy2;
}T[N<<2];
ll a[N],p;
void pushup(ll k)
{
	T[k].sum=(T[k<<1].sum+T[k<<1|1].sum)%p;
}
void build(ll k,ll l,ll r)
{
	T[k].l=l;T[k].r=r;
	T[k].lazy1=0;T[k].lazy2=1;
	if(l==r)
	{
		T[k].sum=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
	pushup(k);
}
void pushdown(int k)
{
	if(T[k].l==T[k].r)return ;
	if(!T[k].lazy1&&T[k].lazy2==1)return ;
	ll x=T[k].lazy1,y=T[k].lazy2;
	T[k<<1].sum=(T[k<<1].sum*y+x*(T[k<<1].r-T[k<<1].l+1))%p;
	T[k<<1|1].sum=(T[k<<1|1].sum*y+x*(T[k<<1|1].r-T[k<<1|1].l+1))%p;
	T[k<<1].lazy1=(T[k<<1].lazy1*y+x)%p;
	T[k<<1|1].lazy1=(T[k<<1|1].lazy1*y+x)%p;
	T[k<<1].lazy2=(T[k<<1].lazy2*y)%p;
	T[k<<1|1].lazy2=(T[k<<1|1].lazy2*y)%p;
	T[k].lazy1=0;T[k].lazy2=1;
}
void add(ll k,ll l,ll r,ll v)
{
	if(T[k].l==l&&T[k].r==r)
	{
		T[k].sum=(T[k].sum+v*(r-l+1))%p;
		T[k].lazy1=(T[k].lazy1+v)%p;
		return ;
	}
	pushdown(k);
	ll mid=T[k].l+T[k].r>>1;
	if(r<=mid)add(k<<1,l,r,v);
	else if(l>mid)add(k<<1|1,l,r,v);
	else
	{
		add(k<<1,l,mid,v);
		add(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
void multi(ll k,ll l,ll r,ll v)
{
	if(T[k].l==l&&T[k].r==r)
	{
		T[k].sum=(T[k].sum*v)%p;
		T[k].lazy2=(T[k].lazy2*v)%p;
		T[k].lazy1=(T[k].lazy1*v)%p;
		return ;
	}
	pushdown(k);
	ll mid=T[k].l+T[k].r>>1;
	if(r<=mid)multi(k<<1,l,r,v);
	else if(l>mid)multi(k<<1|1,l,r,v);
	else
	{
		multi(k<<1,l,mid,v);
		multi(k<<1|1,mid+1,r,v);
	}
	pushup(k);
}
ll query(ll k,ll l,ll r)
{
	pushdown(k);
	if(T[k].l==l&&T[k].r==r)
		return T[k].sum;
	ll mid=T[k].l+T[k].r>>1;
	if(r<=mid)return query(k<<1,l,r);
	else if(l>mid)return query(k<<1|1,l,r);
	else return (query(k<<1,l,mid)+query(k<<1|1,mid+1,r))%p;
}

ll read()
{
	ll res=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
	return res*w;
}
void write(ll x)
{
	if(x<0){putchar('-');x=-x;}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
void writeln(ll x)
{
	write(x);
	putchar('
');
}

int main() 
{
	ll n=read();p=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	build(1,1,n);
	ll m=read();
	while(m--)
	{
		int op=read();
		if(op==1)
		{
			ll l=read(),r=read(),x=read();
			multi(1,l,r,x);
		}
		else if(op==2)
		{
			ll l=read(),r=read(),x=read();
			add(1,l,r,x);
		}
		else
		{
			ll l=read(),r=read();
			writeln(query(1,l,r));
		}
//		for(int i=1;i<=16;i++)
//			printf("%d %d %d %d
",i,T[i].l,T[i].r,T[i].sum);
	}
	return 0;
}