hihocoder1718 最长一次上升子序列

思路：

对于每个i，分别求1~i和i+1~N两部分的最长下降子序列“拼”起来，最终取最大长度即可。学习了如何使用BIT把LIS问题O(N²)算法优化为O(Nlog(N))的算法。

https://www.cnblogs.com/zsyacm666666/p/5703745.html

此外，还有基于二分查找的O(Nlog(N))算法。

实现：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int MAXN = 100005;
 4 int bit[MAXN], a[MAXN], d1[MAXN], d2[MAXN], n;
 5 int lowbit(int x) { return x & -x; }
 6 void update(int i, int x)
 7 {
 8     while (i <= MAXN) { bit[i] = max(x, bit[i]); i += lowbit(i); }
 9 }
10 int query(int i)
11 {
12     int ans = 0;
13     while (i) { ans = max(ans, bit[i]); i -= lowbit(i); }
14     return ans;
15 }
16 int main()
17 {
18     cin >> n;
19     for (int i = 1; i <= n; i++) cin >> a[i];
20     for (int i = 1; i <= n; i++)
21     {
22         int tmp = 100001 - a[i];
23         d1[i] = query(tmp - 1) + 1;
24         update(tmp, d1[i]);
25     }
26     memset(bit, 0, sizeof bit);
27     for (int i = n; i >= 1; i--)
28     {
29         d2[i] = query(a[i] - 1) + 1;
30         update(a[i], d2[i]);
31     }
32     for (int i = 1; i <= n; i++) d1[i] = max(d1[i], d1[i - 1]);
33     for (int i = n; i >= 1; i--) d2[i] = max(d2[i], d2[i + 1]);
34     int maxn = 2;
35     for (int i = 1; i <= n; i++) maxn = max(maxn, d1[i] + d2[i + 1]);
36     cout << maxn << endl;
37     return 0;
38 }