线段树求解
#include <bits/stdc++.h> using i64 = long long; #define endl '\n' const i64 inf = 1e17 + 50, mod = 1e9 + 7; class SegmentTree { private: int size; std::vector<int> tree; public: SegmentTree(int max_val) { size = 1; while (size < max_val) size <<= 1; tree.assign(2 * size, 0); } void update(int pos, int val) { int node = size + pos - 1; if (tree[node] >= val) return; tree[node] = val; for(node >>= 1; node >= 1; node >>= 1) { int new_val = std::max(tree[2 * node], tree[2 * node + 1]); if (tree[node] == new_val) break; tree[node] = new_val; } } int query(int l, int r) { if (l > r) return 0; l = std::max(l, 1); r = std::min(r, size); int res = 0; int node_l = size + l - 1; int node_r = size + r - 1; while (node_l <= node_r) { if (node_l % 2 == 1) res = std::max(res, tree[node_l++]); if (node_r % 2 == 0) res = std::max(res, tree[node_r--]); node_l >>= 1; node_r >>= 1; } return res; } }; void solve() { int n; std::cin >> n; std::vector<int> a(n); for(int i = 0; i < n; ++i) std::cin >> a[i]; // 离散化 std::vector<int> b(a); std::sort(b.begin(), b.end()); b.erase(std::unique(b.begin(), b.end()), b.end()); for(int &x : a) { x = std::lower_bound(b.begin(), b.end(), x) - b.begin() + 1; } int m = b.size(); // 计算前缀数组p std::vector<int> p(n, 1); SegmentTree st_p(m); for(int i = 0; i < n; ++i) { int x = a[i]; p[i] = st_p.query(1, x - 1) + 1; st_p.update(x, p[i]); } // 计算后缀数组s std::vector<int> s(n, 1); SegmentTree st_s(m); for(int i = n - 1; i >= 0; --i) { int x = a[i]; s[i] = st_s.query(1, x - 1) + 1; st_s.update(x, s[i]); } int ans = 10 * n; for(int i = 1; i < n - 1; ++i) { ans = std::min(ans, n - (p[i] + s[i] - 1)); } std::cout << ans << endl; } signed main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr), std::cout.tie(nullptr); solve(); return 0; }