結果

問題 No.1234 典型RMQ
ユーザー Example0911Example0911
提出日時 2020-09-18 22:38:02
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 282 ms / 2,000 ms
コード長 4,153 bytes
コンパイル時間 1,684 ms
コンパイル使用メモリ 169,788 KB
実行使用メモリ 10,404 KB
最終ジャッジ日時 2023-08-08 18:49:05
合計ジャッジ時間 8,805 ms
ジャッジサーバーID
(参考情報)
judge11 / judge13
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 2 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 2 ms
4,380 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 268 ms
8,140 KB
testcase_07 AC 226 ms
4,376 KB
testcase_08 AC 282 ms
9,840 KB
testcase_09 AC 252 ms
6,464 KB
testcase_10 AC 275 ms
9,148 KB
testcase_11 AC 262 ms
7,780 KB
testcase_12 AC 249 ms
5,908 KB
testcase_13 AC 230 ms
4,376 KB
testcase_14 AC 251 ms
6,128 KB
testcase_15 AC 247 ms
5,420 KB
testcase_16 AC 276 ms
8,788 KB
testcase_17 AC 254 ms
6,504 KB
testcase_18 AC 219 ms
4,380 KB
testcase_19 AC 279 ms
9,872 KB
testcase_20 AC 209 ms
10,112 KB
testcase_21 AC 270 ms
7,752 KB
testcase_22 AC 236 ms
10,336 KB
testcase_23 AC 233 ms
10,404 KB
testcase_24 AC 232 ms
10,016 KB
testcase_25 AC 231 ms
10,340 KB
testcase_26 AC 233 ms
10,124 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 2 ms
4,376 KB
testcase_29 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include "bits/stdc++.h"
using namespace std;
#define int long long
int N, Q;

/* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体
	set(i,x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
	add(a,b,x): 区間[a,b) の要素に x を加算。O(log(n))
	query(a,b): 区間 [a,b) での最小の要素を取得。O(log(n))
	find_rightest(a,b,x): [a,b) で x以下の要素を持つ最右位置を求める。O(log(n))
	find_leftest(a,b,x): [a,b) で x以下の要素を持つ最左位置を求める。O(log(n))
*/
template <typename T>
struct RMQ {
	const T INF = numeric_limits<T>::max();
	int n;
	vector<T> dat, lazy;
	RMQ(int n_) : n(), dat(n_ * 4, INF), lazy(n_ * 4, 0) {
		int x = 1;
		while (n_ > x) x *= 2;
		n = x;
	}

	void set(int i, T x) { dat[i + n - 1] = x; }
	void build() {
		for (int k = n - 2; k >= 0; k--) dat[k] = min(dat[2 * k + 1], dat[2 * k + 2]);
	}

	/* lazy eval */
	void eval(int k) {
		if (lazy[k] == 0) return;  // 更新するものが無ければ終了
		if (k < n - 1) {           // 葉でなければ子に伝搬
			lazy[k * 2 + 1] += lazy[k];
			lazy[k * 2 + 2] += lazy[k];
		}
		// 自身を更新
		dat[k] += lazy[k];
		lazy[k] = 0;
	}

	void add(int a, int b, T x, int k, int l, int r) {
		eval(k);
		if (a <= l && r <= b) {  // 完全に内側の時
			lazy[k] += x;
			eval(k);
		}
		else if (a < r && l < b) {                  // 一部区間が被る時
			add(a, b, x, k * 2 + 1, l, (l + r) / 2);  // 左の子
			add(a, b, x, k * 2 + 2, (l + r) / 2, r);  // 右の子
			dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
		}
	}
	void add(int a, int b, T x) { add(a, b, x, 0, 0, n); }

	T query_sub(int a, int b, int k, int l, int r) {
		eval(k);
		if (r <= a || b <= l) {  // 完全に外側の時
			return INF;
		}
		else if (a <= l && r <= b) {  // 完全に内側の時
			return dat[k];
		}
		else {  // 一部区間が被る時
			T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);
			T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);
			return min(vl, vr);
		}
	}
	T query(int a, int b) { return query_sub(a, b, 0, 0, n); }

	T find_rightest(int a, int b, int x) { return find_rightest_sub(a, b, x, 0, 0, n); }  // 存在しなければ a-1
	T find_leftest(int a, int b, int x) { return find_leftest_sub(a, b, x, 0, 0, n); }    // 存在しなければ b
	T find_rightest_sub(int a, int b, int x, int k, int l, int r) {
		eval(k);
		if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn a-1
			return a - 1;
		}
		else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
			return (k - (n - 1));
		}
		else {
			int vr = find_rightest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
			if (vr != a - 1) {  // 右の部分木を見て a-1 以外ならreturn
				return vr;
			}
			else {  // 左の部分木を見て値をreturn
				return find_rightest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
			}
		}
	}
	T find_leftest_sub(int a, int b, int x, int k, int l, int r) {
		eval(k);
		if (dat[k] > x || r <= a || b <= l) {  // 自分の値がxより大きい or [a,b)が[l,r)の範囲外ならreturn b
			return b;
		}
		else if (k >= n - 1) {  // 自分が葉ならその位置をreturn
			return (k - (n - 1));
		}
		else {
			int vl = find_leftest_sub(a, b, x, 2 * k + 1, l, (l + r) / 2);
			if (vl != b) {  // 左の部分木を見て b 以外ならreturn
				return vl;
			}
			else {  // 右の部分木を見て値をreturn
				return find_leftest_sub(a, b, x, 2 * k + 2, (l + r) / 2, r);
			}
		}
	}

	/* debug */
	inline T operator[](int a) { return query(a, a + 1); }
	void print() {
		for (int i = 0; i < n; ++i) {
			cout << (*this)[i];
			if (i != n) cout << ",";
		}
		cout << endl;
	}
};


signed main() {
	cin >> N;
	vector<int>a(N);
	for (int i = 0; i < N; i++)cin >> a[i];
	cin >> Q;
	RMQ<int> rmq(N);
	for (int i = 0; i < N; i++) {
		rmq.set(i, a[i]);
	}
	rmq.build();
	for (int i = 0; i < Q; i++) {
		int c, x, y; cin >> c >> x >> y; x--; y--;
		int t; cin >> t;
		if (c == 1) rmq.add(x, y+1, t);
		else cout << rmq.query(x, y + 1) << endl;
	}
	return 0;
}
0