結果

問題 No.318 学学学学学
ユーザー toma
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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()
{
	// input
	ll n;
	cin >> n;
	vector<ll> a(n);
	rep(i, n)cin >> a[i];

	// seg init
	auto 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);

	// mapper
	map<ll, set<ll>> mp;
	rep(i, n)mp[a[i]].insert(i);

	// query
	for (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;
}
0