文章目录

题目链接：

牛客练习赛28-B数据结构

①先加还是先乘？

来总结一哈线段树的lazy标记：
就是lazy标记既有加的，又有乘的，那向下更新的时候，应该先弄乘还是先弄加喃？
我们弄成都是先乘再加，只不过如果是先加再乘的话，做一哈变形就阔以了：
原来是sum，先加add，再乘mul，最后就是 (sum+add)mul
拆开来就是summul+addmul，这样就是先加再乘了，只不过lazy加不再是add了，而是addmul了

②维护平方和

拿4个数来举例子：
原来是： a , b , c , d a,b,c,d a,b,c,d
都加个 x x x ，变成 ( a + x ) 2 + ( b + x ) 2 + ( c + x ) 2 + ( d + x ) 2 (a+x)^2+(b+x)^2+(c+x)^2+(d+x)^2 (a+x)2+(b+x)2+(c+x)2+(d+x)2
拆开变成3坨：
( a 2 + b 2 + c 2 + d 2 ) + 2 ( a + b + c + d ) ⋅ x + 4 x 2 (a^2+b^2+c^2+d^2)+2(a+b+c+d)\cdot x+4x^2 (a2+b2+c2+d2)+2(a+b+c+d)⋅x+4x2

所以找出规律就是：
原来的平方和 + 2 ⋅ +2\cdot +2⋅ 原来的和 ⋅ x \cdot x ⋅x+区间长度 ⋅ x 2 \cdot x^2 ⋅x2

#include"bits/stdc++.h"
using namespace std;
typedef long long LL;
const int maxn=4e5+5;
LL MOD;
LL Sum1[maxn],Sum2[maxn],Add[maxn],Mul[maxn];
int N,Q;
void pushup(int id)
{
	Sum1[id]=Sum1[id<<1]+Sum1[id<<1|1];
	Sum2[id]=Sum2[id<<1]+Sum2[id<<1|1];
}
void pushdown(int id,int L,int R)
{
	if(Add[id]!=0||Mul[id]!=1)
	{
		Add[id<<1]  =Add[id<<1]*Mul[id]+Add[id];
		Add[id<<1|1]=Add[id<<1|1]*Mul[id]+Add[id];
		Mul[id<<1]  *=Mul[id];
		Mul[id<<1|1]*=Mul[id];
		int mid=L+R>>1;
		Sum2[id<<1]  =Sum2[id<<1]   + 2LL*Sum1[id<<1]  *Add[id] + Add[id]*Add[id]*(mid-L+1);
		Sum2[id<<1|1]=Sum2[id<<1|1] + 2LL*Sum1[id<<1|1]*Add[id] + Add[id]*Add[id]*(R-mid);
		Sum1[id<<1]  =Sum1[id<<1]   * Mul[id] + Add[id]*(mid-L+1);
		Sum1[id<<1|1]=Sum1[id<<1|1] * Mul[id] + Add[id]*(R-mid);
		Add[id]=0;
		Mul[id]=1;
	}
}
void Build(int id,int L,int R)
{
	Add[id]=0;
	Mul[id]=1;
	if(L==R)
	{
		scanf("%d",&Sum1[id]);
		Sum2[id]=Sum1[id]*Sum1[id];
		return ;
	}
	int mid=L+R>>1;
	Build(id<<1,L,mid);
	Build(id<<1|1,mid+1,R);
	pushup(id);
}
void Update(int id,int L,int R,int qL,int qR,LL add,LL mul)
{
	if(qL<=L&&qR>=R)
	{
		
		Add[id]=Add[id]*mul+add;
		Mul[id]*=mul;
		Sum2[id]=Sum2[id]+2LL*Sum1[id]*add+add*add*(R-L+1);
		Sum1[id]=Sum1[id]*mul+add*(R-L+1);
		return ;
	}
	pushdown(id,L,R);
	int mid=L+R>>1;
	if(qL<=mid)Update(id<<1,L,mid,qL,qR,add,mul);
	if(qR>=mid+1)Update(id<<1|1,mid+1,R,qL,qR,add,mul);
	pushup(id);
}
LL query(int id,int L,int R,int qL,int qR,int cmd)
{
	if(qL<=L&&qR>=R)
	{
		if(cmd==1)return Sum1[id];
		else return Sum2[id];
	}
	pushdown(id,L,R);
	int mid=L+R>>1;
	LL res=0;
	if(qL<=mid)res+=query(id<<1,L,mid,qL,qR,cmd);
	if(qR>=mid+1)res+=query(id<<1|1,mid+1,R,qL,qR,cmd);
	return res;
}

int main()
{

	while(cin>>N>>Q)
	{
		Build(1,1,N);
		while(Q--)
		{
			int cmd,L,R;
			LL val;
			scanf("%d",&cmd);
			if(cmd==1)
			{
				scanf("%d%d",&L,&R);
				cout<<query(1,1,N,L,R,1)<<endl;
			}
			else if(cmd==2)
			{
				scanf("%d%d",&L,&R);
				cout<<query(1,1,N,L,R,2)<<endl;
			}
			else if(cmd==3)
			{
				scanf("%d%d%lld",&L,&R,&val);
				Update(1,1,N,L,R,0,val);
			}
			else
			{
				scanf("%d%d%lld",&L,&R,&val);
				Update(1,1,N,L,R,val,1);
			}
// print();
		}
	}
}

打印出线段树

void print()
{
	for(int i=1; i<4*N; i++)
	{
		cout<<"id="<<i<<" Add="<<Add[i]<<" Mul="<<Mul[i]<<" Sum1="<<Sum1[i]<<" Sum2="<<Sum2[i]<<" | ";
		if((i&(i+1))==0)puts("");
	}
	puts("");
}

对拍

/*对拍程序 int N=4,Q=10; cout<<N<<" "<<Q<<endl; for(int i=1;i<=N;i++)cout<<Rand(1,10)<<" "; puts(""); while(Q--) { int cmd=Rand(2,4),L=Rand(1,N),R=Rand(1,N); if(L>R)swap(L,R); if(cmd==2)cout<<cmd<<" "<<L<<" "<<R<<endl; else if(cmd==3)cout<<cmd<<" "<<L<<" "<<R<<" "<<Rand(1,10)<<endl; else if(cmd==4)cout<<cmd<<" "<<L<<" "<<R<<" "<<Rand(1,10)<<endl; } */