自动搬运

查看原文

来自洛谷，原作者为

	我是PG **

搬运于2025-08-24 21:58:49，当前版本为作者最后更新于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;
}

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