NTSEQ – spoj

Đề 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.pw/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<bits/stdc++.h>
#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<<tmp.sl<<endl;
        update(a[i], f[i], tmp.sl);
    }
	return 0;
}
Khuyên dùng

 

About Aida Nana

Nghề chính là chém gió, quăng bom và ném lựu đạn.
Nghề phụ là cắt cỏ, chém chuối, cưa cây......

Speak Your Mind

*