51 nod 1376は、最も長くサブシーケンスの数をインクリメントする(dp、CDQ分割124 BIT).

10916 ワード
ダイナミック？プログラム データ構造 思考 を選択します。 分割支配 cdq分割
件名:
N≦5×104のシーケンス、0≦Ai≦109、LISの数を求めます.
分析:
f[i]:i番目の数で終るLISの長さと、その長さのLISの数で移行すると、明らかにf[i].first=max｛f[j].first｝＋1,jコード:
//
//  Created by TaoSama on 2016-02-16
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, a[N];

using P = pair<int, int>;

void getMax(P& x, P y) {
    if(x.first < y.first) x = y;
    else if(x.first == y.first) {
        if((x.second += y.second) >= MOD)
            x.second -= MOD;
    }
}

struct BIT {
    int n; P b[N];
    void init(int _n) {
        n = _n;
        for(int i = 1; i <= n; ++i) b[i] = P(0, 0);
    }
    void add(int i, P v) {
        for(; i <= n; i += i & -i) getMax(b[i], v);
    }
    P sum(int i) {
        P ret(0, 1);
        for(; i; i -= i & -i) getMax(ret, b[i]);
        return ret;
    }
} bit;

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    scanf("%d", &n);
    vector<int> xs;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        xs.push_back(a[i]);
    }
    sort(xs.begin(), xs.end());
    xs.resize(unique(xs.begin(), xs.end()) - xs.begin());
    bit.init(xs.size());

    P ans(0, 0);
    for(int i = 1; i <= n; ++i) {
        int x = lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin() + 1;
        P cur = bit.sum(x - 1);
        ++cur.first;
        getMax(ans, cur);
        bit.add(x, cur);
    }
    printf("%d
", ans.second);

    return 0;
}
もちろん、これは二次元偏順の問題です.一次元の下標記で、二次元の値は直接cdqで分割すればいいです.複雑度が多く、logはOです.同じようなテクニックがあることを避けるために、間隔を並べ替えるのが機転がよくて、質問になるかもしれないのは第一位になりました.
コード:
//
//  Created by TaoSama on 2016-02-16
//  Copyright (c) 2016 TaoSama. All rights reserved.
//
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, a[N];

using P = pair<int, int>;

P f[N]; //LIS length, count

void getMax(P& x, P y) {
    if(x.first < y.first) x = y;
    else if(x.first == y.first) {
        if((x.second += y.second) >= MOD)
            x.second -= MOD;
    }
}

int id[N];
bool cmp(int x, int y) {
    if(a[x] != a[y]) return a[x] < a[y];
    return x > y;
}

void cdq(int l, int r) {
    if(l == r) return;

    int m = l + r >> 1;
    cdq(l, m);

    for(int i = l; i <= r; ++i) id[i] = i;
    sort(id + l, id + r + 1, cmp);

    P maxf(0, 0);
    for(int i = l; i <= r; ++i) {
        int idx = id[i];
        if(idx <= m) getMax(maxf, f[idx]);
        else {
            P cur = maxf;
            ++cur.first;
            getMax(f[idx], cur);
        }
    }
    cdq(m + 1, r);
}

int main() {
#ifdef LOCAL
    freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
//  freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", a + i);

    for(int i = 1; i <= n; ++i) f[i] = P(1, 1);
    cdq(1, n);

    P ans(0, 0);
    for(int i = 1; i <= n; ++i) getMax(ans, f[i]);
    printf("%d
", ans.second);

    return 0;
}
2018-2019 ACM-ICPC Pacific Northwest Regional Conteest(Div.1)題解