裸的线段树，注意标签下放就行了
多么痛的领悟，一定要开int64
/**************************************************************
Problem:
User: BLADEVIL
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ //By BLADEVIL
type
rec =record
left, right, sum :int64;
m_flag, p_flag :int64;
end; var
n, p, m :int64;
t :array[..] of rec; procedure build(x,l,r:int64);
var
mid :int64;
begin
t[x].left:=l; t[x].right:=r;
t[x].m_flag:=;
if l=r then
begin
read(t[x].sum);
t[x].sum:=t[x].sum mod p;
exit;
end;
with t[x] do mid:=(left+right) div ;
build(x*,l,mid); build(x*+,mid+,r);
t[x].sum:=(t[x*].sum+t[x*+].sum) mod p;
end; procedure m_change(x,l,r,c:int64);
var
mid :int64;
cur :int64; begin
if t[x].left<>t[x].right then
begin
if t[x].m_flag<> then
begin
cur:=t[x].m_flag;
t[*x].m_flag:=(t[*x].m_flag*cur) mod p;
t[*x].p_flag:=(t[*x].p_flag*cur) mod p;
t[*x].sum:=(t[*x].sum*cur) mod p;
t[*x+].m_flag:=(t[*x+].m_flag*cur) mod p;
t[*x+].p_flag:=(t[*x+].p_flag*cur) mod p;
t[*x+].sum:=(t[*x+].sum*cur) mod p;
t[x].m_flag:=;
end;
if t[x].p_flag<> then
begin
cur:=t[x].p_flag;
t[*x].p_flag:=(t[*x].p_flag+cur) mod p;
t[*x].sum:=(t[*x].sum+cur*(t[*x].right-t[*x].left+)) mod p;
t[*x+].p_flag:=(t[*x+].p_flag+cur) mod p;
t[*x+].sum:=(t[*x+].sum+cur*(t[*x+].right-t[*x+].left+)) mod p;
t[x].p_flag:=;
end;
end;
if (t[x].left=l) and (t[x].right=r) then
begin
t[x].sum:=(t[x].sum*c) mod p;
t[x].p_flag:=(t[x].p_flag*c mod p);
t[x].m_flag:=(t[x].m_flag*c mod p);
exit;
end;
with t[x] do mid:=(left+right) div ;
if l>mid then m_change(x*+,l,r,c) else
if r<=mid then m_change(x*,l,r,c) else
begin
m_change(x*,l,mid,c);
m_change(x*+,mid+,r,c);
end;
t[x].sum:=(t[*x].sum+t[*x+].sum) mod p;
end; procedure p_change(x,l,r,c:int64);
var
mid :int64;
cur :int64;
begin
if t[x].left<>t[x].right then
begin
if t[x].m_flag<> then
begin
cur:=t[x].m_flag;
t[*x].m_flag:=(t[*x].m_flag*cur) mod p;
t[*x].p_flag:=(t[*x].p_flag*cur) mod p;
t[*x].sum:=(t[*x].sum*cur) mod p;
t[*x+].m_flag:=(t[*x+].m_flag*cur) mod p;
t[*x+].p_flag:=(t[*x+].p_flag*cur) mod p;
t[*x+].sum:=(t[*x+].sum*cur) mod p;
t[x].m_flag:=;
end;
if t[x].p_flag<> then
begin
cur:=t[x].p_flag;
t[*x].p_flag:=(t[*x].p_flag+cur) mod p;
t[*x].sum:=(t[*x].sum+cur*(t[*x].right-t[*x].left+)) mod p;
t[*x+].p_flag:=(t[*x+].p_flag+cur) mod p;
t[*x+].sum:=(t[*x+].sum+cur*(t[*x+].right-t[*x+].left+)) mod p;
t[x].p_flag:=;
end;
end;
if (t[x].left=l) and (t[x].right=r) then
begin
t[x].sum:=(t[x].sum+c*(r-l+)) mod p;
t[x].p_flag:=(t[x].p_flag+c) mod p;
exit;
end;
with t[x] do mid:=(left+right) div ;
if l>mid then p_change(x*+,l,r,c) else
if r<=mid then p_change(x*,l,r,c) else
begin
p_change(x*,l,mid,c);
p_change(x*+,mid+,r,c);
end;
t[x].sum:=(t[x*].sum+t[x*+].sum) mod p;
end; function ask(x,l,r:int64):int64;
var
mid :int64;
cur :int64;
begin
if t[x].left<>t[x].right then
begin
if t[x].m_flag<> then
begin
cur:=t[x].m_flag;
t[*x].m_flag:=(t[*x].m_flag*cur) mod p;
t[*x].p_flag:=(t[*x].p_flag*cur) mod p;
t[*x].sum:=(t[*x].sum*cur) mod p;
t[*x+].m_flag:=(t[*x+].m_flag*cur) mod p;
t[*x+].p_flag:=(t[*x+].p_flag*cur) mod p;
t[*x+].sum:=(t[*x+].sum*cur) mod p;
t[x].m_flag:=;
end;
if t[x].p_flag<> then
begin
cur:=t[x].p_flag;
t[*x].p_flag:=(t[*x].p_flag+cur) mod p;
t[*x].sum:=(t[*x].sum+cur*(t[*x].right-t[*x].left+)) mod p;
t[*x+].p_flag:=(t[*x+].p_flag+cur) mod p;
t[*x+].sum:=(t[*x+].sum+cur*(t[*x+].right-t[*x+].left+)) mod p;
t[x].p_flag:=;
end;
end;
if (t[x].left=l) and (t[x].right=r) then
begin
ask:=t[x].sum mod p;
exit;
end;
with t[x] do mid:=(left+right) div ;
if l>mid then ask:=ask(x*+,l,r) else
if r<=mid then ask:=ask(x*,l,r) else
ask:=(ask(x*,l,mid)+ask(x*+,mid+,r)) mod p;
end; procedure init;
begin
read(n,p);
build(,,n);
end; procedure main;
var
i :longint;
k, l, r, x :int64; begin
read(m);
for i:= to m do
begin
read(k);
if k= then
begin
read(l,r,x);
m_change(,l,r,x);
end else
if k= then
begin
read(l,r,x);
p_change(,l,r,x);
end else
if k= then
begin
read(l,r);
writeln(ask(,l,r));
end;
end;
end; begin
init;
main;
end.
赠送对拍器
var
n, m, p :longint;
r, l :longint;
i :longint;
k :longint;
begin
randomize;
n:=;
m:=;
p:=random()+;
writeln(n,' ',p);
for i:= to n do write(random()+,' ');
writeln;
writeln(m);
for i:= to m do
begin
r:=random(n)+;
l:=random(r)+;
k:=random()+;
if k= then
writeln(k,' ',l,' ',r) else
writeln(k,' ',l,' ',r,' ',random()+);
end;
end.