NTSEQ – spoj

October 13, 2016 by Leave a Comment

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

Thuật toán:

  • Rời rạc hóa rồi sử dụng cấu trúc dữ liệu BIT để tính
  • Các bạn mới học cần phải làm bài này trước mới hiểu rõ được: http://yeulaptrinh.de/102/lis-va-liq-su-dung-bit-spoj/
  • Mỗi nút của cây BIT lưu 2 giá trị là số lượng và độ dài dãy con dài nhất
  • Đọc code các bạn có thể hiểu ngay được

Code:

using namespace std;
#include
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e5;
const int INF = 1e9 + 7;

int n, a[MAXN], b[MAXN], __max = 0;
int f[MAXN];

struct data{
    int val, sl;
} T[MAXN];

void add(int &a, int b)
{
    a += b;
    if (a > INF) a -= INF;
}

data get(int x)
{
    data ans; ans.val = 0; ans.sl = 0;
    for(int i = x; i > 0; i -= i & -i) {
        if (ans.val < T[i].val) ans = T[i];
        else if (ans.val == T[i].val) add(ans.sl, T[i].sl);
    }
    return ans;
}

void update(int x, int val, int sl)
{
    for(int i = x; i <= __max + 1; i += i & -i){
        if (val > T[i].val) T[i].val = val, T[i].sl = sl;
        else {
                if (val == T[i].val) add(T[i].sl, sl);
        }
    }
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    FORE(i, 1, n) cin >> a[i];
    FORE(i, 1, n) b[i] = a[i]; sort(b + 1, b + n + 1);
    FORE(i, 1, n) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    __max = *max_element(a + 1, a + n + 1);
    a[n + 1] = __max + 1;
    FORE(i, 1, n + 1){
        data tmp = get(a[i] - 1);
        f[i] = tmp.val + 1;
        if (tmp.sl == 0) tmp.sl++;
        if (i == n + 1) cout<
Chủ đề: BIT, Nén số (rời rạc hóa mảng) Mức độ:

C11SEQ – spoj

September 27, 2016 by Leave a Comment

Đề 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.
Chủ đề: BIT, Nén số (rời rạc hóa mảng) Mức độ: