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.
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
这题看了别人的题解，最后看懂了。题意是从1~n，一次插入位置，然后每插入一个数求出它的最长递增子序列（不连续）。可以用线段树先求出每个数所在的位置，可以从后往前，因为每次最后一个数的位置一定是固定的。然后就是二分法的lis了，这里如果继续用线段树求lis的话会超时的。
这里二分的lis之前一直看不懂，其实因为输入的数是一次增大的，所以每次只要记录这个数的位置，然后二分找到最接近但大于当前数的位置，然后替换掉找到的数。
这题我对二分又有了新的认识，二分模板不是固定的，而是根据题目意思决定最后返回的值是l还是r.
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
#define maxn 100005
int a[maxn],ans[maxn],dp[maxn];
struct node{
int l,r,n;
}b[4*maxn];
void build(int l,int r,int i)
{
int mid;
b[i].l=l;b[i].r=r;b[i].n=r-l+1;
if(l==r)return;
mid=(l+r)/2;
build(l,mid,i*2);
build(mid+1,r,i*2+1);
}
void update(int index,int m,int i)
{
int mid;
if(b[i].l==b[i].r){
b[i].n=0;ans[m]=b[i].l;return;
}
if(b[i*2].n>=index) update(index,m,i*2);
else update(index-b[i*2].n,m,i*2+1);
b[i].n=b[i*2].n+b[i*2+1].n;
}
int find(int l,int r,int x)
{
int mid;
while(l<=r){
mid=(l+r)/2;
if(dp[mid]>x){
r=mid-1;
}
else l=mid+1;
}
return r+1; //这里也可以是l,可以草稿纸上画一下
}
int main()
{
int n,m,i,j,h,T,k,len; //len表示最长递增子序列
scanf("%d",&T);
for(h=1;h<=T;h++)
{
printf("Case #%d:
",h);
scanf("%d",&n);
for(i=1;i<=n;i++){scanf("%d",&a[i]);dp[i]=0;}
build(1,n,1);
for(i=n;i>=1;i--){
update(a[i]+1,i,1);
}
len=0;
for(i=1;i<=n;i++){
if(len==0){
dp[++len]=ans[1]; //ans[]表示i所在的位置
printf("%d
",len);
continue;
}
k=find(1,len,ans[i]);
len=max(len,k); //不管这n个数排列顺序怎样，每一次的最长递增子序列一定是递增的，可以画一下。
dp[k]=ans[i]; //dp[k]表示最长递增序列中的第k个数，用到了单调队列的思想
printf("%d
",len);
}
printf("
");
}
return 0;
}