先从第一颗树飞,然后用瞬移卡,每次选可以飞的次数最多且可以瞬移到的树瞬移
#include <iostream>
#include <algorithm>
using namespace std;
using PII = pair<int, int>;
using LL = long long;
constexpr int N = 3e5 + 10;
int n, m;
int tree[N], card[N], l[N], r[N];
int q[N], tt;
PII a[N];
int max_skip(int u)
{
return max(l[u], r[u]);
}
int find(int x)
{
int l = 0, r = n - 1;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (a[mid].first <= x) l = mid;
else r = mid - 1;
}
return l;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; ++ i)
cin >> tree[i];
for (int i = 0; i < m; ++ i)
cin >> card[i];
for (int i = 0; i < n; ++ i)
{
int h = 0;
while (tt && tree[q[tt - 1]] < tree[i]) h = max(h, l[q[-- tt]] + 1);
l[i] = h;
q[tt ++] = i;
}
tt = 0;
for (int i = n - 1; i >= 0; -- i)
{
int h = 0;
while (tt && tree[q[tt - 1]] < tree[i]) h = max(h, r[q[-- tt]] + 1);
r[i] = h;
q[tt ++] = i;
}
for (int i = 0; i < n; ++ i) a[i] = {tree[i], max_skip(i)};
sort(a, a + n);
for (int i = 1; i < n; ++ i)
{
a[i].second = max(a[i].second, a[i - 1].second);
}
LL res = max_skip(0);
for (int i = 0; i < m; ++ i)
res += a[find(card[i])].second;
cout << res;
}