Codeforces Round#250 D-The Child and Sequence/[TYVJ 3838]DQSとシーケンス(by帝江&Darkfalmes)

9225 ワード

テーマの大意

  • は3種類の操作があります:和を求めて、区間は型を取って、単点は
  • を修正します
  • n,m<=105,a[i]<=109

  • 公式の問題解.


    http://codeforces.com/blog/entry/12513vfkの大きなテーマは簡単に言えば、型取り操作の複雑さはnlog(n)を超えないと説明したが、私はTTTTTTTTを続け、確かに他の人よりQQQQQが遅いようだ.UPD:書き直したよ~
    const
     maxn=700000;
    var
     w:array[0..4*maxn,1..2]of int64;
     i,j,k:longint;
     n,m:longint;
     a,b,c,d:longint;
    procedure build(a,l,r:longint);
    var mid:longint;
    begin
     if l=r then begin read(w[a,1]); w[a,2]:=w[a,1]; exit; end;
     mid:=(l+r)>>1;
     build(a*2,l,mid); build(a*2+1,mid+1,r);
     w[a,1]:=w[a*2,1]+w[a*2+1,1];
     if w[a*2,2]>w[a*2+1,2]
     then w[a,2]:=w[a*2,2] else w[a,2]:=w[a*2+1,2];
    end;
    
    function query(a,x,y,l,r:longint):int64;
    var mid:longint;
    begin
     if (x=l)and(y=r)
     then exit(w[a,1]);
     mid:=(x+y)>>1;
     if r<=mid then exit(query(a*2,x,mid,l,r)) else 
     if l>mid then exit(query(a*2+1,mid+1,y,l,r))
     else exit(query(a*2,x,mid,l,mid)+query(a*2+1,mid+1,y,mid+1,r));
    end;
    
    procedure update1(a,x,y,l,r,mmod:longint);
    var mid:longint;
    begin
     if w[a,2]<mmod then exit;
     if x=y then begin w[a,1]:=w[a,1] mod mmod; w[a,2]:=w[a,1]; exit; end;
     mid:=(x+y)>>1;
     if r<=mid then update1(a*2,x,mid,l,r,mmod) else 
     if l>mid then update1(a*2+1,mid+1,y,l,r,mmod)
     else begin update1(a*2,x,mid,l,mid,mmod); update1(a*2+1,mid+1,y,mid+1,r,mmod); end;
     w[a,1]:=w[a*2,1]+w[a*2+1,1];
     if w[a*2,2]>w[a*2+1,2]
     then w[a,2]:=w[a*2,2] else w[a,2]:=w[a*2+1,2];
    end;
    
    procedure update2(a,x,y,b,c:longint);
    var mid:longint;
    begin
     if x=y then begin w[a,1]:=c; w[a,2]:=c; exit; end;
     mid:=(x+y)>>1;
     if b<=mid then update2(a*2,x,mid,b,c)
     else update2(a*2+1,mid+1,y,b,c);
     w[a,1]:=w[a*2,1]+w[a*2+1,1];
     if w[a*2,2]>w[a*2+1,2]
     then w[a,2]:=w[a*2,2] else w[a,2]:=w[a*2+1,2];
    end;
    
    begin
     readln(n,m);
     build(1,1,n);
     for i:=1 to m do
      begin
       read(a);
       case a of
       1:begin readln(b,c); writeln(query(1,1,n,b,c)); end;
       2:begin readln(b,c,d); update1(1,1,n,b,c,d); end;
       3:begin readln(b,c); update2(1,1,n,b,c); end;
       end;
      end;
    end.