51nod-1134 最长递增子序列，用线段树将N^2的dp降到NlogN

给出长度为N的数组，找出这个数组的最长递增子序列。(递增子序列是指，子序列的元素是递增的）

例如：5 1 6 8 2 4 5 10，最长递增子序列是1 2 4 5 10。

Input

第1行：1个数N，N为序列的长度(2 <= N <= 50000)

第2 - N + 1行：每行1个数，对应序列的元素(-10^9 <= S[i] <= 10^9)

Output

输出最长递增子序列的长度。

--------------------------------------------------------------------------------------------------------------

很容易想到N^2的做法，F[i] = max{F[j],0<=j<i且Aj<Ai} + 1。

但是N有5w，N^2肯定过不了。

于是写了个线段树，维护区间最大值。求F[i]时只需一次查询和一次更新。

具体做法为：

1，离散化

2，建树

3, 查询和更新

for i = 0...N

int tmp = query(1,A[i]-1) + 1; //查询1~A[i]-1之间的最大值。

ans = max{ans,tmp};

update(A[i],tmp); //更新A[i]经过的区间。

end for

#define  _CRT_SECURE_NO_WARNINGS

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <map>

using namespace std;

const int N = ;

int A[N], B[N];

int Cnt; map<int, int> mapper;

struct Node{

    int l,r;

    int maxv;

    Node(){ maxv = ; }

    int mid(){ return (l + r) >> ; }

};

Node segtree[N*];

void build(int id, int l, int r){

    segtree[id].l = l;

    segtree[id].r = r;

    if(l==r) return;

    int mid = segtree[id].mid();

    build(id*+,l,mid);

    build(id*+,mid+,r);

}

void update(int id, int pos, int val){

    segtree[id].maxv = std::max(segtree[id].maxv, val);

    if(segtree[id].l==segtree[id].r) return;

    int mid=segtree[id].mid();

    if(pos<=mid)

        update(id*+,pos,val);

    else update(id*+,pos,val);

}

int query(int id,int l,int r){

    if(segtree[id].l==l&&segtree[id].r==r)

        return segtree[id].maxv;

    int mid = segtree[id].mid();

    if(l>mid) return query(id*+,l,r);

    if(r<=mid) return query(id*+,l,r);

    return std::max(query(id*,l,mid),query(id*+,mid+,r));

}

int main(){

    int n; cin>>n;

    for(int i=;i<n;i++) scanf("%d",A+i);

    memcpy(B,A,sizeof(int)*n);

    std::sort(B,B+n);

    Cnt = std::unique(B,B+n)-B;

    for(int i=;i<Cnt;i++) mapper[B[i]]=i+;

    for(int i=;i<n;i++) A[i]=mapper[A[i]];

    build(,,Cnt+);

    int ans = ;

    for(int i=;i<n;i++){

        int tmp = query(,,A[i]-)+;

        ans = std::max(ans, tmp);

        update(,A[i],tmp);

    }

    printf("%d\n",ans);

    return ;

}

巴特西

51nod-1134 最长递增子序列，用线段树将N^2的dp降到NlogN

最新文章

热门文章