【洛谷P4309】最长上升子序列

题目大意：给定一个序列，初始为空。现在我们将 1 到 N 的数字插入到序列中，每次将一个数字插入到一个特定的位置。每插入一个数字，我们都想知道此时最长上升子序列长度是多少？

题解：学会了 rope 操作。

由于是从小到大插入元素，发现当前插入 i 时，对前 i-1 个元素的答案没有影响，即：后续插入对之前的答案不造成影响，因此可以离线操作。

现在瓶颈在于如何快速构建出最终的序列形态，即：需要一种可以支持快速插入的数据结构。

这里采用 C++ 自带的数据结构 rope，插入元素到指定位置的时间复杂度为 \(O(\sqrt n)\)，用法为 insert(pos, val)，下标从 0 开始。

最后，可以利用树状数组求出以每个元素结尾的最长上升子序列的长度，输出答案时取前缀 max 即可。

代码如下

#include <bits/stdc++.h>

#include <ext/rope>

using namespace std;

using namespace __gnu_cxx;

const int maxn=1e5+10;

rope<int> t;

int n,bit[maxn],ans[maxn];

void modify(int pos,int val){

	for(int i=pos;i<=n;i+=i&-i)bit[i]=max(bit[i],val);

}

int query(int pos){

	int ret=0;

	for(int i=pos;i;i-=i&-i)ret=max(ret,bit[i]);

	return ret;

}

int main(){

	scanf("%d",&n);

	for(int i=1,pos;i<=n;i++){

		scanf("%d",&pos);

		t.insert(pos,i);

	}

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

		int x=t[i];

		ans[x]=query(x-1)+1;

		modify(x,ans[x]);

	}

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

		ans[i]=max(ans[i],ans[i-1]);

		printf("%d\n",ans[i]);

	}

	return 0;

}

巴特西

【洛谷P4309】最长上升子序列

最新文章

热门文章