Editorial for Bedao Regular Contest 05 - CARRAY
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
DP, LIS.
Ý tưởng
Với từng ~a[i]~, giả sử ta chọn ~a[i]~ làm phần tử đầu tiên được thêm để tạo thành dãy B, ta rút ra nhận xét như sau:
Các phần tử được thêm vào dãy ~B~ bằng cách thêm vào đầu, ta thêm lần lượt và vẫn giữ nguyên trình tự khi nằm trên dãy ~A~. Nhận ra rằng các phần tử đó tạo ra dãy con giảm dài nhất có phần tử đầu tiên là ~a[i]~ . Vì là dãy giảm dài nhất nên khi ta thêm lần lượt vào dãy ~B~ bằng cách thêm vào đầu thì dãy B vẫn tăng dần (thỏa mãn tính chất, và các số được thêm vào luôn tăng, dài nhất).
Tương tự với các phần tử được thêm vào dãy ~B~ Bằng cách thêm vào đuôi. Nhận ra rằng các phần tử đó tạo ra dãy con tăng dài nhất có phần tử đầu tiên là ~a[i]~ .
--> Với từng ~a[i]~ ta chỉ cần tìm các dãy tăng hoặc giảm ngặt bắt đầu bằng ~a[i]~ và kết quả là giá trị lớn nhất giữa tổng hai độ dài trừ đi ~1~ vì ~a[i]~ lặp lại hai lần.
Đọc thêm về cách tìm LIS trong ~O(nlogn)~ tại đây
Code mẫu
#include <bits/stdc++.h> using namespace std; int n; int a[100001]; int f[200001], g[200001]; int bit1[200001], bit2[200001]; void upd1(int x, int val) { for (; x > 0; x -= x & (-x)) bit1[x] = max(bit1[x], val); } void upd2(int x, int val) { for (; x <= n; x += x & (-x)) bit2[x] = max(bit2[x], val); } int query1(int x) { int ans = 0; for (; x <= n; x += x & (-x)) ans = max(ans, bit1[x]); return ans; } int query2(int x) { int ans = 0; for (; x > 0; x -= x & (-x)) ans = max(ans, bit2[x]); return ans; } int main(int argc, char** argv) { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n; vector<int> val; for (int i = 1; i <= n; i++) { cin >> a[i]; val.push_back(a[i]); } sort(val.begin(), val.end()); for (int i = 1; i <= n; i++) a[i] = lower_bound(val.begin(), val.end(), a[i]) - val.begin() + 1; for (int i = n; i >= 1; i--) { f[i] = 1 + query1(a[i] + 1); g[i] = 1 + query2(a[i] - 1); upd1(a[i], f[i]); upd2(a[i], g[i]); } int ans = 0; for (int i = 1; i <= n; i++) ans = max(ans, f[i] + g[i] - 1); cout << ans; }
Comments