題面：

3173: [Tjoi2013]最長上升子序列

Time Limit:?10 Sec??Memory Limit:?128 MB
Submit:?2108??Solved:?1067
[Submit][Status][Discuss]

Description

給定一個序列，初始為空?，F在我們將1到N的數字插入到序列中，每次將一個數字插入到一個特定的位置。每插入一個數字，我們都想知道此時最長上升子序列長度是多少？

Input

第一行一個整數N，表示我們要將1到N插入序列中，接下是N個數字，第k個數字Xk，表示我們將k插入到位置Xk（0<=Xk<=k-1,1<=k<=N）

Output

N行，第i行表示i插入Xi位置后序列的最長上升子序列的長度是多少。

Sample Input

3
0 0 2

Sample Output

1
1
2

HINT

100%的數據 n<=100000

?

既然插入的數從小到大,我們就可以搞出最終的序列求LIS。

ans[i]=max{f[j],(1<=j<=i)},f[i]表示插入i后以i為結尾LIS長度。

只要求出最終序列問題就解決了。

可以用平衡樹(Treap或Splay)

但是轉化為前綴k小后就可以用樹狀數組求辣！(樹狀數組求k小值?)

1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 #include <math.h> 6 using namespace std; 7 #define maxn 100001 8 #define lowbit(x) (x&(-x)) 9 template<typename __> 10 inline void read(__ &s) 11 { 12 char ch; 13 for(ch=getchar(),s=0;ch<'0'||ch>'9';ch=getchar()); 14 for(;ch>='0'&&ch<='9';s=s*10+ch-'0',ch=getchar()); 15 } 16 int n; 17 class fenwick 18 { 19 public: 20 int c[maxn]; 21 void update_sum(int x,int val) 22 { 23 for(;x<=n;x+=lowbit(x)) 24 c[x]+=val; 25 } 26 void update_max(int x,int val) 27 { 28 for(;x<=n;x+=lowbit(x)) 29 c[x]=max(c[x],val); 30 } 31 int query_kth(int k) 32 { 33 int cnt=0,ans=0; 34 for(int i=17;i>=0;i--) 35 { 36 ans+=(1<<i); 37 if(ans>=n||cnt+c[ans]>=k) 38 ans-=(1<<i); 39 else 40 cnt+=c[ans]; 41 } 42 return ans+1; 43 } 44 int query_max(int x) 45 { 46 int ans=0; 47 for(;x;x-=lowbit(x)) 48 ans=max(ans,c[x]); 49 return ans; 50 } 51 }T; 52 int QWQ[maxn],QAQ[maxn],f[maxn]; 53 int main() 54 { 55 read(n); 56 for(int i=1;i<=n;i++) 57 { 58 read(QWQ[i]); 59 ++T.c[i]; 60 if((i+lowbit(i))<=n) 61 T.c[i+lowbit(i)]+=T.c[i]; 62 } 63 int tmp; 64 for(int i=n;i>=1;i--) 65 { 66 QAQ[tmp=T.query_kth(QWQ[i]+1)]=i; 67 T.update_sum(tmp,-1); 68 } 69 memset(T.c,0,sizeof(T.c)); 70 for(int i=1;i<=n;i++) 71 { 72 f[QAQ[i]]=T.query_max(QAQ[i])+1; 73 T.update_max(QAQ[i],f[QAQ[i]]); 74 } 75 for(int i=1;i<=n;i++) 76 printf("%d\n",f[i]<f[i-1]?(f[i]=f[i-1]):f[i]); 77 } BZOJ 3173

?

轉載于:https://www.cnblogs.com/radioteletscope/p/7762177.html

總結

以上是生活随笔為你收集整理的BZOJ3173 [TJOI2013]最长上升子序列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。