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.
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 2HintIn 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
解题：先求出这个序列+排序+LIS。
#include<stdio.h>
#include<algorithm>
#include<iostream>
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<b.i;}
void bulide2(int l,int r,int k)
{
tree[k]=0;
if(l==r)return ;
bulide2(l,(l+r)/2,k*2);
bulide2((l+r)/2+1,r,k*2+1);
}
void set_tree2(int l,int r,int k,int id,int lis)
{
int m=(l+r)/2;
if(l==r)
{
if(tree[k]<lis) tree[k]=lis; return ;
}
if(id<=m)set_tree2(l,m,k*2,id,lis);
else set_tree2(m+1,r,k*2+1,id,lis);
if(tree[k*2]>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<tree[k*2]) max=tree[k*2];//左边的数一定比当前数小，因为排了个序从小到大排
}
return max;
}
int main()
{
int a[N+5],LIS[N+5],m,n;
scanf("%d",&m);
for(int j=1;j<=m;j++)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]); a[i]++;
}
bulide1(1,n,1);
for(int i=n;i>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");
}
}