結果
問題 | No.318 学学学学学 |
ユーザー |
|
提出日時 | 2019-09-24 22:43:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 209 ms / 2,000 ms |
コード長 | 3,299 bytes |
コンパイル時間 | 2,111 ms |
コンパイル使用メモリ | 187,412 KB |
実行使用メモリ | 22,144 KB |
最終ジャッジ日時 | 2024-09-19 13:29:30 |
合計ジャッジ時間 | 7,186 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include"bits/stdc++.h"using namespace std;#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)#define rep(i,n) REP((i),0,(n))using ll = long long;template<typename Monoid, typename OperatorMonoid = Monoid>class LazySegmentTree {private:using F = function<Monoid(Monoid, Monoid)>;using G = function<Monoid(Monoid, OperatorMonoid, int)>;using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;int sz; // 対応する配列の幅vector<Monoid> data;vector<OperatorMonoid> lazy;const F f; // 2区間マージ演算(data-data-ボトムアップマージ)const G g; // 要素,作用素マージ演算(lazy->data同位置変換時の、(data,lazy,len)の計算)const H h; // 作用素マージ演算 (query->lazyトップダウン伝搬時の、(lazy,query_value)の計算)const Monoid M1; // モノイド単位元 (data単位元)const OperatorMonoid OM0; // 作用素単位元 (lazy単位元)void propagate(int idx, int len) {// 幅lenのlazy[idx]が存在するとき、値を下に流すif (lazy[idx] != OM0) {if (idx < sz) {lazy[(idx << 1) | 0] = h(lazy[(idx << 1) | 0], lazy[idx]);lazy[(idx << 1) | 1] = h(lazy[(idx << 1) | 1], lazy[idx]);}data[idx] = g(data[idx], lazy[idx], len);lazy[idx] = OM0;}}Monoid update_impl(int a, int b, const OperatorMonoid& val, int idx, int l, int r) {propagate(idx, r - l);if (r <= a || b <= l)return data[idx];else if (a <= l && r <= b) {lazy[idx] = h(lazy[idx], val);propagate(idx, r - l);return data[idx];}else return data[idx] = f(update_impl(a, b, val, (idx << 1) | 0, l, (l + r) >> 1),update_impl(a, b, val, (idx << 1) | 1, (l + r) >> 1, r));}Monoid query_impl(int a, int b, int idx, int l, int r) {propagate(idx, r - l);if (r <= a || b <= l)return M1;else if (a <= l && r <= b)return data[idx];else return f(query_impl(a, b, (idx << 1) | 0, l, (l + r) >> 1),query_impl(a, b, (idx << 1) | 1, (l + r) >> 1, r));}public:// init忘れに注意LazySegmentTree(int n, const F f, const G g, const H h,const Monoid& M1, const OperatorMonoid OM0):f(f), g(g), h(h), M1(M1), OM0(OM0) {sz = 1;while (sz < n)sz <<= 1;data.assign(2 * sz, M1);lazy.assign(2 * sz, OM0);}void build(const vector<Monoid>& vals) {rep(idx, vals.size())data[idx + sz] = vals[idx];for (int idx = sz - 1; idx > 0; idx--) {data[idx] = f(data[(idx << 1) | 0], data[(idx << 1) | 1]);}}Monoid update(int a, int b, const OperatorMonoid& val) {return update_impl(a, b, val, 1, 0, sz);}Monoid query(int a, int b) {return query_impl(a, b, 1, 0, sz);}Monoid operator[](const int& idx) {return query(idx, idx + 1);}};int main(){// inputll n;cin >> n;vector<ll> a(n);rep(i, n)cin >> a[i];// seg initauto f = [](ll l, ll r) {return l + r; };auto g = [](ll data, ll lazy, int siz) {return lazy; };auto h = [](ll lazy, ll query) {return query; };LazySegmentTree<ll> seg(n, f, g, h, 0, 0);// mappermap<ll, set<ll>> mp;rep(i, n)mp[a[i]].insert(i);// queryfor (auto itr : mp) {ll val = itr.first;ll l = *itr.second.begin();ll r = *(--itr.second.end());seg.update(l, r + 1, val);}rep(i, n)cout << seg[i] << " ";cout << endl;return 0;}