結果

問題 No.3198 Monotonic Query
ユーザー ks2m
提出日時 2025-07-11 22:06:42
言語 Java
(openjdk 23)
結果
AC  
実行時間 583 ms / 3,000 ms
コード長 5,920 bytes
コンパイル時間 4,520 ms
コンパイル使用メモリ 91,152 KB
実行使用メモリ 56,092 KB
最終ジャッジ日時 2025-07-12 10:54:53
合計ジャッジ時間 17,913 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int q = Integer.parseInt(br.readLine());
		SegTree<Integer> st = new SegTree<>(q, 0, (v1, v2) -> Math.max(v1, v2));
		int n = 0;

		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			String[] sa = br.readLine().split(" ");
			int t = Integer.parseInt(sa[0]);
			int x = Integer.parseInt(sa[1]);
			if (t == 1) {
				st.set(n, x);
				n++;
			} else {
				int ans = st.prod(n - x, n);
				pw.println(ans);
			}
		}
		pw.flush();
		br.close();
	}
}

class SegTree<S> {
	private final int n; // 要素数
	private final int size; // 葉の数（n以上の最小の2べき）
	private final BinaryOperator<S> op; // 二項演算
	private final S e; // 単位元
	private final S[] data;

	/**
	 * 長さnの配列aを作る。初期値は全て単位元。<br>
	 * O(n)
	 * 
	 * @param n 要素数
	 * @param e 単位元
	 * @param op 二項演算
	 */
	@SuppressWarnings("unchecked")
	public SegTree(int n, S e, BinaryOperator<S> op) {
		this.n = n;
		int k = 1;
		while (k < n) k <<= 1;
		this.size = k;
		this.e = e;
		this.op = op;
		this.data = (S[]) new Object[size << 1];
		Arrays.fill(data, e);
	}

	/**
	 * 長さdat.lengthの配列aをdatを元に作る。<br>
	 * O(n)
	 * 
	 * @param dat 初期データ
	 * @param e 単位元
	 * @param op 二項演算
	 */
	public SegTree(S[] dat, S e, BinaryOperator<S> op) {
		this(dat.length, e, op);
		build(dat);
	}

	private void build(S[] dat) {
		int l = dat.length;
		System.arraycopy(dat, 0, data, size, l);
		for (int i = size - 1; i > 0; i--) {
			data[i] = op.apply(data[i << 1 | 0], data[i << 1 | 1]);
		}
	}

	/**
	 * a[p] = xとする。<br>
	 * O(log n)
	 * 
	 * @param p 設定位置（0≦p＜n）
	 * @param x 設定値
	 */
	void set(int p, S x) {
		assert 0 <= p && p < n : "p=" + p;

		data[p += size] = x;
		p >>= 1;
		while (p > 0) {
			data[p] = op.apply(data[p << 1 | 0], data[p << 1 | 1]);
			p >>= 1;
		}
	}

	/**
	 * a[p]を取得する。<br>
	 * O(1)
	 * 
	 * @param p 取得位置（0≦p＜n）
	 */
	S get(int p) {
		assert 0 <= p && p < n : "p=" + p;

		return data[p + size];
	}

	/**
	 * 区間l～(r-1)の計算を行う。<br>
	 * l＝rのときは単位元を返す。<br>
	 * O(log n)
	 * 
	 * @param l 開始位置（含む）    （0≦l≦r≦n）
	 * @param r 終了位置（含まない）（0≦l≦r≦n）
	 */
	S prod(int l, int r) {
		assert 0 <= l && l <= r && r <= n : "l=" + l + ", r=" + r;

		S sumLeft = e;
		S sumRight = e;
		l += size;
		r += size;
		while (l < r) {
			if ((l & 1) == 1) sumLeft = op.apply(sumLeft, data[l++]);
			if ((r & 1) == 1) sumRight = op.apply(data[--r], sumRight);
			l >>= 1;
			r >>= 1;
		}
		return op.apply(sumLeft, sumRight);
	}

	/**
	 * 全区間の計算を行う。<br>
	 * O(1)
	 */
	S allProd() {
		return data[1];
	}

	/**
	 * f(op(l～(r-1)))＝trueとなる最大のrを返す。<br>
	 * （計算区間にrを追加するとfalseになる）<br>
	 * O(log n)
	 * 
	 * @param l 左端（含む）（0≦l≦n）
	 * @param f 判定関数（f(e)＝true）（例：val -> val > 0）
	 * @return 条件を満たす最大のr
	 */
	int maxRight(int l, Predicate<S> f) {
		assert 0 <= l && l <= n : "l=" + l;
		assert f.test(e);

		if (l == n) return n;
		l += size;
		S sum = e;
		do {
			l >>= Integer.numberOfTrailingZeros(l);
			if (!f.test(op.apply(sum, data[l]))) {
				while (l < size) {
					l = l << 1;
					if (f.test(op.apply(sum, data[l]))) {
						sum = op.apply(sum, data[l]);
						l++;
					}
				}
				return l - size;
			}
			sum = op.apply(sum, data[l]);
			l++;
		} while ((l & -l) != l);
		return n;
	}

	/**
	 * f(op(l～(r-1)))＝trueとなる最小のlを返す。<br>
	 * （計算区間に(l-1)を追加するとfalseになる）<br>
	 * O(log n)
	 * 
	 * @param r 右端（含まない）（0≦r≦n）
	 * @param f 判定関数（f(e)＝true）（例：val -> val > 0）
	 * @return 条件を満たす最小のl
	 */
	int minLeft(int r, Predicate<S> f) {
		assert 0 <= r && r <= n : "r=" + r;
		assert f.test(e);

		if (r == 0) return 0;
		r += size;
		S sum = e;
		do {
			r--;
			while (r > 1 && (r & 1) == 1) r >>= 1;
			if (!f.test(op.apply(data[r], sum))) {
				while (r < size) {
					r = r << 1 | 1;
					if (f.test(op.apply(data[r], sum))) {
						sum = op.apply(data[r], sum);
						r--;
					}
				}
				return r + 1 - size;
			}
			sum = op.apply(data[r], sum);
		} while ((r & -r) != r);
		return 0;
	}

	// **************** DEBUG **************** //

	private int indent = 6;

	void setIndent(int newIndent) {
		this.indent = newIndent;
	}

	@Override
	public String toString() {
		return toSimpleString();
	}

	/**
	 * セグメント木全体の要素をツリー状に出力。
	 */
	String toDetailedString() {
		return toDetailedString(1, 0);
	}

	private String toDetailedString(int k, int sp) {
		if (k >= size) return indent(sp) + data[k];
		StringBuilder sb = new StringBuilder();
		sb.append(toDetailedString(k << 1 | 1, sp + indent));
		sb.append("\n");
		sb.append(indent(sp) + data[k]);
		sb.append("\n");
		sb.append(toDetailedString(k << 1 | 0, sp + indent));
		return sb.toString();
	}

	private String indent(int n) {
		StringBuilder sb = new StringBuilder();
		while (n-- > 0) sb.append(' ');
		return sb.toString();
	}

	/**
	 * n件の要素のみを、配列形式で出力。
	 */
	String toSimpleString() {
		StringBuilder sb = new StringBuilder();
		sb.append('[');
		for (int i = 0; i < size; i++) {
			sb.append(data[i + size]);
			if (i < size - 1) sb.append(',').append(' ');
		}
		sb.append(']');
		return sb.toString();
	}
}
0