-
-
Save neetsdkasu/3537d161651d2b7d647feefaf566326d to your computer and use it in GitHub Desktop.
RangeMin.java (範囲最小値を取得)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.*; | |
final class Main { | |
static final int TEST = 100; | |
static final int N_MIN = 100; | |
static final int N_MAX = 999; | |
public static void main(String[] args) throws Exception { | |
long t0 = System.currentTimeMillis(); | |
Random rand = new Random(System.currentTimeMillis()); | |
for (int t = 1; t <= TEST; t++) { | |
int N = rand.nextInt(N_MAX - N_MIN + 1) + N_MIN; | |
System.err.printf("[TEST] %3d/%3d N=%d : ", t, TEST, N); | |
List<Integer> list = new ArrayList<>(N); | |
for (int i = 1; i <= N; i++) list.add(i); | |
for (int i = 0; i < 5; i++) | |
Collections.shuffle(list, rand); | |
List<Integer> res0 = new ArrayList<>(N * N); | |
long time0 = System.currentTimeMillis(); | |
{ | |
RangeMin<Integer> rm = new RangeMin<>(list, (a, b) -> a.compareTo(b)); | |
for (int i = 0; i < list.size(); i++) { | |
for (int k = i; k < list.size(); k++) { | |
res0.add(rm.getMin(i, k)); | |
} | |
} | |
} | |
long time1 = System.currentTimeMillis(); | |
List<Integer> res1 = new ArrayList<>(N * N); | |
long time2 = System.currentTimeMillis(); | |
{ | |
for (int i = 0; i < list.size(); i++) { | |
for (int k = i; k < list.size(); k++) { | |
Integer y = list.get(k); | |
for (int e = i; e < k; e++) { | |
if (list.get(e).compareTo(y) <= 0) | |
y = list.get(e); | |
} | |
res1.add(y); | |
} | |
} | |
} | |
long time3 = System.currentTimeMillis(); | |
int pos = 0; | |
for (int i = 0; i < list.size(); i++) { | |
for (int k = i; k < list.size(); k++) { | |
Integer x = res0.get(pos); | |
Integer y = res1.get(pos); | |
if (!y.equals(x)) { | |
System.err.println("NG"); | |
System.err.println(Arrays.toString(list.toArray(new Integer[0]))); | |
throw new RuntimeException("[invalid] expect:" + y + ", getMin("+i+","+k+")=" + x); | |
} | |
pos++; | |
} | |
} | |
System.err.printf("OK ( %7d ms / %7d ms )%n", time1 - time0, time3 - time2); | |
} | |
long t1 = System.currentTimeMillis(); | |
System.err.printf("ALL DONE ( %10d ms )%n", t1 - t0); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class RangeMin<T> { | |
java.util.List<java.util.List<T>> table; | |
int[][] starts, ends; | |
java.util.Comparator<? super T> cmp; | |
RangeMin(java.util.List<T> base, java.util.Comparator<? super T> cmp) { | |
this.cmp = cmp; | |
table = new java.util.ArrayList<>(); | |
java.util.List<int[]> starts = new java.util.ArrayList<>(); | |
java.util.List<int[]> ends = new java.util.ArrayList<>(); | |
int[] tts = new int[base.size()], tte = new int[base.size()]; | |
for (int i = 0; i < base.size(); i++) { | |
tts[i] = tte[i] = i; | |
} | |
starts.add(tts); | |
ends.add(tte); | |
table.add(base); | |
while (base.size() > 1) { | |
int b = (base.size() + 1) / 2; | |
java.util.List<T> tmp = new java.util.ArrayList<>(b); | |
int[] ts = new int[b], te = new int[b]; | |
for (int i = 0; i < base.size(); i += 2) { | |
if (i + 1 < base.size()) { | |
T v1 = base.get(i), v2 = base.get(i + 1); | |
tmp.add(cmp.compare(v1, v2) <= 0 ? v1 : v2); | |
ts[i >> 1] = tts[i]; | |
te[i >> 1] = tte[i + 1]; | |
} else { | |
tmp.add(base.get(i)); | |
ts[i >> 1] = tts[i]; | |
te[i >> 1] = tte[i]; | |
} | |
} | |
table.add(tmp); | |
base = tmp; | |
starts.add(ts); | |
tts = ts; | |
ends.add(te); | |
tte = te; | |
} | |
java.util.Collections.reverse(starts); | |
java.util.Collections.reverse(ends); | |
this.starts = starts.toArray(new int[0][]); | |
this.ends = ends.toArray(new int[0][]); | |
} | |
/** | |
* @param endIndex inclusive | |
*/ | |
T getMin(int startIndex, int endIndex) { | |
if (startIndex == endIndex) { | |
return table.get(0).get(startIndex); | |
} | |
return getMin(0, 0, startIndex, endIndex); | |
} | |
private T getMin(int p, int i, int startIndex, int endIndex) { | |
if (starts[p][i] == startIndex && ends[p][i] == endIndex) { | |
return table.get(table.size() - 1 - p).get(i); | |
} | |
if (endIndex <= ends[p + 1][i << 1]) { | |
return getMin(p + 1, i << 1, startIndex, endIndex); | |
} | |
if (ends[p + 1][i << 1] < startIndex) { | |
return getMin(p + 1, (i << 1) + 1, startIndex, endIndex); | |
} | |
T v1 = getMin(p + 1, i << 1, startIndex, ends[p + 1][i << 1]); | |
T v2 = getMin(p + 1, (i << 1) + 1, starts[p + 1][(i << 1) + 1], endIndex); | |
return cmp.compare(v1, v2) <= 0 ? v1 : v2; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment