Untitled
unknown
plain_text
a month ago
2.2 kB
1
Indexable
Never
#include <bits/stdc++.h> using namespace std; #define ll long long #define all(x) (x).begin(), (x).end() #define f(i, n) for (int i = 0; i < n; i++) #define trace(x) cerr << #x << ": " << x << '\n' int n; const int N = 2e5 + 7; int arr[N], dp[N]; struct ST { int t[4 * N]; static const int inf = 1e9; ST() { memset(t, 0, sizeof t); } void build(int n, int b, int e) { if (b == e) { t[n] = 1; return; } int mid = (b + e) >> 1, l = n << 1, r = l | 1; build(l, b, mid); build(r, mid + 1, e); t[n] = max(t[l], t[r]); } void upd(int n, int b, int e, int i, int x) { if (b > i || e < i) return; if (b == e && b == i) { t[n] = max(t[n], x); return; } int mid = (b + e) >> 1, l = n << 1, r = l | 1; upd(l, b, mid, i, x); upd(r, mid + 1, e, i, x); t[n] = max(t[l], t[r]); } int query(int n, int b, int e, int i, int j) { if (b > j || e < i) return -inf; if (b >= i && e <= j) return t[n]; int mid = (b + e) >> 1, l = n << 1, r = l | 1; int L = query(l, b, mid, i, j); int R = query(r, mid + 1, e, i, j); return max(L, R); } } t; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; f(i, N) dp[i] = 1; map<int, int> m; set<int> st; for (int i = 1; i <= n; i++) cin >> arr[i], st.insert(arr[i]); int i = 1; for (auto a : st) { m[a] = i++; } for (int i = 1; i <= n; i++) arr[i] = m[arr[i]]; t.build(1, 1, n); for (int i = 1; i <= n; i++) { // for (int j = 1; j < i; j++) // { // if (arr[j] < arr[i]) // dp[i] = max(dp[i], dp[j] + 1); // } if (arr[i] != 1) { int mx = t.query(1, 1, n, 1, arr[i] - 1); dp[i] = max(dp[i], mx + 1); } t.upd(1, 1, N, arr[i], dp[i]); } int mx = 0; for (int i = 1; i <= n; i++) mx = max(mx, dp[i]); cout << mx << '\n'; }
Leave a Comment