codeforces 261D Maxim and Increasing Subsequence dp+树状数组

题目网址：
洛谷

大意：
给你一个数列b，和一个数t，构造出一个数列a为t个数列b组成的数列。
比如：b={3,2,1},t=2;a={3,2,1,3,2,1}。
有k组数据，数列中元素大小为[0,maxb]
求数列a的最长上升子序列(严格单调)。

分析：
观察样例与数据可以知道，当t>=sum时，答案就是sum，其中sum为序列中不同数字的个数，因为是严格单调的。

那么，我们只考虑t＜sum的情况。我们发现n*maxb≤2*10^7的，我们可以发现，这种情况下序列长度就是≤2*10^7，因为sum一定小于maxb。

然后dp，找最大值用树状数组，反正我用线段树TLE了。复杂度还是很恐怖的。在代码里面玄学优化就差不多了= =。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>

const int maxn=1e5+7;

using namespace std;

int k,n,maxb,t,sum,ans,i,j,c;
int a[maxn],b[maxn],tree[maxn],f[maxn];

int lowbit(int x)
{
    return x&(-x);
}

void updata(int x,int c)
{
    while (x<=maxb)
    {
        tree[x]=max(tree[x],c);
        x+=lowbit(x);
    }
}

int get(int x)
{
    int c=0;
    while (x>0)
    {
        c=max(c,tree[x]);
        x-=lowbit(x);
    }
    return c;
}

int main()
{
    scanf("%d%d%d%d",&k,&n,&maxb,&t);
    while (k--)
    {
        sum=0;
        for (i=1;i<=n;i++) 
        {
            scanf("%d",&a[i]);
            if (b[a[i]]!=k+1) sum++;
            b[a[i]]=k+1;
        }
        if (t>=sum)
        {
            printf("%d\n",sum);
            continue;
        }
        ans=0;
        for (i=1;i<=maxn;i++) 
        {
            tree[i]=0;  
            f[i]=0;
        }       
        for (i=1;i<=t;i++)
           for (j=1;j<=n;j++)
           {
                c=get(a[j]-1)+1;
                if (c>f[j])
                {
                    f[j]=c;
                    ans=max(ans,c);
                    updata(a[j],c);//能修改才修改
                }
                if (ans>=sum) break;//因为答案最大是sum，等于sum时可以退出
           }
        printf("%d\n",ans);
    }
}