Another LIS
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 258 Accepted Submission(s): 45
Total Submission(s): 258 Accepted Submission(s): 45
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.
思路：首先我们把所有的位置（1-N)都空出来，记集合S，显然集合S的空位置数目为N个；
第一步：唯一能确定在最终状态下位置的是数值 N；它的位置就是在集合S中第value[n]+1（我的位置是从1-n的）的空位置；然后这个位置p坐下的数值为n，集合S的空位置-1;然后依次类推n-1，它的位置是S集合中第value[n-1]+1个空位置，然后坐下；依次坐下后每个位置上都会有个数值了；这一步用线段树能在nlog(n)时间处理完；
第二步就是裸裸的LIS了，很显然dp[j]>=dp[i](j>i)；
记得第一步跟PKU的某一道题如出一辙！
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100002;
struct Seg
{
int l,r,totnum;
int mid(){return (l+r)>>1;}
};
Seg seg[3*N];
int pos[N],dia[N],dp[N],ans[N];
void maketree(int l,int r,int c)
{
seg[c].l=l;
seg[c].r=r;
seg[c].totnum=r-l+1;
if(l==r) return ;
int mid=seg[c].mid();
maketree(l,mid,c<<1);
maketree(mid+1,r,(c<<1)+1);
}
int finds(int c,int num)
{
if(seg[c].l==seg[c].r)
return seg[c].l;
if(seg[c<<1].totnum<num)
return finds((c<<1)+1,num-seg[c<<1].totnum);
else
return finds(c<<1,num);
}
void del(int c,int p)
{
seg[c].totnum--;
if(seg[c].l==seg[c].r) return ;
int mid=seg[c].mid();
if(p<=mid)
del(c<<1,p);
else
del((c<<1)+1,p);
}
int main()
{
int i,j,n,T,cas,p;
scanf("%d",&T);
for(cas=1;cas<=T;cas++)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&dia[i]);
maketree(1,n,1);
for(i=n;i>=1;i--)
{
p=finds(1,dia[i]+1);
pos[p]=i;
del(1,p);
}
dp[0]=0;
int h=0,l=0,mid,temp,len=0;
printf("Case #%d:/n",cas);
for(i=1;i<=n;i++)
{
temp=pos[i];
l=0,h=len;
while(l<=h)
{
mid=(l+h)>>1;
if(temp>dp[mid])
l=mid+1;
else
h=mid-1;
}
dp[l]=temp;
ans[temp]=l;
if(l>len)
len++;
}
ans[0]=0;
for(i=1;i<=n;i++)
{
if(ans[i]<ans[i-1])
ans[i]=ans[i-1];
printf("%d/n",ans[i]);
}
printf("/n");
}
return 0;
}