BZOJ-1798/5039: [Ahoi2009]Seq 维护序列seq

老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。 有长为N的数列，不妨设为a1,a2,…,aN 。有如下三种操作形式： (1)把数列中的一段数全部乘一个值; (2)把数列中的一段数全部加一个值; (3)询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。n<=100000线段树码农题。好久没写线段树这么恶心的题，感觉都不适应了。。。噩梦啊。

先乘后加，一开始没统计siz，直接往sum里加权值。。。我好菜啊。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 401000
typedef long long ll;
int n,m,t,g,c,sw;
ll mod;
int w[101000];
struct seg
{
	int sum[N],lz_ad[N],lz_cn[N],siz[N];
	void pushup(int pos)
	{
		sum[pos]=(sum[pos<<1]+sum[pos<<1|1])%mod;
	}
	void pushdown(int pos)
	{
		if(lz_cn[pos]!=1)
		{
			sum[pos<<1]=1ll*sum[pos<<1]*lz_cn[pos]%mod;
			sum[pos<<1|1]=1ll*sum[pos<<1|1]*lz_cn[pos]%mod;
			lz_cn[pos<<1]=1ll*lz_cn[pos<<1]*lz_cn[pos]%mod;
			lz_cn[pos<<1|1]=1ll*lz_cn[pos<<1|1]*lz_cn[pos]%mod;
			lz_ad[pos<<1]=1ll*lz_ad[pos<<1]*lz_cn[pos]%mod;
			lz_ad[pos<<1|1]=1ll*lz_ad[pos<<1|1]*lz_cn[pos]%mod;
			lz_cn[pos]=1;
		}
		if(lz_ad[pos])
		{
			sum[pos<<1]=(sum[pos<<1]+1ll*lz_ad[pos]*siz[pos<<1]%mod)%mod;
			sum[pos<<1|1]=(sum[pos<<1|1]+1ll*lz_ad[pos]*siz[pos<<1|1])%mod;
			lz_ad[pos<<1]=(lz_ad[pos<<1]+lz_ad[pos])%mod;
			lz_ad[pos<<1|1]=(lz_ad[pos<<1|1]+lz_ad[pos])%mod;
			lz_ad[pos]=0;
		}
	}
	void build(int pos,int l,int r)
	{
		lz_cn[pos]=1;
		if(l==r) {sum[pos]=w[l];siz[pos]=1;return ;}
		int mid=l+r>>1;
		build(pos<<1,l,mid);
		build(pos<<1|1,mid+1,r);
		pushup(pos);
		siz[pos]=siz[pos<<1]+siz[pos<<1|1];
	}
	void fix_ch(int pos,int l,int r,int x,int y,int val)
	{
		if(x<=l&&y>=r)
		{
			lz_cn[pos]=1ll*lz_cn[pos]*val%mod;
			lz_ad[pos]=1ll*lz_ad[pos]*val%mod;
			sum[pos]=1ll*sum[pos]*val%mod;
			return ;
		}
		pushdown(pos);
		int mid=l+r>>1;
		if(y<=mid) fix_ch(pos<<1,l,mid,x,y,val);
		else if(x>mid) fix_ch(pos<<1|1,mid+1,r,x,y,val);
		else fix_ch(pos<<1,l,mid,x,y,val),fix_ch(pos<<1|1,mid+1,r,x,y,val);
		pushup(pos);
	}
	void fix_ja(int pos,int l,int r,int x,int y,int val)
	{
		if(x<=l&&y>=r)
		{
			lz_ad[pos]=(lz_ad[pos]+val)%mod;
			sum[pos]=(sum[pos]+1ll*val*siz[pos]%mod)%mod;
			return ;
		}
		pushdown(pos);
		int mid=l+r>>1;
		if(y<=mid) fix_ja(pos<<1,l,mid,x,y,val);
		else if(x>mid) fix_ja(pos<<1|1,mid+1,r,x,y,val);
		else fix_ja(pos<<1,l,mid,x,y,val),fix_ja(pos<<1|1,mid+1,r,x,y,val);
		pushup(pos);
	}
	int query(int pos,int l,int r,int x,int y)
	{
		if(x<=l&&y>=r) return sum[pos];
		pushdown(pos);
		int mid=l+r>>1;
		if(y<=mid) return query(pos<<1,l,mid,x,y);
		else if(x>mid) return query(pos<<1|1,mid+1,r,x,y);
		else return (query(pos<<1,l,mid,x,y)+query(pos<<1|1,mid+1,r,x,y))%mod;
	}
}T;
int main()
{
	scanf("%d%lld",&n,&mod);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	T.build(1,1,n);
	scanf("%d",&m);
	while(m--)
	{
		scanf("%d",&sw);
		switch(sw)
		{
			case 1:
			{
				scanf("%d%d%d",&t,&g,&c);
				T.fix_ch(1,1,n,t,g,c);
				break;
			}
			case 2:
			{
				scanf("%d%d%d",&t,&g,&c);
				T.fix_ja(1,1,n,t,g,c);
				break;
			}
			case 3:
			{
				scanf("%d%d",&t,&g);
				printf("%d\n",T.query(1,1,n,t,g));
				break;
			}
		}
	}
	return 0;
}