NKLINEUP – spoj

Đề bài:

Thuật toán:

  • Interval tree

Code:

#include <bits/stdc++.h>
using namespace std;
 
int n,q;
vector<int> a;
vector< pair<int,int> > node;
int resmax, resmin;
 
void Init_Tree(int k, int l, int r, int i)
{
    if(l>i || r<i) return;
    if(l==r)
    {
        node[k]=make_pair(a[i],a[i]);
        return;
    }
    int m=(l+r)/2;
    Init_Tree(2*k,l,m,i);
    Init_Tree(2*k+1,m+1,r,i);
    node[k]=make_pair(max(node[2*k].first, node[2*k+1].first),min(node[2*k].second, node[2*k+1].second));
}
 
void Init()
{
    scanf("%d%d",&n,&q);
    a.resize(n+2);
    node.resize(4*n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        Init_Tree(1,1,n,i);
    }
}
 
void Query(int k, int l, int r, int A, int B)
{
    if(l>B || r<A) return;
    if(A<=l && B>=r)
    {
        resmax=max(resmax,node[k].first);
        resmin=min(resmin,node[k].second);
        return;
    }
    int m=(l+r)/2;
    Query(2*k,l,m,A,B);
    Query(2*k+1,m+1,r,A,B);
}
 
void Solve()
{
    for (int i=1;i<=q;i++)
    {
        int A, B;
        scanf("%d%d",&A,&B);
        resmax=0;
        resmin=10000000;
        Query(1,1,n,A,B);
        printf("%dn",resmax-resmin);
    }
}
 
int main()
{
    Init();
    Solve();
}
uses    math;
const   fi='';
        fo='';
        maxn=50000;
        maxq=200000;
type    arrp=record
                dau:longint;
                cuoi:longint;
                end;
var     i,j,n,q:longint;
        f:text;
        res1,res2:longint;
        a:array[1..maxn] of longint;
        p:array[1..maxq] of arrp;
        mind,maxd:array[1..maxn*4] of longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n,q);
    for i:=1 to n do readln(f,a[i]);
    for i:=1 to q do readln(f,p[i].dau,p[i].cuoi);
    close(f);
end;
procedure update(k,l,r:longint);
var     mid:longint;
begin
    if l=r then
    begin
        maxd[k]:=a[l];
        mind[k]:=a[l];
    end
    else
    begin
        mid:=(l+r) div 2;
        update(k*2,l,mid);
        update(k*2+1,mid+1,r);
        mind[k]:=min(mind[k*2],mind[k*2+1]);
        maxd[k]:=max(maxd[k*2],maxd[k*2+1]);
    end;
end;
procedure find(k,l,r:longint);
var     mid:longint;
begin
    if (l>j) or (r<i) then exit;
    if (i<=l) and (j>=r) then
    begin
        res1:=min(res1,mind[k]);
        res2:=max(res2,maxd[k]);
        exit;
    end;
    mid:=(l+r) div 2;
    find(k*2,l,mid);
    find(k*2+1,mid+1,r);
end;
procedure xuat;
var     k:longint;
begin
    assign(f,fo);
    rewrite(f);
    update(1,1,n);
    for k:=1 to q do
    begin
        res1:=high(longint);
        res2:=0;
        i:=p[k].dau;
        j:=p[k].cuoi;
        find(1,1,n);
        writeln(f,res2-res1);
    end;
    close(f);
end;
begin
    nhap;
    xuat;
end.

QMAX – spoj

Đề bài:

Thuật toán:

it - yeulaptrinh.pw

  • Đây là bài thuần sử dụng cấu trúc dữ liệu IT. Các bạn có thể tham khảo thêm tại: http://adf.ly/1f54AI

Code:

uses    math;
const   fi='';
        fo='';
        maxn=100000;
        oo      =2*trunc(1e10);
var     a       :array[0..maxn] of int64;
        i,j,n,p,q,m :longint;
        t       :array[1..4*maxn] of int64;
        res     :int64;
procedure enter;
var     u,v,k   :longint;
begin
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,k);
                        a[u] := a[u]+ k;
                        a[v+1] := a[v+1] -k;
                end;
        for i:=1 to n do
                a[i] := a[i-1] +a[i];
end;
procedure update(k,l,r:longint);
var     m :longint;
begin
        if l=r then
                begin
                        t[k] := a[l];
                        exit;
                end;
        m := (l+r) div 2;
        update(k*2,l,m);
        update(k*2+1,m+1,r);
        t[k] := max(t[k*2],t[k*2+1]);
end;
procedure find(k,l,r,i,j:longint);
var     m :longint;
begin
	if (i>r) or (j<l) then exit;
        if (i<=l) and (r<=j) then
                begin
                        res := max(t[k],res);
                        exit;
                end;
        m := (l+r) div 2;
        find(k*2,l,m,i,j);
        find(k*2+1,m+1,r,i,j);
end;
procedure process;
begin
        update(1,1,n);
end;
procedure print;
var     u,v     :longint;
	i	:longint;
begin
        read(q);
        for i:=1 to q do
          begin
                read(u,v);
                res := -oo;
                find(1,1,n,u,v);
                writeln(res);
          end;
end;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
        enter;
        process;
        print;
close(input);close(output);
end.

VOMARIO – SPOJ

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

Thuận toán: Sử dụng Interval Tree để quản lí tập các đoạn thẳng. Có thể dễ dàng tìm được công thức QHĐ O(N^2) với F(i) = số năng lượng max đến lượt chơi thứ i. Để giảm độ phức tạp thì có thể dùng IT để cập nhật nhanh.

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 2;
const int INF = 1e9 + 7;
 
