線段樹。支持區間加、區間乘、區間查詢和。

標記下移還有取模要注意。

?

• var

• n,p,q,i,s,t:longint;

• a:int64;

• num,n1,n2,n3:array[0..500000] of int64;

• ?

• procedure build(o,l,r:longint);

• var m,i:longint;

• begin

• m:=(l+r) div 2;

• if l=r then

• ? begin

• ? n1[o]:=num[l];

• ? n2[o]:=num[l];

• ? end

• else

• ? begin

• ? build(o*2,l,m);

• ? build(o*2+1,m+1,r);

• ? end;

• if o>1 then n1[o div 2]:=(n1[o div 2]+n1[o]) mod p;

• end;

• ?

• procedure add(o,l,r:longint);

• var m,i:longint;

• begin

• m:=(l+r) div 2;

• if l<>r then

• ? begin

• ? n1[o*2]:=(n1[o*2]*n3[o]+n2[o]*((m-l+1) mod p)) mod p;

• ? n2[o*2]:=(n2[o*2]*n3[o]+n2[o]) mod p;

• ? n3[o*2]:=(n3[o*2]*n3[o]) mod p;

• ? n1[o*2+1]:=(n1[o*2+1]*n3[o]+n2[o]*((r-m) mod p)) mod p;

• ? n2[o*2+1]:=(n2[o*2+1]*n3[o]+n2[o]) mod p;

• ? n3[o*2+1]:=(n3[o*2+1]*n3[o]) mod p;

• ? n2[o]:=0;n3[o]:=1;

• ? end;

• if (s<=l)and(r<=t) then

• ? begin

• ? n1[o]:=(n1[o]+a*((r-l+1) mod p)) mod p;

• ? n2[o]:=(n2[o]+a) mod p;

• ? end

• else

• ? begin

• ? if s<m+1 then add(o*2,l,m);

• ? if m<t then add(o*2+1,m+1,r);

• ? n1[o]:=(n1[o*2]+n1[o*2+1]) mod p;

• ? end;

• end;

• ?

• procedure che(o,l,r:longint);

• var m,i:longint;

• begin

• m:=(l+r) div 2;

• if l<>r then

• ? begin

• ? n1[o*2]:=(n1[o*2]*n3[o]+n2[o]*((m-l+1) mod p)) mod p;

• ? n2[o*2]:=(n2[o*2]*n3[o]+n2[o]) mod p;

• ? n3[o*2]:=(n3[o*2]*n3[o]) mod p;

• ? n1[o*2+1]:=(n1[o*2+1]*n3[o]+n2[o]*((r-m) mod p)) mod p;

• ? n2[o*2+1]:=(n2[o*2+1]*n3[o]+n2[o]) mod p;

• ? n3[o*2+1]:=(n3[o*2+1]*n3[o]) mod p;

• ? n2[o]:=0;n3[o]:=1;

• ? end;

• if (s<=l)and(r<=t) then

• ? begin

• ? n1[o]:=(n1[o]*a) mod p;

• ? n2[o]:=(n2[o]*a) mod p;

• ? n3[o]:=(n3[o]*a) mod p;

• ? end

• else

• ? begin

• ? if s<m+1 then che(o*2,l,m);

• ? if m<t then che(o*2+1,m+1,r);

• ? n1[o]:=(n1[o*2]+n1[o*2+1]) mod p;

• ? end;

• end;

• ?

• function que(o,l,r:longint):int64;

• var m,i:longint;

• begin

• m:=(l+r) div 2;

• que:=0;

• if l<>r then

• ? begin

• ? n1[o*2]:=(n1[o*2]*n3[o]+n2[o]*((m-l+1) mod p)) mod p;

• ? n2[o*2]:=(n2[o*2]*n3[o]+n2[o]) mod p;

• ? n3[o*2]:=(n3[o*2]*n3[o]) mod p;

• ? n1[o*2+1]:=(n1[o*2+1]*n3[o]+n2[o]*((r-m) mod p)) mod p;

• ? n2[o*2+1]:=(n2[o*2+1]*n3[o]+n2[o]) mod p;

• ? n3[o*2+1]:=(n3[o*2+1]*n3[o]) mod p;

• ? n2[o]:=0;n3[o]:=1;

• ? end;

• if (s<=l)and(r<=t) then que:=n1[o]

• else

• ? begin

• ? if s<m+1 then que:=(que+que(o*2,l,m)) mod p;

• ? if m<t then que:=(que+que(o*2+1,m+1,r)) mod p;

• ? end;

• end;

• ?

• begin

• read(n,p);

• for i:=1 to n do read(num[i]);

• for i:=1 to n do num[i]:=num[i] mod p;

• for i:=1 to 3*n do n3[i]:=1;

• build(1,1,n);

• read(q);

• for i:=1 to q do

• ? begin

• ? read(a);

• ? case a of

• ? ? 1:begin

• ? ? ? read(s,t,a);

• ? ? ? a:=a mod p;

• ? ? ? che(1,1,n);

• ? ? ? end;

• ? ? 2:begin

• ? ? ? read(s,t,a);

• ? ? ? a:=a mod p;

• ? ? ? add(1,1,n);

• ? ? ? end;

• ? ? 3:begin

• ? ? ? read(s,t);

• ? ? ? writeln(que(1,1,n));

• ? ? ? end;

• ? ? end;

• ? end;

• end.

  ?

?

我寫的有些麻煩。。。

?

轉載于:https://www.cnblogs.com/NanoApe/p/4396760.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的BZOJ-1798 维护序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。