Another LIS

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1244 Accepted Submission(s): 431

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

0 0 2

Sample Output

Case #1:

Hint

In the sample, we add three numbers to the sequence, and form three sequences.
a. 1
b. 2 1
c. 2 1 3

题意：一个空序列，第k次在xk处插入 k，并输出序列当前的LIS。

首先倒序用线段树来确定每个元素最终的位置。然后求n次LIS，当然要用线段树维护了，，或者二分等等也可以。 nlogn

 #include <cstdio>

 #include <string>

 #include <cstdlib>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int maxn = 1e5+;

 int seg[maxn<<],a[maxn];            // seg表示该区间 位置剩余量

 void build (int l,int r,int pos)

 {

     if (l == r)

     {

         seg[pos] = ;

         return;

     }

     int mid = (l + r) >> ;

     build(l,mid,pos<<);

     build(mid+,r,pos<<|);

     seg[pos] = seg[pos<<] + seg[pos<<|];

 }

 int ans[maxn];                            //ans[i]表示 元素i的位置为ans[i]

 void Insert(int l,int r,int pos,int x,int k)

 {

     if (l == r)

     {

         ans[k] = l;

         seg[pos] = ;

         return ;

     }

     int mid = (l + r) >> ;

     if (seg[pos<<] >= x)                            //左孩子的区间 位置剩余量大于x时，递归进入左孩子，否则右孩子同时 x-seg[pos<<1]

         Insert(l,mid,pos<<,x,k);

     else

         Insert(mid+,r,pos<<|,x - seg[pos<<],k);

     seg[pos] = seg[pos<<] + seg[pos<<|];

 }

 void update(int l,int r,int pos,int x,int v)

 {

     if (l == r)

     {

         seg[pos] = v;

         return;

     }

     int mid = (l + r) >> ;

     if (x <= mid)

         update(l,mid,pos<<,x,v);

     else

         update(mid+,r,pos<<|,x,v);

     seg[pos] = max(seg[pos<<],seg[pos<<|]);

 }

 int query(int l,int r,int pos,int ua,int ub)

 {

     if (ua <= l && ub >= r)

     {

         return seg[pos];

     }

     int mid = (l + r) >> ;

     int t1 = ,t2 = ;

     if (ua <= mid)

         t1 = query(l,mid,pos<<,ua,ub);

     if (ub > mid)

         t2 = query(mid+,r,pos<<|,ua,ub);

     return max(t1,t2);

 }

 int main(void)

 {

     #ifndef ONLINE_JUDGE

         freopen("in.txt","r",stdin);

     #endif

     int t,cas = ;

     scanf ("%d",&t);

     while (t--)

     {

         int n;

         scanf ("%d",&n);

         for (int i = ; i <= n; i++)

             scanf ("%d",a+i);

         build (,n,);

         for (int i = n; i >= ; i--)

             Insert(,n,,a[i] + ,i);               //倒序 确定每个元素 最终的位置保存在ans里

         memset(seg,,sizeof(seg));

         printf("Case #%d:\n",cas++);

         for (int i = ; i <= n; i++)

         {

             int t1 = query(,n,,,n);

             int t2 = query(,n,,,ans[i]);

             update(,n,,ans[i],t2+);

             if (t2 < t1)                        //输出当前区间的LIS

                 printf("%d\n",t1);

             else

                 printf("%d\n",+t2);

         }

         printf("\n");

     }

     return ;

 }

巴特西

HDU3564 --- Another LIS （线段树维护最值问题）

Another LIS

最新文章

热门文章