Yukicoder No.318 学学学学学
solution
区間一様代入と点取得のsegment木を書けばよい。$O((n+q)\log n)$。 segment木でなくてもできる。
implementation
#include <iostream>
#include <vector>
#include <map>
#include <cmath>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
template <class T> void setmax(T & a, T const & b) { if (a < b) a = b; }
template <class T> void setmin(T & a, T const & b) { if (b < a) a = b; }
template <typename T>
struct lazed_segment_tree { // on associative symmetric monoid
int n;
vector<T> a;
function<T (T,T)> append; // associative, symmetric
co_segment_tree() = default;
template <typename F>
co_segment_tree(int a_n, T a_init, F a_append) {
n = pow(2,ceil(log2(a_n)));
a.resize(2*n-1, a_init);
append = a_append;
}
void range_update(int l, int r, T z) {
range_update(0, 0, n, l, r, z);
}
void range_update(int i, int il, int ir, int l, int r, T z) {
if (l <= il and ir <= r) {
a[i] = append(a[i], z);
} else if (ir <= l or r <= il) {
// nop
} else {
range_update(2*i+1, il, (il+ir)/2, l, r, z);
range_update(2*i+2, (il+ir)/2, ir, l, r, z);
}
}
T point_concat(int i) {
T z = a[i+n-1];
for (i = (i+n)/2; i > 0; i /= 2) {
z = append(z, a[i-1]);
}
return z;
}
};
int main() {
// input
int n; cin >> n;
vector<int> as(n); repeat (i,n) cin >> as[i];
// compute
map<int,pair<int,int> > q;
repeat (i,n) {
if (not q.count(as[i])) q[as[i]] = { i, i };
setmin(q[as[i]].first, i);
setmax(q[as[i]].second, i);
}
co_segment_tree<int> t(n, 0, [](int a, int b) { return max(a, b); });
for (auto it : q) {
int a = it.first;
int l, r; tie(l, r) = it.second;
t.range_update(l, r+1, a);
}
// output
repeat (i,n) {
if (i) cout << ' ';
cout << t.point_concat(i);
}
cout << endl;
return 0;
}