题解 P3373 一棵封装好的线段树
经典的线段树问题，大受
基础的思想与前面的
为了避免暴力地去处理，我们利用lazy_tag来存储一段区间上的操作，当处理或访问该区间时下放标记，将区间的值处理为修改后的真实值。
但是题目中有加、乘两种运算，我们在用两种标记分别存储两种操作的同时，还应处理好两种运算之间的关系——乘法的优先级高于加法，某次乘法操作的乘数k会影响到之前所有加上的值，因此要对区间的值和之前的加法操作标记都乘上k。
在下放标记时，如果先处理加法标记再处理乘法，会导致加法标记被多乘一遍使答案偏大；我们应先下放乘法的标记使子区间原来的值和加法标记乘k，再从原区间的加法标记处理子区间的加法操作。
对某几次操作的演示：
区间原值
--加法操作-> 区间原值+加法标记1*区间长度
--乘法操作-> (区间原值+加法标记1*区间长度)*乘法标记
--加法操作-> (区间原值+加法标记1*区间长度)*乘法标记+加法标记2*区间长度在这些的基础上，我们可以进行一些特别的优化：
-
在区间的加法标记为0、乘法标记为1（即该区间没有进行过任何操作）时，可以不进行下放标记的操作；
-
当被操作数小于模数时，取模操作可以不进行，在此可以进行判断（但最后千万不要忘写取模操作！）
-
我们把整棵线段树封装起来，将一些常用操作处理成专门的函数（可以使用
\mathrm{inline} 适当加快速度），更能提升代码的可读性，便于代码的修改。
这样，一篇别具风格的线段树代码就敲好啦~
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define PBCWZCC
using namespace std;
#define MAXN 100000
#define LL long long
#define DEBUG
#define MODIT
template<class T>inline void read(T&X)
{
X=0;
char symbol('\0'),ch(getchar());
for(;ch<'0'||'9'<ch;(ch=='-')?(symbol='\1'):(1),ch=getchar());
for(;'0'<=ch&&ch<='9';X=(X<<3)+(X<<1)+(ch^48),ch=getchar());
(symbol)?(X=-X):(1); // 原谅我的鬼畜码风，
//在我的程序里没有while()，这里的展开只是为了清晰Q.Q
} // 顺便有个快读板子？Q.Q
int n,m;
LL Modit; // 模数
namespace seg{ // 线段树所在的名空间
LL A[MAXN|3];
class sgt{ // 整棵线段树
private:
inline int fa(const int x) // 父亲（在这里没用）
{
return x>>1;
}
inline int lc(const int x) // 左孩子
{
return x<<1;
}
inline int rc(const int x) // 右孩子
{
return x<<1|1;
}
public:
LL val[MAXN<<2|3], // 区间和
tag[MAXN<<2|3], // 加法标记
tag2[MAXN<<2|3]; // 乘法标记
inline void pushup(const int p)
{
val[p] = val[lc(p)] + val[rc(p)];
// 首次/重新整合区间的信息
// 在更新完左右区间后，整合到父区间
}
void build(const int p,const int l,const int r)
{
tag2[p] = 1;
// 注意不能是 0 ，因为这个是乘法标记，表示
// 这段区间没乘过任何数（或者乘过 1 ）
if(l==r)
{
tag[p] = 0; // 加法标记
val[p] = A[l];
// 将单个元素的值赋到线段树的叶子结点
return ;
}
int mid((l+r)>>1);
build(lc(p),l,mid);
build(rc(p),mid+1,r);
pushup(p); // 整合子区间信息
}
inline void F1(const int p,const int l,const int r,const LL k)
{ // 指定区间的加法操作
tag[p] += k;
// 在加法标记加上 k
(Modit<=tag[p])?(tag[p]%=Modit):(1);
// 由于取模运算常数较大，这里特判是否需要取模
val[p] += k * (r-l+1);
// 这段区间加上的 k 的个数等于区间中元素的个数
(Modit<=val[p])?(val[p]%=Modit):(1);
}
inline void F2(const int p,const int l,const int r,const LL k)
{ // 指定区间的乘法操作
tag2[p] *= k;
// 乘法标记累乘
(Modit<=tag2[p])?(tag2[p]%=Modit):(1);
tag[p] *= k;
(Modit<=tag[p])?(tag[p]%=Modit):(1);
val[p] *= k;
(Modit<=val[p])?(val[p]%=Modit):(1);
// 区间的值和加法标记都要乘上 k
// (区间原值+加法操作的值)*k -> 区间新值1*k -> 区间新值2
}
inline void pushdown(const int p,const int l,const int r)
{
int mid((l+r)>>1);
F2(lc(p),l,mid,tag2[p]);
F2(rc(p),mid+1,r,tag2[p]);
// 应优先下放乘法标记，如果先下放加法标记会导致它被多乘一遍
F1(lc(p),l,mid,tag[p]);
F1(rc(p),mid+1,r,tag[p]);
tag2[p] = 1;
tag[p] = 0;
// 标记完成下放后，要记得还原
}
void update1(const int x,const int y,const int p,const int l,const int r,const LL k)
{ // 加法操作全过程
if(x<=l&&r<=y)
{
F1(p,l,r,k);
// 当前区间被包含在待修改区间里，直接处理这段区间对应的值
return ;
}
if(tag[p]||(tag2[p]^1)) pushdown(p,l,r);
// 在标记非空的时候下放标记
int mid((l+r)>>1);
if(x<=mid) update1(x,y,lc(p),l,mid,k);
if(mid+1<=y) update1(x,y,rc(p),mid+1,r,k);
pushup(p);
// 处理完子区间，整合
}
void update2(const int x,const int y,const int p,const int l,const int r,const LL k)
{ // 乘法操作全过程，基本与上面相同
if(x<=l&&r<=y)
{
F2(p,l,r,k);
return ;
}
if(tag[p]||(tag2[p]^1)) pushdown(p,l,r);
int mid((l+r)>>1);
if(x<=mid) update2(x,y,lc(p),l,mid,k);
if(mid+1<=y) update2(x,y,rc(p),mid+1,r,k);
pushup(p);
}
LL query(const int x,const int y,const int p,const int l,const int r)
{ // 区间和的查询
if(x<=l&&r<=y)
{
return val[p];
// 当前区间被包含在待查询区间里，直接返回这段区间对应的值
}
if(tag[p]||(tag2[p]^1)) pushdown(p,l,r);
int mid((l+r)>>1);
LL qq(0); // 待返回值
if(x<=mid) qq += query(x,y,lc(p),l,mid);
if(mid+1<=y) qq += query(x,y,rc(p),mid+1,r);
return qq%Modit; // 最后返回的时候记得取模（多数情况下这个 qq 会比模数大）
}
};
sgt T; // 一棵茂盛的（划）线段树
}
using namespace seg;
int main()
{
int i,t,x,y;
LL z;
read(n);
read(m);
read(Modit);
for(i=1;i<=n;++i)
{
read(A[i]);
}
T.build(1,1,n);
for(i=1;i<=m;++i)
{
read(t);
read(x);
read(y);
if(!(t^1))
{
read(z);
T.update2(x,y,1,1,n,z);
}
else if(!(t^2))
{
read(z);
T.update1(x,y,1,1,n,z);
}
else
{
printf("%lld\n",T.query(x,y,1,1,n));
}
}
return 0;
}
// 本人打这份代码平均要用 14 min 我真是太菜了TAT