結果

問題 No.1234 典型RMQ
コンテスト
ユーザー Example0911
提出日時 2020-09-18 22:38:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 309 ms / 2,000 ms
コード長 4,153 bytes
コンパイル時間 1,875 ms
コンパイル使用メモリ 172,504 KB
実行使用メモリ 10,368 KB
最終ジャッジ日時 2024-11-09 02:00:04
合計ジャッジ時間 9,543 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

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