using namespace std;
int n;
long long x[MAXN], w[MAXN], e[MAXN], a[MAXN], v[MAXN], b[MAXN];
long long f[MAXN];
struct line{
    long long a, b;
} it[MAXN * 4];
long long Get(line d, long long pos)
{
    return d.a * v[pos] + d.b;
}
 
long long query(int x, int l, int r, long long pos)
{
    //cout << it[x].a<<" "<<it[x].b<<" :"<<l<<" "<<r<<endl;
    if (pos < l || pos > r) return 0;
    long long ans = Get(it[x], pos);
    if (l == r) return ans;
    int mid = (l + r) / 2;
    ans = max(ans, query(2 * x, l, mid, pos));
    ans = max(ans, query(2 * x + 1, mid + 1, r, pos));
    return ans;
}
 
void update(int x, int l, int r, int u, int v, line val)
{
    int mid = (l + r) / 2;
    if (r < u || v < l) return;
    if (u <= l && r <= v){
    // do something
    if (Get(it[x], l) >= Get(val, l) && Get(it[x], r) >= Get(val, r)){
        return;
    }
    if (Get(it[x], l) <= Get(val, l) && Get(it[x], r) <= Get(val, r)){
        it[x] = val;
        return;
    }
    if (Get(it[x], l) >= Get(val, l) && Get(it[x], mid) >= Get(val, mid)){
        update(2 * x + 1, mid + 1, r, u, v, val);
        return;
    }
    if (Get(it[x], l) <= Get(val, l) && Get(it[x], mid) <= Get(val, mid)){
        update(2 * x + 1, mid + 1, r, u, v, it[x]);
        it[x] = val;
        return;
    }
    if (Get(it[x], mid + 1) >= Get(val, mid + 1) && Get(it[x], r) >= Get(val, r)){
        update(2 * x, l, mid, u, v, val);
        return;
    }
    if (Get(it[x], mid + 1) <= Get(val, mid + 1) && Get(it[x], r) <= Get(val, r)){
        update(2 * x, l, mid, u, v, it[x]);
        it[x] = val;
        return;
    }
    }
    update(2 * x, l, mid, u, v, val);
    update(2 * x + 1, mid + 1, r, u, v, val);
}
 
map<long long, long long> M;
long long pos[MAXN];
 
void trau()
{
    f[0] = 0;
    FORE(i, 1, n) FORE(j, 0, i - 1) if (f[j] >= w[j] * abs(x[i] - x[j]))
            f[i] = max(f[i], f[j] - w[j] * abs(x[i] - x[j]) + e[i]);
    cout << f[n] << endl;
    //FORE(i, 1, n) cout << f[i]<<" ";cout<<endl;
    memset(f, 0, sizeof(f));
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("VOMARIO.inp", "r", stdin);
    freopen("VOMARIO.out", "w", stdout);
    #endif //YEULAPTRINH.PW
    cin >> n;
    FORE(i, 1, n){
        cin >> x[i] >> w[i] >> e[i];
        a[i] = x[i];
    }
    //trau();
    sort(a, a + n + 1);
 
    FORE(i, 0, n) b[i] = lower_bound(a, a + n + 1, x[i]) - a;
    FORE(i, 0, n) v[b[i]] = x[i], M[x[i]] = b[i];
    FORE(i, 0, n) pos[i] = M[a[i]];
    int top = *max_element(b, b + n + 1);
    FORE(i, 1, MAXN * 4 - 1) it[i].a = 0, it[i].b = 0;
    update(1, 0, top, 0, top, (line){0, 0});
    //FORE(i, 1, n + 1) cout << b[i] <<" "<<v[b[i]]<<endl;
    //FORE(i, 1, n + 1) cout<<a[i]<<" ";cout<<endl;
    //b[0] = b[n + 1];
/*
    update(1, 0, top, 0, 2, (line){-1, -1});
    update(1, 0, top, 0, 0, (line){1, 9});
    update(1, 0, top, 5, 5, (line){-4, 26});
    update(1, 0, top, 5, 5, (line){4, -6});
    cout << top << endl;
    cout << query(1, 0, top, 2)<<"wtf"<<endl;
    */
    //FORE(i, 0, n) cout << a[i]<<" ";cout<<endl;
    //FORE(i, 0, n) cout << b[i]<<" ";cout<<endl;
    long long ans = 0;
    FORE(i, 1, n){
        f[i] = query(1, 0, top, b[i]) + e[i];
        ans = max(ans, f[i]);
        long long l, r;
        if (w[i] == 0) r = top, l = 0;
        else{
            //if (i == 2) cout << (x[i] + f[i] / w[i])<<"wtf"<<endl;
            r = upper_bound(a, a + n + 1, x[i] + f[i] / w[i]) - a - 1;
            //cout << x[i] + f[i] / w[i]<<"???"<<r<<"<<<<<"<<b[r]<<endl;
            r = pos[r];
            l = lower_bound(a, a + n + 1, x[i] - f[i] / w[i]) - a;
            l = pos[l];
 
            //cout <<l<<" "<<r<<endl;
        }
        long long mid = b[i];
        update(1, 0, top, mid, r, (line){-w[i], f[i] + w[i] * x[i]});
        update(1, 0, top, l, mid, (line){w[i],  f[i] - w[i] * x[i]});
        //cout<<i<<"=+"<<b[i]<<"??"<<f[i]<<endl;
        //cout << mid <<" "<<r<<"line"<<-w[i]<<" "<<f[i] + w[i] * x[i]<<endl;
        //cout << l <<" "<<mid<<"line"<<w[i]<<" "<<f[i] - w[i] * x[i]<<endl;
    }
    cout << ans;
 
    return 0;
}

HIREHP – SPOJ

Đề bài:

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<l) then exit(oo);
    if (i<=l) and (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.