题解 P4309 【[TJOI2013]最长上升子序列】

我是PG · 2018-12-11 22:19:50 · 题解

有很多巨佬用什么rope，线段树，splay等高级（掉头发）数据结构，蒟蒻只能来一篇vector加树状数组的题解

#include<bits/stdc++.h>
int ans[1000001],n,tree[1000001];
std::vector<int>a;
inline void update(int x,int val){while(x<=n)tree[x]=std::max(tree[x],val),x+=x&-x;}
inline int query(int x){
    int t=0;
    while(x)t=std::max(t,tree[x]),x-=x&-x;
    return t;
}
int main(){
    scanf("%d",&n);
    for(register int i=1,t;i<=n;++i)scanf("%d",&t),a.insert(t+a.begin(),i);
    for(register int i=0,t;i<n;++i)t=a[i],update(t,ans[t]=query(t)+1);
    for(register int i=1;i<=n;++i)printf("%d\n",ans[i]=std::max(ans[i],ans[i-1]));
    return 0;
}

我想应该是最短最简单的题解了吧