C11SEQ – spoj

Đề bài: http://vn.spoj.com/problems/C11SEQ/

Thuật toán:

• Gọi S[i] là tổng từ a[1] đến a[i]
• Ta biến đổi yêu cầu đề bài

  • L <= a[i] + a[i+1] + ... + a[j] <= R

  • =>    L<=s[i] - s[j-1]<=R

  • =>        s[j-1]>=s[i]-r;
                 s[j-1]<=s[i]-l;
• Lưu các giá trị s[i] – r và s[i] – l và mảng kt 2*n ——> rời rạc hóa thành mảng b[1..2*n] ——> lưa vào cây BIT để tính:

  ans := ans + get(b[i]) - get(b[n+i]);

Code:

const
  fi='';//c11seq.inp';
  fo='';//c11seq.out';
  maxn=trunc(1e5);
var
  s,sr,sl : array[0..maxn] of int64;
  a  : array[0..maxn*3] of int64;
  b,cs,t  : array[0..maxn*3] of longint;
  i,j,n,l,r : longint;
  ans : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n,l,r);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do if (l<=a[i]) and (r>=a[i]) then inc(ans);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint);
  var i,j : longint;
      x : int64;
  begin
    i :=l;j:=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]j;
    if il then qs(l,j);
  end;
procedure init;
  var i,hold : longint;
  begin
    for i := 1 to n do s[i] := s[i-1] + a[i];
    for i := 1 to n do sl[i] := s[i] - l;
    for i := 1 to n do sr[i] := s[i] - r - 1;
    for i := 1 to n do
      begin
        a[i] := sl[i];
        a[n+i] := sr[i];
        a[n+n+i] := s[i-1];
      end;
    //a[2*n+1] := s[0] - l;
    //a[2*n+2] := s[0] - r;
    for i:=1 to 3*n do cs[i] := i;
    qs(1,3*n);
    b[cs[1]] := 1; hold := 1;
    for i:=2 to n*3 do
      if a[cs[i]] = a[cs[i-1]] then
        begin
          b[cs[i]] := hold;
        end
        else
        begin
          inc(hold);
          b[cs[i]] := hold;
        end;
  end;
procedure update(i : longint);
  begin
    while i<=3*n do
      begin
        t[i] := t[i] + 1;
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  begin
    get := 0;
    while i>0 do
      begin
        get := get + t[i];
        i := i - i and (-i);
      end;
  end;
procedure process;
  var i : longint;
  begin
    for i:=1 to n do
      begin
        ans := ans + get(b[i]) - get(b[n+i]);
        update(b[2*n+i]);
      end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(Output);
    writeln(ans);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.