#555168 (C++14) No.1234 典型RMQ

• 問題: No.1234 典型RMQ
• ユーザー: Example0911
• 提出日時: 2020-09-18 22:26:33
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA
• 実行時間: -
• コード長: 2,306 bytes
• コンパイル時間: 1,889 ms
• コンパイル使用メモリ: 177,480 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2024-07-20 00:50:15
• 合計ジャッジ時間: 9,468 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	WA	-
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	WA	-
testcase_04	AC	2 ms; 5,376 KB
testcase_05	AC	2 ms; 5,376 KB
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	AC	221 ms; 8,832 KB
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	AC	2 ms; 5,376 KB
testcase_28	AC	2 ms; 5,376 KB
testcase_29	AC	2 ms; 5,376 KB

ソースコード

#include "bits/stdc++.h"
using namespace std;
#define int long long
int N, Q;
int INF = (1LL<<60);
struct LazySegmentTree {
private:
	int n;
	vector<int> node, lazy;

public:
	LazySegmentTree(vector<int> v) {
		int sz = (int)v.size();
		n = 1; while (n < sz) n *= 2;
		node.resize(2 * n - 1);
		lazy.resize(2 * n - 1, 0);

		for (int i = 0; i < sz; i++) node[i + n - 1] = v[i];
		for (int i = n - 2; i >= 0; i--) node[i] = min(node[i * 2 + 1], node[i * 2 + 2]);
	}
	void eval(int k, int l, int r) {

		// 遅延配列が空でない場合、自ノード及び子ノードへの
		// 値の伝播が起こる
		if (lazy[k] != 0) {
			node[k] += lazy[k];

			// 最下段かどうかのチェックをしよう
			// 子ノードは親ノードの 1/2 の範囲であるため、
			// 伝播させるときは半分にする
			if (r - l > 1) {
				lazy[2 * k + 1] += lazy[k] / 2;
				lazy[2 * k + 2] += lazy[k] / 2;
			}

			// 伝播が終わったので、自ノードの遅延配列を空にする
			lazy[k] = 0;
		}
	}

	void add(int a, int b, int x, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;

		// k 番目のノードに対して遅延評価を行う
		eval(k, l, r);

		// 範囲外なら何もしない
		if (b <= l || r <= a) return;

		// 完全に被覆しているならば、遅延配列に値を入れた後に評価
		if (a <= l && r <= b) {
			lazy[k] += (r - l) * x;
			eval(k, l, r);
		}

		// そうでないならば、子ノードの値を再帰的に計算して、
		// 計算済みの値をもらってくる
		else {
			add(a, b, x, 2 * k + 1, l, (l + r) / 2);
			add(a, b, x, 2 * k + 2, (l + r) / 2, r);
			node[k] = min(node[2 * k + 1], node[2 * k + 2]);
		}
	}

	int find(int a, int b, int k = 0, int l = 0, int r = -1) {
		if (r < 0) r = n;
		eval(k, l, r);
		if (b <= l || r <= a) return INF;
		if (a <= l && r <= b) return node[k];
		int vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
		int vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
		return min(vl, vr);
	}
};

signed main() {
	cin >> N;
	vector<int>a(N);
	for (int i = 0; i < N; i++)cin >> a[i];
	cin >> Q;
	LazySegmentTree seg(a);
	for (int i = 0; i < Q; i++) {
		int c, x, y; cin >> c >> x >> y; x--; y--;
		int t; cin >> t;
		if (c == 1) seg.add(x, y+1, t);
		else cout << seg.find(x, y + 1) << endl;
	}
}