Cấu trúc dữ liệu

Cấu trúc dữ liệu BIT – Binary Indexed Tree (Fenwick Tree)

August 12, 2017 by Aida Nana Leave a Comment

Giới thiệu về cây Fenwick (hay còn được gọi là BIT)

Tổng quát, đặt m = 2^k.p (với p là số lẻ). Hay nói cách khác, k là vị trí của bít 1 bên phải nhất của m. Trong Fenwick-Tree, nút có số hiệu m sẽ là nút gốc của một cây con gồm 2^k nút có số hiệu từ m- 2^k+1 đến m.

Ví dụ:

– 8 = 2³.1, vậy 8 là nút gốc của các nút 1, 2, 3, …, 8.

– 12 = 2².3, vậy 12 là nút gốc của các nút 9, 10, 11, 12

– 10 = 2¹.5, vậy 10 là nút gốc của các nút 9, 10.

– 7 = 2⁰.7, vậy 7 là nút gốc của chỉ nút 7.

– 16 = 2⁴.1, vậy 16 là nút gốc của các nút 1, 2, 3, …, 16.

Trong Fenwick-Tree, nút gốc đại diện cho tất cả các nút con của nó. Ý nghĩa của từ đại diện ở đây thường dùng là nút gốc lưu tổng giá trị của các nút con. Vì vậy khi tính toán, ta chỉ cần truy xuất nút gốc là đủ mà không cần thiết phải truy xuất đến các nút con. Xét ví dụ:

Cho mảng gồm n phần tử a₁, a₂, …, a_n. Hãy tính tổng A_m = a₁ + a₂+ … + a_m (m ≤ n).

Thay vì sử dụng vòng lặp từ 1 đến m để truy xuất từng phần tử a_i một (độ phức tạp O(m)), ta sử dụng cấu trúc FENWICK-TREE như sau:

– t₁ = a₁

– t₂ = a₁ + a₂

– t₃ = a₃

– t₄ = a₁ + a₂ + a₃ + a₄

– t₅ = a₅

– t₆ = a₅ + a₆

– t₇ = a₇

– t₈ = a₁ + a₂ + a₃ + a₄+ a₅ + a₆ + a₇ + a₈

– …

– t₁₂ = a₉ + a₁₀ + a₁₁ + a₁₂

– … (tiếp tục như vậy theo cách xây dựng Fenwick-Tree)

* Để tính A₁₅ (m=15), thay vì phải duyệt từ a₁ đến a₁₅, ta chỉ cần tính t₈+ t₁₂+ t₁₄+ t₁₅ .

* Để tính A₁₀, chỉ cần tính t₈+ t₁₀

* Để tính A₁₃, chỉ cần tính t₈+ t₁₂ + t₁₃

* Để tính A₁₆, lấy ngay giá trị t₁₆

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, sau đó lần lượt xóa các bít 1 của m theo thứ tự từ phải sang trái, tại mỗi bước trung gian chính là chỉ số nút cần truy xuất trong Fenwick-Tree.

Ví dụ: m = 13 có biểu diễn nhị phân là 1101:

1) 1101 -> truy xuất nút 13

2) Xóa bít 1 bên phải nhất còn 1100 -> truy xuất nút 12

3) Xóa bít 1 bên phải nhất còn 1000 -> truy xuất nút 8

4) Xóa bít 1 bên phải nhất và dừng.

Thao tác truy xuất các nút như trên được gọi là getFENWICK-TREE. May mắn là ta có một công thức rất đơn giản để xóa bít 1 bên phải dùng phép toán AND. Thủ tục getFENWICK-TREE như sau:

int getFENWICK-TREE(int m)
{
            int result = 0;
            for(; m> 0; m &= m-1)
            {
                      result += t[m];
            }
            return result;
}

Độ phức tạp của getFENWICK-TREE là O(log₂m)

Vấn đề còn lại là làm thế nào để xây dựng được Fenwick-Tree như trên? Cách thực hiện là ban đầu khởi tạo các nút của Fenwick-Tree là 0. Sau đó ứng với mỗi giá trị a_m thì cập nhật các nút cha liên quan trong cây. Ví dụ:

– Cập nhật giá trị a₅ -> cần cập nhật các nút t₅, nút cha t₆, nút cha t₈, nút cha t₁₆,….

– Cập nhật giá trị a₉ -> cần cập nhật các nút t₉, nút cha t₁₀, nút cha t₁₂, nút cha t₁₆,…

– Cập nhật giá trị a₄ -> cần cập nhật các nút t₄, nút cha t₈, nút cha t₁₆,…

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, nếu cộng 1 vào bít bên phải nhất của m thì ta được nút cha của m.

