[Codeforces261D]Maxim and Increasing Subsequence—

题目链接：

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxbn\le210^7,t\le10^9$。

设$b$中不同数的个数为$sum$。如果$sum\le t$，那么答案就是$sum$(只需要从第$i$个序列$b$中取第$i$小的数即可)。现在只需要考虑$t<sum$的情况，因为$sum\le maxb$，所以$t<maxb$，这也就说明$n*t<n*maxb=2*10^7$，那么序列长度最大为$2*10^7$，我们只需要$O(nlog_{n})$求序列的最长上升子序列即可。直接$DP$，$f[i]$表示前$i$个数的最长上升子序列长度，用树状数组存前缀最大值然后扫一遍整个序列$DP$即可。

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

int sum;

int n,t,k;

int b[100010];

int a[20000010];

int v[100010];

int ans;

int maxb;

int f[20000010];

map<int,int>mp;

void add(int x,int k)

{

	for(int i=x;i<=maxb;i+=i&-i)

	{

		v[i]=max(v[i],k);

	}

}

int ask(int x)

{

	int res=0;

	for(int i=x;i;i-=i&-i)

	{

		res=max(res,v[i]);

	}

	return res;

}

int main()

{

	scanf("%d%d%d%d",&k,&n,&maxb,&t);

	while(k--)

	{

		memset(v,0,sizeof(v));

		mp.clear();

		sum=0;

		ans=0;

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

		{

			scanf("%d",&b[i]);

			if(!mp[b[i]])

			{

				sum++;

				mp[b[i]]=1;

			}

		}

		if(t>=sum)

		{

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

			continue;

		}

		for(int i=1;i<=n*t;i++)

		{

			a[i]=b[(i-1)%n+1];

		}

		for(int i=1;i<=n*t;i++)

		{

			f[i]=ask(a[i]-1)+1;

			ans=max(ans,f[i]);

			add(a[i],f[i]);

		}

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

	}

}

巴特西

[Codeforces261D]Maxim and Increasing Subsequence——树状数组+DP

题目链接：

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxbn\le210^7,t\le10^9$。

最新文章

热门文章

巴特西

[Codeforces261D]Maxim and Increasing Subsequence——树状数组+DP

题目链接：

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxb*n\le2*10^7,t\le10^9$。

最新文章

热门文章

题目大意：$k$次询问，每次给出一个长度为$n$的序列$b$及$b$中的最大值$maxb$，构造出序列$a$为$t$个序列$b$连接而成，求$a$的最长上升子序列。$n,maxb\le10^5,maxbn\le210^7,t\le10^9$。