给定一个数组，要从中删除一段连续的子数组，使得新的数组的连续递增子序列最长。
要删除一个连续区间，则考虑区间端点，设左端点为j，右端点为i，且新的数组最长连续递增子序列包含i，j。
则新数组的连续递增子序列为 pre[j]+suf[i]，其中 pre[j] 表示以 j 为右端点的最长连续递增子序列长度，suf[i] 表示以 i 为左端点的最长连续递增子序列长度。这两者都可以 O(n) 地预处理出来。
接下来问题就转化为求一对 (i,j)，使得 pre[j]+suf[i] 最大。
枚举 i，对每一个i，存它之前的所有j，并且每次用最长的 pre[j]。
考虑用set维护最长的 pre[j]。以a[i]为关键字。当存入一个pre[i]时，比较它与已经在set中的，前一个节点的pre值大于pre[i]，则没有必要把pre[i]存入set，否则要存入。当存入后，考虑把后面的某些pre值小于pre[i]的节点都删掉，由于每次都是保证set中a值大的点pre值也一定大，所以当某点pre值大于pre[i]时，后面的点pre值一定也大于pre[i]，故停止搜索。
用erase删除点时，会导致原有迭代器失效，故只能用p=st.erase§。
在每次向set中插入值时，会先检查是否已经在set中，所以当有两个值相同，而其中一个已经在set中时，另一个就无法再插入了。再本题中，重载了两个点的a值相同，则两点相同，故当当前要插入的点已经存在于set中了，即使两点pre值不同，也无法插入。但我们需要的是用新的点替换旧的点，因为原数组中下标大的，且a值相同的点，一定比下标小的，a值相同的点pre只会大不会小。所以需要每次插入之前先从set中删除a值相同的点，再插入，确保set被更新了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
int n, ans, t;
int a[maxn], pre[maxn], suf[maxn];
struct X
{
int val, pr;
friend bool operator<(const X& a, const X& b) {
return a.val > b.val;
}
};
set<X>st;
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
scanf("%d", &t);
while (t--) {
st.clear();
ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
a[0] = -1; a[n + 1] = -1;
for (int i = 1; i <= n; i++) {
if (a[i] > a[i - 1])pre[i] = pre[i - 1] + 1;
else pre[i] = 1;
}
for (int i = n; i >= 1; i--) {
if (a[i] < a[i + 1])suf[i] = suf[i + 1] + 1;
else suf[i] = 1;
}
for (int i = 1; i <= n; i++) {
auto p = st.upper_bound(X{ a[i],pre[i] });
if (p != st.end())ans = max(ans, suf[i] + (*p).pr);
else ans = max(ans, suf[i]);
if (p != st.end() && (*p).pr >= pre[i])continue;
st.erase(X{ a[i],pre[i] });
pair<set<X>::iterator, bool> np;
np = st.insert(X{ a[i],pre[i] });
set<X>::iterator pp = np.first;
if (pp == st.begin())continue;
pp--;
for (; (*pp).pr <= pre[i]; ) {
pp = st.erase(pp);
if (pp == st.begin())break;
pp--;
}
}
printf("%d\n", ans);
}
return 0;
}
|