Ví dụ, m = 5 có biểu diễn nhị phân là 101:

1) 101 -> cập nhật nút 5

2) Cộng 1 vào bít phải nhất thành 0110 -> cập nhật nút 6

3) Cộng 1 vào bít phải nhất thành 1000 -> cập nhật nút 8

4) Cộng 1 vào bít phải nhất thành 10000 -> cập nhật nút 16.

Thao tác cập nhật các nút từ con đến cha như trên được gọi là updateFENWICK-TREE. Ta cũng có một công thức rất đơn giản để cộng 1 vào bít 1 bên phải nhất dùng phép toán AND. Thủ tục updateFENWICK-TREE như sau:

void updateFENWICK-TREE(int m, int value)
{
   for(; m<= n; m += m & -m)
   {
        t[m] += value;
   }
}

Độ phức tạp của updateFENWICK-TREE là O(log₂n)

Trên đây là lý thuyết về Binary Indexed Tree. Bây giờ ta sẽ áp dụng FENWICK-TREE để giải bài Dãy nghịch thế và Dĩa nhạc 3.

Dãy nghịch thế: (Theo cách vét cạn thì cần xét tất cả các cặp, độ phức tạp là O(n²))

Phác thảo thuật toán:

– Dùng một mảng đếm t[100.000], t[u] cho biết hiện giờ có bao nhiêu số nhỏ hơn u.

– Đầu tiên khởi tạo các phần tử mảng t là 0.

– Duyệt từ cuối mảng lên đầu mảng (i từ n->1), ứng với mỗi a_i thực hiện hai thao tác:

1) Kiểm tra xem hiện giờ có bao nhiêu số nhỏ hơn a_i (truy xuất t[a_i]).

2) Cập nhật a_i vào mảng t, nghĩa là tăng các phần tử từ t[a_i+1] đến t[100.000], mỗi phần tử thêm 1.

Tuy nhiên trong thao tác 2 việc cập nhật như vậy tổng thể độ phức tạp vẫn là O(n²). Bây giờ ta sẽ chuyển mảng t thành cấu trúc FENWICK-TREE. Đối với thao tác 1 dùng getFENWICK-TREE, đối với thao tác 2 dùng updateFENWICK-TREE.

Chương trình hoàn chỉnh

cin>>n;
for(i= 1; i<= n; i++) cin>>a[i];
kq = 0;
for(i= n; i>= 1; i–)
{
kq += getFENWICK-TREE(a[i]);
updateFENWICK-TREE(a[i]+1, 1);
}
cout<<kq;

Độ phức tạp là O(nlog₂n)

Chủ đề: BIT, Cấu trúc dữ liệu

MSE07B – spoj

August 11, 2017 by Aida Nana Leave a Comment

Đề bài:

http://vn.spoj.com/problems/MSE07B/

Thuật toán:

Nếu bạn sử dụng C++ thì có thể dùng cấu trúc dữ liệu có sẵn là std::set, còn nếu dùng Pascal thì sẽ phải code dài hơn một chút.
Toàn bộ về std::set cho bạn nào dùng C++: http://yeulaptrinh.de/938/set-trong-c/

Code:

(xem code C++)

#include 
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;

set s;
set::iterator it;
int p, k, x, i;

int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> x;
    while (x != 0) {
        //
        if (x == 1) {
            cin >> k >> p;
            s.insert(PII(p,k));
        }
        //
        if (x == 2)
        if (!s.empty()) {
            it = s.end(); -- it;
            cout << it -> se << endl;
            s.erase(it);
        } else cout << 0 << endl;
        //
        if (x==3)
        if (!s.empty()) {
            it = s.begin();
            cout << it -> se << endl;
            s.erase(it);
        } else cout << 0 << endl;
        //
        cin >> x;
    }
	return 0;
}

Chủ đề: Cấu trúc dữ liệu, Set

MESSAGE1 – spoj

August 9, 2017 by cau_buon_vi_ai Leave a Comment

[mathjax]

Đề bài

http://vn.spoj.com/problems/MESSAGE1/

Thuật toán

Ở bài này ta dời bảng B như hình, trong mỗi lần dời ta so sách các ô trong vùng giao nhau nữa 2 bảng, ô bằng nhau có giá trị 1, khác nhau có giá trị 0.

Cụ thể hơn, giả sử ta dời bảng B theo một vector $(x, y)$, khi đó ô $A(i, j)$ sẽ được so sánh với ô $B(i-x, j-y)$. Ta tính toạ độ các ô trong phần giao giữa 2 bảng như sau, có 4 điều kiện:

