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

Đề bài:

• http://vn.spoj.com/problems/LIQ/
• http://vn.spoj.com/problems/LIS/

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<