hdu_5748_Bellovin(LIS)

题意：

给你一个数列ai，设f(a₁,a₂,a₃,..a_n)=(f₁,f₂,f₃,...,f_n),其中f_i表示以a_i结尾的最长递增子序列长度，注意：必须要包括a_i，当时就是被这里坑了，这^TM也太坑爹了

题解：

直接上nlog_n的LIS算法，记录一下位置就行了

 1 #include<map>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<queue>
 5 #include<vector>
 6 #include<string>
 7 #include<cstring>
 8 #include<algorithm>
 9 #include<functional>
10 #define pb push_back
11 #define ls l,m,rt<<1
12 #define rs m+1,r,rt<<1|1
13 #define mst(a,b) memset(a,b,sizeof(a))
14 #define F(i,a,b) for(int i=a;i<=b;++i)
15 #define ___ freopen("c:\acm\input.txt","r",stdin);
16 using namespace std;
17 typedef long long LL;
18 
19 int n,a[100010],ans[100010];
20 
21 int main(){
22     int t;
23     scanf("%d",&t);
24     while(t--)
25     {
26         int len=1,tp;
27         scanf("%d%d",&n,&tp);
28         a[1]=tp,ans[1]=1;
29         F(i,2,n)
30         {
31             scanf("%d",&tp);
32             if(a[len]<tp)a[++len]=tp,ans[i]=len;
33             else {
34                 int pos=lower_bound(a+1,a+1+len,tp)-a;
35                 a[pos]=tp,ans[i]=pos;
36             }
37         }
38         F(i,1,n)printf("%d%c",ans[i],i==n?'
':' ');
39     }
40     return 0;
41 }

View Code