#708520 (C++17) No.1705 Mode of long array

• 問題: No.1705 Mode of long array
• ユーザー: Example0911
• 提出日時: 2021-10-21 18:53:37
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 181 ms / 3,000 ms
• コード長: 3,527 bytes
• コンパイル時間: 2,330 ms
• コンパイル使用メモリ: 207,336 KB
• 実行使用メモリ: 6,400 KB
• 最終ジャッジ日時: 2024-09-21 15:00:57
• 合計ジャッジ時間: 10,214 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	2 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	3 ms; 5,376 KB
testcase_04	AC	3 ms; 5,376 KB
testcase_05	AC	4 ms; 5,376 KB
testcase_06	AC	8 ms; 5,376 KB
testcase_07	AC	8 ms; 5,376 KB
testcase_08	AC	9 ms; 5,376 KB
testcase_09	AC	8 ms; 5,376 KB
testcase_10	AC	7 ms; 5,376 KB
testcase_11	AC	7 ms; 5,376 KB
testcase_12	AC	8 ms; 5,376 KB
testcase_13	AC	81 ms; 5,760 KB
testcase_14	AC	60 ms; 5,376 KB
testcase_15	AC	72 ms; 5,376 KB
testcase_16	AC	81 ms; 5,376 KB
testcase_17	AC	61 ms; 5,376 KB
testcase_18	AC	49 ms; 5,376 KB
testcase_19	AC	88 ms; 5,376 KB
testcase_20	AC	54 ms; 5,376 KB
testcase_21	AC	61 ms; 5,376 KB
testcase_22	AC	91 ms; 6,144 KB
testcase_23	AC	39 ms; 5,376 KB
testcase_24	AC	37 ms; 5,376 KB
testcase_25	AC	39 ms; 5,376 KB
testcase_26	AC	39 ms; 5,376 KB
testcase_27	AC	37 ms; 5,376 KB
testcase_28	AC	36 ms; 5,376 KB
testcase_29	AC	37 ms; 5,376 KB
testcase_30	AC	37 ms; 5,376 KB
testcase_31	AC	37 ms; 5,376 KB
testcase_32	AC	38 ms; 5,376 KB
testcase_33	AC	73 ms; 6,272 KB
testcase_34	AC	73 ms; 6,272 KB
testcase_35	AC	72 ms; 6,400 KB
testcase_36	AC	71 ms; 6,400 KB
testcase_37	AC	76 ms; 6,400 KB
testcase_38	AC	73 ms; 6,272 KB
testcase_39	AC	75 ms; 6,400 KB
testcase_40	AC	74 ms; 6,272 KB
testcase_41	AC	73 ms; 6,400 KB
testcase_42	AC	73 ms; 6,400 KB
testcase_43	AC	176 ms; 6,400 KB
testcase_44	AC	165 ms; 6,400 KB
testcase_45	AC	162 ms; 6,400 KB
testcase_46	AC	167 ms; 6,400 KB
testcase_47	AC	167 ms; 6,400 KB
testcase_48	AC	181 ms; 6,400 KB
testcase_49	AC	101 ms; 6,400 KB
testcase_50	AC	101 ms; 6,400 KB
testcase_51	AC	100 ms; 6,400 KB
testcase_52	AC	95 ms; 6,400 KB
testcase_53	AC	93 ms; 6,400 KB

ソースコード

#include "bits/stdc++.h"

#define int long long

using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll INF = (1LL << 61);
ll mod = 1000000007;

/* RMQ：[0,n-1] について、区間ごとの最小値を管理する構造体
	set(int i, T x), build(): i番目の要素をxにセット。まとめてセグ木を構築する。O(n)
	update(i,x): i 番目の要素を 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 e = numeric_limits<T>::max();
	function<T(T, T)> fx = [](T x1, T x2) -> T { return min(x1, x2); };
	int n;
	vector<T> dat;
	RMQ(int n_) : n(), dat(n_ * 4, e) {
		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] = fx(dat[2 * k + 1], dat[2 * k + 2]);
	}
	void update(int i, T x) {
		i += n - 1;
		dat[i] = x;
		while (i > 0) {
			i = (i - 1) / 2;  // parent
			dat[i] = fx(dat[i * 2 + 1], dat[i * 2 + 2]);
		}
	}
	// the minimum element of [a,b)
	T query(int a, int b) { return query_sub(a, b, 0, 0, n); }
	T query_sub(int a, int b, int k, int l, int r) {
		if (r <= a || b <= l) {
			return e;
		}
		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 fx(vl, vr);
		}
	}
	int find_rightest(int a, int b, T x) { return find_rightest_sub(a, b, x, 0, 0, n); }
	int find_leftest(int a, int b, T x) { return find_leftest_sub(a, b, x, 0, 0, n); }
	int find_rightest_sub(int a, int b, T x, int k, int l, int r) {
		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);
			}
		}
	}
	int find_leftest_sub(int a, int b, T x, int k, int l, int r) {
		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);
			}
		}
	}
};
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M; cin >> N >> M;
	RMQ<int>rmq(M);
	for (int i = 0; i < M; i++) {
		int a; cin >> a;
		rmq.update(i, -a);
	}
	int Q; cin >> Q;
	for (int i = 0; i < Q; i++) {
		int T, X, Y; cin >> T >> X >> Y; X--;
		if (T == 1) {
			int now = rmq.query(X, X + 1);
			rmq.update(X, now - Y);
		}
		else if (T == 2) {
			int now = rmq.query(X, X + 1);
			rmq.update(X, now + Y);
		}
		else {
			int now = rmq.query(0, M);
			cout << rmq.find_rightest(0, M, now) + 1 << endl;
		}
	}
	return 0;
}