結果

問題 No.876 Range Compress Query
ユーザー tomatoma
提出日時 2019-09-06 21:56:33
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 378 ms / 2,000 ms
コード長 5,074 bytes
コンパイル時間 2,016 ms
コンパイル使用メモリ 177,400 KB
実行使用メモリ 10,112 KB
最終ジャッジ日時 2024-06-24 17:43:17
合計ジャッジ時間 6,230 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 4 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 4 ms
5,376 KB
testcase_08 AC 3 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 376 ms
9,984 KB
testcase_12 AC 306 ms
9,856 KB
testcase_13 AC 304 ms
9,856 KB
testcase_14 AC 363 ms
9,984 KB
testcase_15 AC 257 ms
9,984 KB
testcase_16 AC 360 ms
9,984 KB
testcase_17 AC 355 ms
10,112 KB
testcase_18 AC 378 ms
10,112 KB
権限があれば一括ダウンロードができます

ソースコード

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;

// 使用方法はworkspaceでgrep 'LazySegmentTree' -rl ./などをすること

//http://beet-aizu.hatenablog.com/entry/2019/03/12/171221
template<typename T>
class SegmentTree {
private:
	using F = function<T(T, T)>; // モノイド型
	int n; // 横幅
	F f;   // モノイド
	T e;   // モノイド単位元
	vector<T> data;

public:
	// init忘れに注意
	SegmentTree() {}
	SegmentTree(F f, T e) :f(f), e(e) {}
	void init(int n_) {
		n = 1;
		while (n < n_)n <<= 1;
		data.assign(n << 1, e);
	}
	void build(const vector<T>& v) {
		int n_ = v.size();
		init(n_);
		rep(i, n_)data[n + i] = v[i];
		for (int i = n - 1; i >= 0; i--) {
			data[i] = f(data[(i << 1) | 0], data[(i << 1) | 1]);
		}
	}
	void set_val(int idx, T val) {
		idx += n;
		data[idx] = val;
		while (idx >>= 1) {
			data[idx] = f(data[(idx << 1) | 0], data[(idx << 1) | 1]);
		}
	}
	T query(int a, int b) {
		// [a,b)
		T vl = e, vr = e;
		for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
			if (l & 1)vl = f(vl, data[l++]); // unknown
			if (r & 1)vr = f(data[--r], vr); // unknown
		}
		return f(vl, vr);
	}
};

template<typename T>
using ST = SegmentTree<T>;


// https://ei1333.github.io/luzhiled/snippets/structure/segment-tree.html
// Monoid: オブジェクト
// OperatorMonoid: オブジェクトに作用する変数
// f,g,hがどこで使用されているかを見るとやりやすい
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区間マージ演算
	const G g; // 要素,作用素マージ演算(区間の長さ込みで伝搬させるときの、(data,lazy,len)の計算)
	const H h; // 作用素マージ演算　(伝搬させるときの、(lazy,val)の計算)
	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 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);
	}
};

template<typename T>
using LST = LazySegmentTree<T>;


int main()
{
	int N, Q;
	cin >> N >> Q;
	vector<ll> a(N);
	rep(i, N)cin >> a[i];

	// aは遅延セグ木で値の管理を行う
	constexpr ll INIT = 0;
	function<ll(ll, ll)> FH = [](ll a, ll b) {
		return a + b;
	};
	function<ll(ll, ll, int)> G = [](ll a, ll b, int sz) {
		return a + b * sz;
	};
	LazySegmentTree<ll> lst(N, FH, G, FH, INIT, INIT);
	lst.build(a);

	// 解は通常セグ木で値の管理を行う
	function<ll(ll, ll)> f = [](ll a, ll b) {
		return a + b;
	};
	SegmentTree<ll> st(f, INIT);
	st.init(N - 1);
	rep(i, N - 1)st.set_val(i, a[i] != a[i + 1] ? 1 : 0);

	// クエリ処理
	rep(i, Q) {
		int com, l, r;
		cin >> com >> l >> r;
		l--; r--;
		if (com == 1) {
			int x;
			cin >> x;
			lst.update(l, r + 1, x);
			if (l != 0) {
				st.set_val(l - 1, lst[l - 1] != lst[l] ? 1 : 0);
			}
			if (r != N - 1) {
				st.set_val(r, lst[r] != lst[r + 1] ? 1 : 0);
			}
		}
		else {
			cout << st.query(l, r) + 1 << endl;
		}
	}

	return 0;
}
0