#include <iostream> #include <set> using namespace std; const int N = 1e5 + 10; int f1[N]; int f2[N]; int arr[N]; set<int> mp[N]; int ans[N]; int main() { int n; cin >> n; for(int i = 1;i <= n;i ++)cin >> arr[i]; int cnt = 0; for(int i = 1;i <= n;i ++) { int l = 1,r = cnt; int x = arr[i]; while(l < r) { // 找到比他大的最小的数所在的位置 int mid = (l + r) >> 1; if(f1[mid] >= x)r = mid; else l = mid + 1; } //cout << f1[r] << ' ' << i << ' ' << x << endl; if(f1[r] < x){ f1[++ cnt] = x; mp[cnt].insert(i); }else if(f1[r] > x){ f1[r] = x; mp[r].insert(i); } } cout << cnt << endl; ans[cnt] = *(mp[cnt].begin()); for(int i = cnt - 1;i >= 1;i --) { int t = arr[ans[i + 1]]; int maxv = 0; for(auto p : mp[i]) { if(p < ans[cnt] && arr[p] < t && arr[p] > arr[maxv]) { maxv = p; } } ans[i] = maxv; } for(int i = 1;i < cnt;i ++)cout << ans[i] << ' '; cout << ans[cnt]; }
全部评论
(0) 回帖