题解 P3373 【【模板】线段树 2】
**Orz写题解的同时顺便说说自己的理解，哪里不对的地方求大佬斧正orz**
~~作为一个快被淘汰的Pascal选手（逃）
一本正经的写下这个Pascal题解（逃）~~
下面是代码,题解会标在代码上...
------------
program ex1;
var i,j,k,n,m,p,x,y,data,cnt,size:longint;
a:array[0..100000] of int64;
tree,mul,lazy:array[0..400007] of int64; f1:text;
//记得开int64，也就是C++中的long long 不然会算术上溢，这也是RE的错误之一了~~（亲身经历233）~~
Procedure pushdown(p,l,r:longint);//标记下传，注意先乘后加
var mid:longint;
begin
if (mul[p]=1)and(lazy[p]=0)then exit;
if (l=r) then
begin
mul[p]:=1;
lazy[p]:=0;
exit;
end;
mid:=(l+r) shr 1;
tree[p shl 1]:=(tree[p shl 1]*mul[p]+lazy[p]*(mid-l+1)) mod size;//mid-l+1与r-l+1同理
tree[p shl 1 or 1]:=(tree[p shl 1 or 1]*mul[p]+lazy[p]*(r-mid)) mod size;//r-mid就是区间长度，不用加1的原因很简单，因为此时的mid的位置是不算滴！
mul[p shl 1]:=(mul[p]*mul[p shl 1]) mod size;
mul[p shl 1 or 1]:=(mul[p]*mul[p shl 1 or 1]) mod size;//下传乘法标记
lazy[p shl 1]:=(lazy[p shl 1]*mul[p]+lazy[p])mod size;
lazy[p shl 1 or 1]:=(lazy[p shl 1 or 1]*mul[p]+lazy[p]) mod size;//下传加法标记，同样还是先乘再加
mul[p]:=1;
lazy[p]:=0;//将标记初始化。
end;
Procedure change(p,l,r,x,y:longint);//乘法运算
var mid:longint;
begin
if (r<x) or (l>y) then exit;
if (l>=x) and (r<=y) then
begin
tree[p]:=(tree[p]*data) mod size;
mul[p]:=(mul[p]*data) mod size;
lazy[p]:=(lazy[p]*data) mod size;//mul数组代表乘的标记，lazy就是加的标记，乘法运算里二者都要更新
exit;
end;
pushdown(p,l,r);
mid:=(l+r) shr 1;
if x<=mid then change(p shl 1,l,mid,x,y);//走左儿子
if y>mid then change(p shl 1 or 1,mid+1,r,x,y);//走右儿子
tree[p]:=(tree[p shl 1]+tree[p shl 1 or 1]) mod size;
end;
Procedure add(p,l,r,x,y:longint);//加法运算
var mid:longint;
begin
if (r<x) or (l>y) then exit;
if (l>=x) and (r<=y) then
begin
lazy[p]:=(lazy[p]+data) mod size;
tree[p]:=(tree[p]+(r-l+1)*data) mod size;//此时区间为[l,r]那么区间长度就是r-l+1，所以当前区间和为原来的和tree[P]加上区间长度r-l+1乘每一位要加的data就是更新的tree[p]。
exit;
end;
pushdown(p,l,r);
mid:=(l+r) shr 1;
if x<=mid then add(p shl 1,l,mid,x,y);
if y>mid then add(p shl 1 or 1,mid+1,r,x,y);
tree[p]:=(tree[p shl 1]+tree[p shl 1 or 1]) mod size;//要心心念念mod size
end;
Function count(p,l,r,x,y:longint):longint;
var mid:longint;
begin
count:=0;
if (r<x) or (l>y) then exit;//边界条件
if (l>=x) and (r<=y) then
exit(tree[p]);
pushdown(p,l,r);
mid:=(l+r) shr 1;//这句话相当于（l+r) div 2，某犇犇说位运算可以加速所以我就写了
exit(count(p shl 1,l,mid,x,y)+count(p shl 1 or 1,mid+1,r,x,y) mod size);
end;
Procedure build(p,l,r:longint);
var mid:longint;
begin
mul[p]:=1;
lazy[p]:=0;//mul数组的初始化特别重要，即乘法标记初始要置为1才能进行后续操作
if l=r then
begin
tree[p]:=a[l];
end else
begin
mid:=(l+r) shr 1;
build(p shl 1,l,mid);
build(p shl 1 or 1,mid+1,r);
tree[p]:=tree[p shl 1]+tree[p shl 1 or 1];
end;
tree[p]:=tree[p] mod size;//时刻mod size Orz
end;
begin//主程序没什么好讲的Orz
readln(n,m,size);
for i:=1 to n do read(a[i]);
build(1,1,n);
//我n天没过（并且找了很多大犇看都没发现问题）的地方就在这里...作为一个初学者，我居然...先build（建树）再read（读入）了啊啊啊啊啊啊啊啊
for i:=1 to m do
begin
read(cnt);
case cnt of
1:begin
readln(x,y,data);
change(1,1,n,x,y);
end;
2:begin
readln(x,y,data);
add(1,1,n,x,y);
end;
3:begin
readln(x,y);
writeln(count(1,1,n,x,y) mod size);
end;
end;
end;
end.
祝大家AC快乐~