$
\begin{cases}
0 <= i < m\\
0 <= j < n\\
0 <= i-x < m\\
0 <= i-y < n\\
\end{cases}
$

Từ đó suy ra:

$
\begin{cases}
max(0, x) <= i < min(m, m + x)\\
max(0, y) <= j < min(n, n + y)\\
\end{cases}
$

Sau đó ta tìm hình chữ nhật chứa toàn số 1 và có diện tích lớn nhất (như bài QBRECT).

Sau đây là cách tìm hình chữ nhật như trên trong thời gian $O(n^2)$:

Với mỗi ô $j$ trên hàng $i$, ta tìm $f(j)$ là số ô 1 liên tiếp trên cột $j$, tính từ hàng $i$ trở lên. Sau đó, với mỗi cột $j$, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có $f$ nhỏ hơn $f(j)$, sau đó tính diện tích hình chữ nhật ở cột $j$ là $S = f(j)\times(r – l – 1)$ với $l, r$ là chỉ số 2 ô bên trái và bên phải nói trên.

Hình minh hoạ khi tính $f(4)$:

message1-2-yeulaptrinh.pw

Để tìm $l, r$ nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Độ phức tạp của toàn bộ lời giải là $O(n^4)$.

Code

#include 
#include 
#include 
using namespace std;

