Pagini recente » Cod sursa (job #2196575) | Cod sursa (job #3256130) | Cod sursa (job #2270712) | Cod sursa (job #1624238) | Cod sursa (job #2267131)
#include <bits/stdc++.h>
using namespace std;
template<typename T>
struct SegmTree {
vector<T> data; int n;
const T kInf;
SegmTree(int n, T kInf) : data(2 * n, kInf), n(n), kInf(kInf) {}
void Update(int pos, T val) {
for (data[pos += n] = val; pos > 1; pos /= 2)
data[pos / 2] = min(data[pos], data[pos ^ 1]);
}
T Query(int b, int e) {
T res = kInf;
for (b += n, e += n; b < e; b /= 2, e /= 2) {
if (b % 2) res = min(res, data[b++]);
if (e % 2) res = min(res, data[--e]);
}
return res;
}
};
int main() {
ifstream cin("subsir2.in");
ofstream cout("subsir2.out");
int n; cin >> n;
vector<int> v(n), stk;
vector<pair<int, int>> order(n);
for (int i = 0; i < n; ++i) {
cin >> v[i];
order[i] = {v[i], i};
}
sort(order.begin(), order.end());
for (int i = 0; i < n; ++i) {
auto it = lower_bound(order.begin(), order.end(), make_pair(v[i], i));
v[i] = distance(order.begin(), it);
}
vector<vector<int>> solve(n);
vector<int> dp(n, 0), prv(n, -1);
for (int i = 0; i < n; ++i) {
while (stk.size() && v[stk.back()] > v[i])
stk.pop_back();
if (stk.size())
solve[stk.back()].push_back(i);
stk.push_back(i);
}
const tuple<int, int, int> kInf = {2e9, n, n};
SegmTree<tuple<int, int, int>> st(n, kInf);
stk.clear();
for (int i = 0; i < n; ++i) {
while (stk.size() && v[stk.back()] <= v[i]) {
st.Update(stk.back(), kInf);
stk.pop_back();
}
st.Update(i, {dp[i], v[i], i});
stk.push_back(i);
for (auto j : solve[i]) {
int start = *lower_bound(
stk.begin(), stk.end(), j, [&](int a, int b) {
return v[a] > v[b];
});
tie(dp[j], ignore, prv[j]) = st.Query(start, n);
dp[j] += 1;
}
}
vector<int> ans;
for (int pos = get<2>(st.Query(0, n)); pos >= 0; pos = prv[pos])
ans.push_back(pos);
reverse(ans.begin(), ans.end());
cout << ans.size() << endl;
for (auto x : ans)
cout << x + 1 << " ";
cout << endl;
return 0;
}