飞舞题目

http://222.203.110.13/d/ybttg/p/P3373/solution

前言

这个题解和上一个人的一样，只不过由于想看他的题解，需要点击一次鼠标.
一个鼠标可以点击约200w下，所以，如果用上一个人的题解，就会损失鼠标$\frac {1} {2000000}$的寿命，这真是太可怕了！！！
所以，我们可以直接把题解搬过来，这样，想看题解的人就可以节省$\frac {1} {2000000}$的鼠标寿命。如果一个鼠标要20元，那么看这个题解相比于上一个人发的题解可以省整整

元钱！
为了给学校省钱，我帮大家把题解直接搬到了这里(真是一个发题解的好理由)

题解

这题跟线段树2 的代码基本一样。

思路

为了实现区间乘法，我们需要为乘法也准备一个懒标记，记录区间需要乘的数。注意：在区间乘新的值时要把加法标记也乘了，所以需要先乘后加

呆码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node{
	int l,r;
	ll num;
}tree[1000001];
ll a[1000001]={},n,tag[1000001],times[1000001],MOD;
void createTree(ll sp,ll l,ll r){
	tree[sp].l=l;
	tree[sp].r=r;
	times[sp]=1;
	if(l==r){
		tree[sp].num=a[l]%MOD;
		return;
	}
	ll mid=(l+r)>>1;
	createTree(sp<<1,l,mid);
	createTree((sp<<1)+1,mid+1,r);
	tree[sp].num=(tree[sp<<1].num+tree[(sp<<1)+1].num)%MOD;
}
void cltts(ll sp){
	//times的内容说明，此位置所有的数都要乘。
	tree[sp<<1].num=ll(tree[sp<<1].num*times[sp]+(tag[sp]*(tree[sp<<1].r-tree[sp<<1].l+1))%MOD)%MOD;
	tree[(sp<<1)+1].num=ll(tree[(sp<<1)+1].num*times[sp]+(tag[sp]*(tree[(sp<<1)+1].r-tree[(sp<<1)+1].l+1))%MOD)%MOD;
	
	times[sp<<1]=ll(times[sp<<1]*times[sp])%MOD;
	times[(sp<<1)+1]=ll(times[(sp<<1)+1]*times[sp])%MOD;
	//先乘后加，不然新加的、不需要乘的数也会被乘到的
	
	tag[sp<<1]=ll(tag[sp<<1]*times[sp]+tag[sp])%MOD;
	tag[(sp<<1)+1]=ll(tag[(sp<<1)+1]*times[sp]+tag[sp])%MOD;
	
	tag[sp]=0;
	times[sp]=1;
}
void pointChange(ll sp,ll pt,ll nn){
	if(tree[sp].l==tree[sp].r){
		tree[sp].num=ll(tree[sp].num+nn)%MOD;
		return;
	}
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(pt<=mid)pointChange(sp<<1,pt,nn);
	else pointChange((sp<<1)+1,pt,nn);
	tree[sp].num=(tree[sp<<1].num+tree[(sp<<1)+1].num)%MOD;
}
void areaChange1(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag[sp]=(tag[sp]+c)%MOD;
		tree[sp].num=ll(tree[sp].num+(tree[sp].r-tree[sp].l+1)*c)%MOD;
		return;
	}
	cltts(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	if(l<=mid){
		areaChange1(sp<<1,l,r,c);
	}
	if(mid<r){
		areaChange1((sp<<1)+1,l,r,c);
	}
	tree[sp].num=(tree[sp<<1].num+tree[(sp<<1)+1].num)%MOD;
}
void areaChange2(ll sp,ll l,ll r,ll c){
	if(tree[sp].l>=l&&tree[sp].r<=r){
		tag[sp]=(tag[sp]*c)%MOD;
		times[sp]=(times[sp]*c)%MOD;
		tree[sp].num=(tree[sp].num*c)%MOD;
		return;
	}
	cltts(sp);
	tree[sp].num=(tree[sp<<1].num+tree[(sp<<1)+1].num);
	ll mid=(tree[sp].l+tree[sp].r)>>1;
	tree[sp].num=(tree[sp<<1].num+tree[(sp<<1)+1].num);
	if(l<=mid){
		areaChange2(sp<<1,l,r,c);
	}
	if(mid<r){
		areaChange2((sp<<1)+1,l,r,c);
	}
	tree[sp].num=(tree[sp<<1].num+tree[(sp<<1)+1].num)%MOD;
}
ll areaAsk(ll sp,ll l,ll r){
	if(tree[sp].l>=l&&tree[sp].r<=r)return tree[sp].num;
	cltts(sp);
	ll mid=(tree[sp].l+tree[sp].r)>>1,maxn=0;
	if(l<=mid){
		maxn=(maxn+areaAsk(sp<<1,l,r))%MOD;
	}
	if(mid<r){
		maxn=(maxn+areaAsk((sp<<1)+1,l,r))%MOD;
	}
	return maxn;
}
int main(){
//	freopen("in.in","r",stdin);
//	freopen("out.out","w",stdout);
	ll T;
	
	cin>>n>>MOD;
	for(ll i=1;i<=n;i++)cin>>a[i];
    cin>>T;
	createTree(1,1,n);
	for(ll i=1;i<=T;i++){
		ll c,x,y;
		cin>>c>>x>>y;
		if(c==1){
			ll k;
			cin>>k;
			areaChange2(1,x,y,k);
		}
		else if(c==2){
			ll k;
			cin>>k;
			areaChange1(1,x,y,k);
		}
		else{
//			for(int i=1;i<=n;i++)cout<<areaAsk(1,i,i)<<" ";
//			cout<<endl;
			cout<<areaAsk(1,x,y)<<endl;
		}
	}
}

肯定还会有同学想要看楼下的题解，但是为了经费着想，这里建议先拿一张纸记下这里的网址，最后在按Ctrl+N打开新网页，由于新网页会自动让你输入网址，也就少了一次点击。

网址：http://222.203.110.13/d/ybttg/p/P3373/solution/675d87dce803e82d6dfb37ab

Q:为什么不直接把鼠标移到链接上看?
A:字太小了