<commit_before>import java.util.*;
import java.io.*;

/* <NAME> */
public class SegmentTreeRMQ
{
	int n;
	int[] A;
	int[] T; 

	public SegmentTreeRMQ(int A[]) {
		this.n = A.length;
		this.A = A;
		int h = (int) (Math.ceil(Math.log(n) / Math.log(2)));
		int max_size = 2 * (int) Math.pow(2, h) - 1;
		this.T = new int[max_size];
		this.fill(0, n - 1, 0);
	}

	int fill(int l, int r, int i) {
		if (l == r) {
			T[i] = A[l];
			return A[l];
		}
		int m = (l + r) >>> 1;
		int vl = fill(l, m, i * 2 + 1);
		int vr = fill(m + 1, r, i * 2 + 2);
		T[i] = Math.min(vl, vr);
		return T[i];
	}	
 
 	int rmq(int al, int ar, int l, int r, int index)
	{
		if (l <= al && r >= ar) {
			return T[index];
		}
		if (ar < l || al > r) {
			return Integer.MAX_VALUE;
		}
		int mid = (al + ar) >>> 1;
		int vl = rmq(al, mid, l, r, 2 * index + 1);
		int vr = rmq(mid + 1, ar, l, r, 2 * index + 2);
		return Math.min(vl, vr);
	}
 
	int rmq(int n, int l, int r)
	{
		assert l >= 0 : "l >= 0";
		assert r < n : "r < n";
		assert l <= r : "l <= r";
		return rmq(0, n - 1, l, r, 0);
	}

	public static void main(String args[]) 
	{
		int A[] = { 3, 2, 7, 5, 4, 2, 3, 8 };
		int n = A.length;
		SegmentTreeRMQ o = new SegmentTreeRMQ(A);
		debug(o.A);
		debug(o.T);
	}

	static boolean DEBUG = true;
	
	static void debug(Object...os) {
		if (!DEBUG) { return; }
		System.err.printf("%.65536s\n", Arrays.deepToString(os));
	}
}
<commit_msg>indexed rmq<commit_after>import java.util.*;
import java.io.*;

/* <NAME> */
public class SegmentTreeRMQ
{
	int n;
	int[] A;
	int[] T; // contains indexes of min elements

	public SegmentTreeRMQ(int A[]) {
		this.n = A.length;
		this.A = A;
		int h = (int) (Math.ceil(Math.log(n) / Math.log(2)));
		int max_size = 2 * (int) Math.pow(2, h) - 1;
		this.T = new int[max_size];
		this.fill(0, n - 1, 0);
	}

	int fill(int l, int r, int i) {
		if (l == r) {
			T[i] = l;
			return l;
		}
		int m = (l + r) >>> 1;
		int il = fill(l, m, i * 2 + 1);
		int ir = fill(m + 1, r, i * 2 + 2);
		T[i] = (A[il] <= A[ir]) ? il : ir;
		return T[i];
	}	
 
 	int rmq(int al, int ar, int l, int r, int index)
	{
		if (l <= al && r >= ar) {
			return T[index];
		}
		if (ar < l || al > r) {
			return -1;
		}
		int mid = (al + ar) >>> 1;
		int il = rmq(al, mid, l, r, 2 * index + 1);
		int ir = rmq(mid + 1, ar, l, r, 2 * index + 2);
		int vl = (il < 0) ? Integer.MAX_VALUE : A[il];
		int vr = (ir < 0) ? Integer.MAX_VALUE : A[ir];
		return (vl <= vr) ? il : ir;
	}
 
	int rmq(int l, int r)
	{
		assert l >= 0 : "l >= 0";
		assert r < n : "r < n";
		assert l <= r : "l <= r";
		return rmq(0, n - 1, l, r, 0);
	}

	static int min(int[] A, int l, int r) {
		int m = Integer.MAX_VALUE;
		for (int i = l; i <= r; i++) {
			m = Math.min(m, A[i]);
		}
		return m;
	}

	public static void main(String args[]) 
	{
		int A[] = { 3, 2, 7, 5, 4, 2, 3, 8 };
		int n = A.length;
		SegmentTreeRMQ o = new SegmentTreeRMQ(A);
		debug(o.A);
		debug(o.T);

		for (int l = 0; l < n; l++) {
			for (int r = l; r < n; r++) {
				assert A[o.rmq(l, r)] == min(A, l, r);
			}
		}
	}

	static boolean DEBUG = true;
	
	static void debug(Object...os) {
		if (!DEBUG) { return; }
		System.err.printf("%.65536s\n", Arrays.deepToString(os));
	}
}

{'fraction_non_alphanumeric': 0.2135286783042394, 'fraction_numerical': 0.024314214463840397, 'mean_word_length': 2.3185108583247156, 'pattern_counts': {'":': 0, '<': 24, '<?xml version=': 0, '>': 25, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5526152', 'n_tokens_mistral': 1655, 'n_tokens_neox': 1473, 'n_words': 455}