18.10.9 不好做的最长上升子序列（nlogn树状数组解LIS）

发布时间：2020-12-14 04:19:41 所属栏目：大数据来源：网络整理

导读：描述一个数的序列 b i ，当 b 1 ?? b 2 ? ... ? b S 的时候，我们称这个序列是上升的。对于给定的一个序列( a 1 ,? a 2 ,...,? a N )，我们可以得到一些上升的子序列( a i 1 ,? a i 2 ,? a i K )，这里1 =? i 1 ?? i 2 ? ... ? i K ?= N。比如，对于序列(1,

描述

一个数的序列b_i，当b₁?<?b₂?< ... <?b_S的时候，我们称这个序列是上升的。对于给定的一个序列(a₁,?a₂,...,?a_N)，我们可以得到一些上升的子序列(a_i₁,?a_i₂,?a_{i_K})，这里1 <=?i₁?<?i₂?< ... <?i_K?<= N。比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,8)等等。这些子序列中最长的长度是4，比如子序列(1,8).

你的任务，就是对于给定的序列，求出最长上升子序列的长度。

输入

输入的第一行是序列的长度N (1 <= N <= 300000)。第二行给出序列中的N个整数，这些整数的取值范围都在0到100000000之间。输出最长上升子序列的长度。

样例输入

7
1 7 3 5 9 4 8

样例输出

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <stack>
 5 #include <string>
 6 #include <math.h>
 7 #include <queue>
 8 #include <stdio.h>
 9 #include <string.h>
10 #include <vector>
11 
12 #define lowbit(x) x&(-x)
13 
14 using namespace std;
15 
16 struct node {
17     int pos,value;
18     bool operator<(node a) {
19         if (value == a.value)
20             return pos > a.pos;
21         return value < a.value;
22     }
23 };
24 
25 const int maxn = 300005;
26 node n[maxn];
27 int N,c[maxn];
28 
29 int query(int pos) {
30     int res = 0;
31     while (pos > 0) {
32         res = max(c[pos],res);
33         pos -= lowbit(pos);
34     }
35     return res;
36 }
37 
38 void change(int pos,int len) {
39     while (pos <= N) {
40         c[pos] = max(c[pos],len);
41         pos += lowbit(pos);
42     }
43 }
44 
45 int getmax() {
46     int s = N,res=0;
47     while (s > 0) {
48         res = max(res,c[s]);
49         s -= lowbit(s);
50     }
51     return res;
52 }
53 
54 void process() {
55     for (int i = 1; i <= N; i++) {
56         int lis;
57         lis = query(n[i].pos) + 1;
58         change(n[i].pos,lis);
59     }
60     printf("%dn",getmax());
61 }
62 
63 
64 int main()
65 {
66     scanf("%d",&N);
67     for (int i = 1; i <= N; i++) {
68         int val;
69         scanf("%d",&val);
70         n[i].pos = i,n[i].value = val;
71     }
72     sort(n + 1,n+N+1);
73     process();
74     return 0;
75 }

View Code

我很好奇他们是怎么发现数据的范围一开始是错的？？

课上睡着了没听到这题，看了PPT做的

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!