设$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
原文：https://www.cnblogs.com/Khada-Jhin/p/10441696.html