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

using namespace std;
//#include<bits/stdc++.h>
#include <algorithm>
#include <stdio.h>
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
 
int n, a[300010], T[300010], c[300010], f[300010], dem;
pair<int, int> 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<<a[i]<<" ";cout<<"=="<<endl;
    //cout<<"????"<<endl;
    FORE(i, 1, n) {
        f[i] = Get(a[i] - 1) + 1;
        Update(a[i], f[i]);
        ans = max(ans, f[i]);
    }
 
    //cout<<ans<<endl;
    printf("%d", ans);
    return 0;
}

using namespace std; //#include<bits/stdc++.h> #include <algorithm> #include <stdio.h> #define FOR(i,a,b) for (long long i=a;i<b;i++) #define FORE(i,a,b) for (long long i=a;i<=b;i++) #define FORD(i,a,b) for (long long i=a;i>=b; i--) int n, a[300010], T[300010], c[300010], f[300010], dem; pair<int, int> 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<<a[i]<<" ";cout<<"=="<<endl; //cout<<"????"<<endl; FORE(i, 1, n) { f[i] = Get(a[i] - 1) + 1; Update(a[i], f[i]); ans = max(ans, f[i]); } //cout<<ans<<endl; printf("%d", ans); return 0; }