Another LIS
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1211 Accepted Submission(s): 424
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 解题：先求出这个序列+排序+LIS。
#include
#include
#include
using namespace std; #define N 100100 typedef struct nnn { int id,i; }point; int tree[3*N]; point oder[N]; void bulide1(int l,int r,int k) { tree[k]=r-l+1; if(l==r)return ; bulide1(l,(l+r)/2,k*2); bulide1((l+r)/2+1,r,k*2+1); } void set_tree1(int l,int r,int k,int id,int i) { int m=(l+r)/2; tree[k]--; if(l==r) { oder[l].id=l; oder[l].i=i; return ; } if(tree[k*2]>=id)set_tree1(l,m,k*2,id,i); else set_tree1(m+1,r,k*2+1,id-tree[k*2],i); } bool cmp(point a,point b){return a.i
tree[k*2+1]) tree[k]=tree[k*2]; else tree[k]=tree[k*2+1]; } int query2(int l,int r,int k,int id) { int m=(l+r)/2; if(l==r)return 0; int max=0; if(m>=id) max=query2(l,m,k*2,id); else { max=query2(m+1,r,k*2+1,id); if(max
0;i--) set_tree1(1,n,1,a[i],i); sort(oder+1,oder+n+1,cmp); bulide2(1,n,1); for(int i=1;i<=n;i++) { int lis=1+query2(1,n,1,oder[i].id); set_tree2(1,n,1,oder[i].id,lis); LIS[i]=tree[1]; } printf("Case #%d:\n",j); for(int i=1;i<=n;i++) printf("%d\n",LIS[i]); printf("\n"); } }