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

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

 1 #include <cstdio>
 2 #include <string>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 1e5+10;
 8 int seg[maxn<<2],a[maxn];            // seg表示该区间 位置剩余量
 9 void build (int l,int r,int pos)
10 {
11     if (l == r)
12     {
13         seg[pos] = 1;
14         return;
15     }
16     int mid = (l + r) >> 1;
17     build(l,mid,pos<<1);
18     build(mid+1,r,pos<<1|1);
19     seg[pos] = seg[pos<<1] + seg[pos<<1|1];
20 }
21 int ans[maxn];                            //ans[i]表示 元素i的位置为ans[i]
22 void Insert(int l,int r,int pos,int x,int k)
23 {
24     if (l == r)
25     {
26         ans[k] = l;
27         seg[pos] = 0;
28         return ;
29     }
30     int mid = (l + r) >> 1;
31     if (seg[pos<<1] >= x)                            //左孩子的区间 位置剩余量大于x时，递归进入左孩子，否则右孩子同时 x-seg[pos<<1]
32         Insert(l,mid,pos<<1,x,k);
33     else
34         Insert(mid+1,r,pos<<1|1,x - seg[pos<<1],k);
35     seg[pos] = seg[pos<<1] + seg[pos<<1|1];
36 }
37 void update(int l,int r,int pos,int x,int v)
38 {
39     if (l == r)
40     {
41         seg[pos] = v;
42         return;
43     }
44     int mid = (l + r) >> 1;
45     if (x <= mid)
46         update(l,mid,pos<<1,x,v);
47     else
48         update(mid+1,r,pos<<1|1,x,v);
49     seg[pos] = max(seg[pos<<1],seg[pos<<1|1]);
50 }
51 int query(int l,int r,int pos,int ua,int ub)
52 {
53     if (ua <= l && ub >= r)
54     {
55         return seg[pos];
56     }
57     int mid = (l + r) >> 1;
58     int t1 = 0,t2 = 0;
59     if (ua <= mid)
60         t1 = query(l,mid,pos<<1,ua,ub);
61     if (ub > mid)
62         t2 = query(mid+1,r,pos<<1|1,ua,ub);
63     return max(t1,t2);
64 }
65 
66 int main(void)
67 {
68     #ifndef ONLINE_JUDGE
69         freopen("in.txt","r",stdin);
70     #endif
71     int t,cas = 1;
72     scanf ("%d",&t);
73     while (t--)
74     {
75         int n;
76         scanf ("%d",&n);
77         for (int i = 1; i <= n; i++)
78             scanf ("%d",a+i);
79         build (1,n,1);
80         for (int i = n; i >= 1; i--)
81             Insert(1,n,1,a[i] + 1,i);               //倒序 确定每个元素 最终的位置保存在ans里
82         memset(seg,0,sizeof(seg));
83         printf("Case #%d:
",cas++);
84         for (int i = 1; i <= n; i++)
85         {
86             int t1 = query(1,n,1,1,n);
87             int t2 = query(1,n,1,1,ans[i]);
88             update(1,n,1,ans[i],t2+1);
89             if (t2 < t1)                        //输出当前区间的LIS
90                 printf("%d
",t1);
91             else
92                 printf("%d
",1+t2);
93         }
94         printf("
");
95     }
96     return 0;
97 }