WS – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';
var
  a : array[1..50000] of longint;
  val,valmax,rem : array[1..200000] of longint;
  n,k,m : longint;
 
 
procedure enter;
  var
    i,j,tmp : longint;
  begin
    n := 0;
    readln(k,m);
    i := 1;
    for j := 1 to k do
      begin
        read(tmp);
        a[i] := 1;
        inc(i,tmp);
        inc(n,tmp);
      end;
    readln;
  end;
 
procedure init(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        valmax[s] := 1;
        exit;
      end;
    mid := (l + r) div 2;
    init(2*s,l,mid);
    init(2*s+1,mid+1,r);
    valmax[s] := valmax[2*s] + valmax[2*s+1];
  end;
 
procedure init2(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        inc(val[s],a[l]);
        exit;
      end;
    mid := (l + r) div 2;
    init2(2*s,l,mid);
    init2(2*s+1,mid+1,r);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure trans(s,l,r : longint);
  var
    mid : longint;
  begin
    if (s = 0) or (l = r) then exit;
    mid := (l + r) div 2;
    inc(val[2*s],rem[s]*(mid-l+1));
    inc(val[2*s+1],rem[s]*(r-mid));
    inc(rem[2*s],rem[s]);
    inc(rem[2*s+1],rem[s]);
    rem[s] := 0;
  end;
 
procedure Jupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = valmax[s] then
          begin
            dec(val[s],r-l+1);
            dec(rem[s]);
            exit;
          end;
        if val[s] = 0 then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Jupdate(2*s,l,mid,u,v);
    Jupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure Dupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = 0 then
          begin
            inc(val[s],r-l+1);
            inc(rem[s]);
            exit;
          end;
        if val[s] = valmax[s] then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Dupdate(2*s,l,mid,u,v);
    Dupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure query(c : char; u,v : longint);
  begin
    if c = 'J' then Jupdate(1,1,n,u+1,v)
    else Dupdate(1,1,n,u+1,v);
  end;
 
procedure main;
  var
    i,u,v : longint;
    c : char;
  begin
    init(1,1,n);
    init2(1,1,n);
    for i := 1 to m do
      begin
        read(c);
        if c = 'C' then
          begin
            writeln(val[1]);
            readln;
          end
        else
          begin
            readln(u,v);
            query(c,u,v);
          end;
      end;
  end;
 
 
begin
  assign(input,fi);
  reset(input);
  enter;
  main;
  close(input);
end.
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây……

Speak Your Mind

*