void calc(int &res, int x, int y, const vector &a, const vector &b) {
    int m = a.size(), n = a[0].size();
    int low_i = max(0, x), high_i = min(m, m + x);
    int low_j = max(0, y), high_j = min(n, n + y);
    if ((high_i - low_i)*(high_j - low_j) <= res) return;
    vector f(high_j, 0);
    vector l(high_j), q(high_j), idx(high_j);
    for (int i=low_i; i < high_i; i++) {
        int top = 0;
        for (int j=low_j; j < high_j; j++) {
            if (a[i][j] == b[i-x][j-y]) {
                f[j]++;
                while (top && q[top-1]>=f[j]) top--;
                if (!top) l[j] = low_j-1;
                else l[j] = idx[top-1];
                q[top] = f[j], idx[top] = j, top++;
            } else {
                f[j] = 0;
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
        top = 0;
        int r;
        for (int j=high_j-1; j >= low_j; j--) {
            if (f[j]) {
                while (top && q[top-1]>=f[j]) top--;
                if (!top) r = high_j;
                else r = idx[top-1];
                res = max(res, f[j]*(r - l[j] - 1));
                q[top] = f[j], idx[top] = j, top++;
            } else {
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> m >> n;
        vector a(m), b(m);
        for (auto &s: a) cin >> s;
        for (auto &s: b) cin >> s;
        int res = 0;
        for (int i=-m+1; i

Chủ đề: Cấu trúc dữ liệu, Deque

QBHEAP – spoj

March 12, 2017 by Aida Nana Leave a Comment

Đề bài:

http://vn.spoj.com/problems/QBHEAP/

Thuật toán:

Với C++ bạn có thể dùng sẵn CTDL Priority Queue (hàng đợi ưu tiên). Còn với Pascal thì bạn phải tự viết CTDL Heap

Code:

C++ (xem)

#include 

using namespace std;

const int MAXN = 20000;
string s;
priority_queue  h;
char key;
int num, a[MAXN];

bool cmp(int a, int b) {
    return (a > b);
}

int main() {
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    // solve
    getline(cin, s);
    do {
        key = s[0];
        if (key == '+') {
            s.erase(0,1);
            num = atoi(s.c_str());
            if (h.size()<15000) h.push(num);
        } else if (!h.empty())
        {
            num = h.top();
            while (!h.empty() && h.top()==num) h.pop();
        }
        getline(cin, s);
    } while (s != "");
    // pop
    int res = 0;
    while (!h.empty()) {
        res++;
        a[res] = h.top();
        while (!h.empty() && h.top()==a[res]) h.pop();
    }
    // print
    cout << res << endl;
    for (int i = 1; i <= res; i++) cout << a[i] << endl;
    return 0;
}

Pascal (xem)

const   fi='';
        fo='';
        maxn=15000+3;
var     h:array[1..maxn] of longint;
        i,j:longint;
        res:array[0..maxn] of longint;
        nh,n,ans:longint;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,i,j:longint;
begin
            i:=l;j:=r;
            x:=res[(i+j) div 2];
            repeat
                while res[i]>x do inc(i);
                while res[j]j;
            if il then qs(l,j);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:= i + i;
        if j>nh then exit;
        if (jh[i] then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if h[i]>h[j] then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
procedure push(x:longint);
begin
        inc(nh);
        h[nh]:=x;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure xuat;
begin
        for i:=1 to n do
                if res[i]<>res[i-1] then writeln(res[i]);
end;
procedure main;
var     tam,s:string;
        x,err:longint;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);

    while not seekeof(input) do
        begin
            readln(s);
            if s[1]='+' then
            begin
              if nh<15000 then
                begin
                    tam:=copy(s,2,length(s));
                    val(tam,x,err);
                    push(x);
                end
                end
                ELSE
                if nh>0 then
                begin
                        if nh>0 then x:=pop;
                        while (nh>0) and (h[1]=x) do pop;
                end;
        end;
        for i:=1 to nh do
                begin
                        res[i]:=pop;
                        inc(n);
                end;
        qs(1,n);
        res[0]:=-1;
        for i:=1 to n do
                if res[i]<>res[i-1] then inc(ans);
        writeln(ans);
        xuat;

    close(input);close(output);
end;
begin
    main;
end.

Chủ đề: Cấu trúc dữ liệu, Heap Mức độ: basic

LIQ và LIS sử dụng BIT – SPOJ

May 2, 2016 by Aida Nana Leave a Comment

Đề bài:

Thuật toán:

Rời rạc hóa lại dãy
Gọi F[i] là độ dài dãy con tăng dài nhất kết thúc là số <= i
F[i] = max(F[1..a[i]-1] + 1)
Sử dụng cấu trúc dữ liệu BIT để tính mảng F trong O(logn)
ĐPT: O(nlogn)

Code:

using namespace std;
//#include
#include 
#include 
#define FOR(i,a,b) for (long long i=a;i=b; i--)

int n, a[300010], T[300010], c[300010], f[300010], dem;
pair b[300010];

int Get(int x)
{
    int ans = 0;
    if (x == 0) return 0;
    while (x > 0) {
        ans = max(ans, T[x]);
        x -= x & (-x);
    }
    return ans;
}

void Update(int x, int v)
{
    while (x <= n){
        T[x] = max(T[x], v);
        x += x & (-x);
    }
}

int main()
{
    //freopen("LIS.inp", "r", stdin);
    //freopen("LIS.out", "w", stdout);
    //cin>>n;
    scanf("%d", &n);
    FORE(i, 1, n) {
        //cin>>a[i];
        scanf("%d", &a[i]);
        b[i].first = a[i];
        b[i].second = i;
    }

    sort(b + 1, b + n + 1);

    int dem = 1; c[ b[1].second ] = dem;
    FORE(i, 2, n) {
        if (b[i].first > b[i - 1].first) dem++;
        c[ b[i].second ] = dem;
    }
    int ans = 0;

    FORE(i, 1, n) a[i] = c[i];
    //FORE(i, 1, n) cout<

Chủ đề: BIT, Cấu trúc dữ liệu, SPOJ, Thuật toán Mức độ: bit, ctdl, day con tang, liq, lis

HIREHP – SPOJ

February 16, 2016 by Aida Nana Leave a Comment

Đề bài: http://vn.spoj.com/problems/HIREHP/
Thuật toán: Dùng cây IT lưu giá trị tối ưu tại mỗi thời gian. Với bài này khi cập nhập thì cập nhập từ lá lên gốc
Code:

uses math;
const
  fi='hirehp.inp';
  fo='hirehp.out';
  maxn=5*trunc(1e5);
  oo=trunc(1e18);
var
  tree : array[1..4*maxn] of int64;
  idleaf : array[1..maxn] of longint;
  i,j,n : longint;
  f : array[1..maxn] of int64;
  t,p : array[1..maxn] of longint;
procedure build(k,l,r : longint);
  var m : longint;
  begin
    if l = r then
      begin
        idleaf[l] := k;
        exit;
      end;
    m := (l+r) div 2;
    build(k*2,l,m);
    build(k*2+1,m+1,r);
  end;
procedure update(j: longint; x : int64);
  begin
    i := idleaf[j];
    while i > 0 do
      begin
        tree[i] := min(tree[i] , x);
        i := i div 2;
      end;
  end;
function get(k,l,r,i,j : longint) : int64;
  var m  :  longint;
      tg1,tg2 : int64;
  begin
    if (i>r) or (j=r) then exit(tree[k]);
    m := (l+r) div 2;
    tg1 := get(k*2,l,m,i,j);
    tg2 := get(k*2+1,m+1,r,i,j);
    get := min(tg1,tg2);
  end;
procedure main;
var i : longint;
begin
//  assign(input,fi);reset(input);
//assign(output,fo);rewrite(output);
  read(n);
  for i := 1 to n do read(t[i] , p[i]);
  for i := 1 to 4*n do tree[i] := oo;
  build(1,1,n);
  update(t[1] , p[1]);
  f[1] := p[1];
  for i := 2 to n do
    begin
      f[i] := get(1,1,n,i-1,n) + p[i];
      update(t[i] , f[i]);
    end;
  writeln(get(1,1,n,n,n));
  //close(input);close(output);
end;
begin
  main;
end.

Chủ đề: Cấu trúc dữ liệu, IT, SPOJ Mức độ: duyen hai, hirehp, IT, spoj

BGMINE – SPOJ

February 9, 2016 by Aida Nana 2 Comments

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

Thuật toán: Theo yêu cầu đề bài thì mình cần tìm một số hang liên tiếp mà có tổng số đá lớn hơn hoặc bằng độ dài các hang và có tổng số vàng lớn nhất đó: Sumr[j] – Sumr[i-1] >= x[j] – x[i] với (j >= i).

Ta biến đổi điều kiện trên thành: Sumr[j] – x[j] >= Sumr[i-1] – x[i] với (j >= i).

Ta sử dụng ctdl BIT để tính nhanh hơn. Ta cần rời rạc hóa giá trị Sumr[i] – x[i] và Sumr[i-1] – x[i] để lưa được trên cây BIT.

ĐPT: O(nlogn)

Code:

Pascal

uses math;
Const
  Fi='';
  Fo='';
  maxn=trunc(1e5)+3;
  oo=trunc(1e9);
var
  g,r,x : array[1..maxn] of longint;
  a  : array[1..2*maxn] of int64;
  cs,b,t : array[0..2*maxn] of longint;
  i,j,n : longint;
  best : int64;
  sr,sg : array[0..maxn] of int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i:=1 to n do read(x[i],g[i],r[i]);
    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;
  begin
    for i:=1 to n do sr[i] := sr[i-1] + r[i];
    for i:=1 to n do sg[i] := sg[i-1] + g[i];
  end;
procedure sub1;
  begin
    for i := 1  to n do
      for j:= i to n do
        begin
          if sr[j] - sr[i-1] >= x[j] - x[i] then
            begin
              best := max(best,sg[j]-sg[i-1]);
            end;
        end;
  end;
procedure roirac;
  var i,hold : longint;
  begin
    for i:=1 to n do a[i] := sr[i]-x[i];
    for i:=1 to n do a[n+i] := sr[i-1]-x[i];
    for i:=1 to 2*n do cs[i] := i;
    qs(1,2*n);
    b[cs[1]]  := 1; hold := 1;
    for i:=2 to 2*n do
      begin
        if a[cs[i]] = a[cs[i-1]] then
          begin
            b[cs[i]] := hold;
          end;
        if a[cs[i]] <> a[cs[i-1]] then
          begin
            inc(hold);
            b[cs[i]] := hold;
          end;
      end;
  end;
procedure update(i,x : longint);
  begin
    while i<=2*n do
      begin
        t[i] := min(t[i],x);
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  var res : longint;
  begin
    res := oo;
    while i>0 do
      begin
        res := min(res,t[i]);
        i := i - i and (-i);
      end;
    exit(res);
  end;
procedure sub2;
  var i,tg : longint;
  begin
    roirac;
    for i := 0 to 2*n+3 do t[i] := oo;
    for i:=1 to n do
      begin
        update(b[n+i],i);
        tg := get(b[i]);
        if tg<>oo then
          begin
            best := max(best, sg[i]-sg[tg-1]);
          end;
      end;
  end;
procedure process;
  begin
    sub2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(best);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.

C++

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;
int x[MAXN], a[MAXN], r[MAXN];
long long sr[MAXN], sx[MAXN], sg[MAXN];
void sub1()
{
    FORE(i, 1, n) sr[i] = sr[i - 1] + r[i];
    FORE(i, 1, n) sx[i] = sx[i - 1] + x[i];
    FORE(i, 1, n) sg[i] = sg[i - 1] + a[i];
    long long ans = 0;
    FORE(i, 1, n) FORE(j, 0, i - 1) if (sr[i] - sr[j] >= x[i] - x[j + 1]){
        ans = max(ans, sg[i] - sg[j]);
        //if (ans == 99) cout<> n;
    FORE(i, 1, n) cin >> x[i] >> a[i] >> r[i];
    if (n <= 5000) sub1();
    else
    sub2();
    return 0;
}

Chủ đề: BIT, Cấu trúc dữ liệu, SPOJ Mức độ: bit, ctdl