Another LIS
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1291 Accepted Submission(s): 451
Problem Description There is a sequence firstly empty. We begin to add number from 1 to N to the sequence, and every time we just add a single number to the sequence at a specific position. Now, we want to know length of the LIS (Longest Increasing Subsequence) after every time's add.
Input An integer T (T <= 10), indicating there are T test cases.
For every test case, an integer N (1 <= N <= 100000) comes first, then there are N numbers, the k-th number Xk means that we add number k at position Xk (0 <= Xk <= k-1).See hint for more details.
Output For the k-th test case, first output Case #k: in a separate line, then followed N lines indicating the answer. Output a blank line after every test case.
Sample Input
1
3
0 0 2
Sample Output
Case #1:
1
1
2
Hint
In the sample, we add three numbers to the sequence, and form three sequences.
a. 1
b. 2 1
c. 2 1 3
Author standy
Source 2010 ACM-ICPC Multi-University Training Contest（13）——Host by UESTC
Recommend zhouzeyong | We have carefully selected several similar problems for you: 3572 2389 3584 3293 1255 思路：就是从左插入找空位，从1~n用线段树记录他们的位置，然后再对他们的位置进行LIS就好 ac代码
#include
#include
#define max(a,b) (a>b?a:b) int a[100010]; int node[100010<<2],d[100010],len,dp[100010]; void build(int l,int r,int tr) { node[tr]=r-l+1; if(l==r) return; int mid=(l+r)>>1; build(l,mid,tr<<1); build(mid+1,r,tr<<1|1); node[tr]=node[tr<<1]+node[tr<<1|1]; } int bin(int x) { int l=1,r=len; while(l<=r) { int mid=(l+r)>>1; if(x>dp[mid]) l=mid+1; else r=mid-1; } return l; } void insert(int pos,int num,int l,int r,int tr) { if(l==r) { d[num]=l; node[tr]=0; return; } int mid=(l+r)>>1; node[tr]--; if(pos<=node[tr<<1]) { insert(pos,num,l,mid,tr<<1); } else insert(pos-node[tr<<1],num,mid+1,r,tr<<1|1); } int main() { int t,c=0; scanf(%d,&t); while(t--) { int n; scanf(%d,&n); int i; for(i=1;i<=n;i++) { scanf(%d,&a[i]); dp[i]=0; } build(1,n,1); for(i=n;i>0;i--) { insert(a[i]+1,i,1,n,1); } len=0; /*for(i=1;i<=n;i++) { printf(%d ,d[i]); }*/ printf(Case #%d: ,++c); for(i=1;i<=n;i++) { int k=bin(d[i]); len=max(len,k); dp[k]=d[i]; printf(%d ,len); } printf( ); } }
?