裸的线段树，注意标签下放就行了

多么痛的领悟，一定要开int64

 

/**************************************************************    Problem: 1798    User: BLADEVIL    Language: Pascal    Result: Accepted    Time:24168 ms    Memory:11948 kb****************************************************************/ //By BLADEVILtype    rec                         =record        left, right, sum        :int64;        m_flag, p_flag          :int64;    end; var    n, p, m                     :int64;    t                           :array[0..300010] of rec; procedure build(x,l,r:int64);var    mid                         :int64;begin    t[x].left:=l; t[x].right:=r;    t[x].m_flag:=1;    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 2;    build(x*2,l,mid); build(x*2+1,mid+1,r);    t[x].sum:=(t[x*2].sum+t[x*2+1].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<>1 then        begin            cur:=t[x].m_flag;            t[2*x].m_flag:=(t[2*x].m_flag*cur) mod p;            t[2*x].p_flag:=(t[2*x].p_flag*cur) mod p;            t[2*x].sum:=(t[2*x].sum*cur) mod p;            t[2*x+1].m_flag:=(t[2*x+1].m_flag*cur) mod p;            t[2*x+1].p_flag:=(t[2*x+1].p_flag*cur) mod p;            t[2*x+1].sum:=(t[2*x+1].sum*cur) mod p;            t[x].m_flag:=1;        end;        if t[x].p_flag<>0 then        begin            cur:=t[x].p_flag;            t[2*x].p_flag:=(t[2*x].p_flag+cur) mod p;            t[2*x].sum:=(t[2*x].sum+cur*(t[2*x].right-t[2*x].left+1)) mod p;            t[2*x+1].p_flag:=(t[2*x+1].p_flag+cur) mod p;            t[2*x+1].sum:=(t[2*x+1].sum+cur*(t[2*x+1].right-t[2*x+1].left+1)) mod p;            t[x].p_flag:=0;        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 2;    if l>mid then m_change(x*2+1,l,r,c) else    if r<=mid then m_change(x*2,l,r,c) else    begin        m_change(x*2,l,mid,c);        m_change(x*2+1,mid+1,r,c);    end;    t[x].sum:=(t[2*x].sum+t[2*x+1].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<>1 then        begin            cur:=t[x].m_flag;            t[2*x].m_flag:=(t[2*x].m_flag*cur) mod p;            t[2*x].p_flag:=(t[2*x].p_flag*cur) mod p;            t[2*x].sum:=(t[2*x].sum*cur) mod p;            t[2*x+1].m_flag:=(t[2*x+1].m_flag*cur) mod p;            t[2*x+1].p_flag:=(t[2*x+1].p_flag*cur) mod p;            t[2*x+1].sum:=(t[2*x+1].sum*cur) mod p;            t[x].m_flag:=1;        end;        if t[x].p_flag<>0 then        begin            cur:=t[x].p_flag;            t[2*x].p_flag:=(t[2*x].p_flag+cur) mod p;            t[2*x].sum:=(t[2*x].sum+cur*(t[2*x].right-t[2*x].left+1)) mod p;            t[2*x+1].p_flag:=(t[2*x+1].p_flag+cur) mod p;            t[2*x+1].sum:=(t[2*x+1].sum+cur*(t[2*x+1].right-t[2*x+1].left+1)) mod p;            t[x].p_flag:=0;        end;    end;    if (t[x].left=l) and (t[x].right=r) then    begin        t[x].sum:=(t[x].sum+c*(r-l+1)) mod p;        t[x].p_flag:=(t[x].p_flag+c) mod p;        exit;    end;    with t[x] do mid:=(left+right) div 2;    if l>mid then p_change(x*2+1,l,r,c) else    if r<=mid then p_change(x*2,l,r,c) else    begin        p_change(x*2,l,mid,c);        p_change(x*2+1,mid+1,r,c);    end;    t[x].sum:=(t[x*2].sum+t[x*2+1].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<>1 then        begin            cur:=t[x].m_flag;            t[2*x].m_flag:=(t[2*x].m_flag*cur) mod p;            t[2*x].p_flag:=(t[2*x].p_flag*cur) mod p;            t[2*x].sum:=(t[2*x].sum*cur) mod p;            t[2*x+1].m_flag:=(t[2*x+1].m_flag*cur) mod p;            t[2*x+1].p_flag:=(t[2*x+1].p_flag*cur) mod p;            t[2*x+1].sum:=(t[2*x+1].sum*cur) mod p;            t[x].m_flag:=1;        end;        if t[x].p_flag<>0 then        begin            cur:=t[x].p_flag;            t[2*x].p_flag:=(t[2*x].p_flag+cur) mod p;            t[2*x].sum:=(t[2*x].sum+cur*(t[2*x].right-t[2*x].left+1)) mod p;            t[2*x+1].p_flag:=(t[2*x+1].p_flag+cur) mod p;            t[2*x+1].sum:=(t[2*x+1].sum+cur*(t[2*x+1].right-t[2*x+1].left+1)) mod p;            t[x].p_flag:=0;        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 2;    if l>mid then ask:=ask(x*2+1,l,r) else    if r<=mid then ask:=ask(x*2,l,r) else    ask:=(ask(x*2,l,mid)+ask(x*2+1,mid+1,r)) mod p;end;     procedure init;begin    read(n,p);    build(1,1,n);end; procedure main;var    i                           :longint;    k, l, r, x                  :int64;     begin    read(m);    for i:=1 to m do    begin        read(k);        if k=1 then        begin            read(l,r,x);            m_change(1,l,r,x);        end else        if k=2 then        begin            read(l,r,x);            p_change(1,l,r,x);        end else        if k=3 then        begin            read(l,r);            writeln(ask(1,l,r));        end;    end;end; begin    init;    main;end.

 赠送对拍器

var    n, m, p                    :longint;    r, l                    :longint;    i                        :longint;    k                        :longint;begin    randomize;    n:=100000;    m:=100000;    p:=random(1000000000)+1;    writeln(n,' ',p);    for i:=1 to n do write(random(1000000000)+1,' ');    writeln;    writeln(m);    for i:=1 to m do     begin        r:=random(n)+1;        l:=random(r)+1;        k:=random(3)+1;        if k=3 then             writeln(k,' ',l,' ',r) else             writeln(k,' ',l,' ',r,' ',random(10000000000)+1);    end;end.