/**
* TODO: verify {@link LazySegTree#maxRight} and {@link LazySegTree#minLeft}
*
* @verified https://atcoder.jp/contests/practice2/tasks/practice2_k
*/
class LazySegTree {
final int MAX;
final int N;
final int Log;
final java.util.function.BinaryOperator Op;
final S E;
final java.util.function.BiFunction op, S e, java.util.function.BiFunction op, S e, java.util.function.BiFunction g) {
inclusiveRangeCheck(l);
if (!g.test(E)) {
throw new IllegalArgumentException("Identity element must satisfy the condition.");
}
if (l == MAX) return MAX;
l += N;
pushTo(l);
S sum = E;
do {
l >>= Integer.numberOfTrailingZeros(l);
if (!g.test(Op.apply(sum, Dat[l]))) {
while (l < N) {
push(l);
l = l << 1;
if (g.test(Op.apply(sum, Dat[l]))) {
sum = Op.apply(sum, Dat[l]);
l++;
}
}
return l - N;
}
sum = Op.apply(sum, Dat[l]);
l++;
} while ((l & -l) != l);
return MAX;
}
public int minLeft(int r, java.util.function.Predicate g) {
inclusiveRangeCheck(r);
if (!g.test(E)) {
throw new IllegalArgumentException("Identity element must satisfy the condition.");
}
if (r == 0) return 0;
r += N;
pushTo(r - 1);
S sum = E;
do {
r--;
while (r > 1 && (r & 1) == 1) r >>= 1;
if (!g.test(Op.apply(Dat[r], sum))) {
while (r < N) {
push(r);
r = r << 1 | 1;
if (g.test(Op.apply(Dat[r], sum))) {
sum = Op.apply(Dat[r], sum);
r--;
}
}
return r + 1 - N;
}
sum = Op.apply(Dat[r], sum);
} while ((r & -r) != r);
return 0;
}
private void exclusiveRangeCheck(int p) {
if (p < 0 || p >= MAX) {
throw new IndexOutOfBoundsException(
String.format("Index %d is not in [%d, %d).", p, 0, MAX)
);
}
}
private void inclusiveRangeCheck(int p) {
if (p < 0 || p > MAX) {
throw new IndexOutOfBoundsException(
String.format("Index %d is not in [%d, %d].", p, 0, MAX)
);
}
}
// **************** DEBUG **************** //
private int indent = 6;
public void setIndent(int newIndent) {
this.indent = newIndent;
}
@Override
public String toString() {
return toSimpleString();
}
private S[] simulatePushAll() {
S[] simDat = java.util.Arrays.copyOf(Dat, 2 * N);
F[] simLaz = java.util.Arrays.copyOf(Laz, 2 * N);
for (int k = 1; k < N; k++) {
if (simLaz[k] == Id) continue;
int lk = k << 1 | 0, rk = k << 1 | 1;
simDat[lk] = Mapping.apply(simLaz[k], simDat[lk]);
simDat[rk] = Mapping.apply(simLaz[k], simDat[rk]);
if (lk < N) simLaz[lk] = Composition.apply(simLaz[k], simLaz[lk]);
if (rk < N) simLaz[rk] = Composition.apply(simLaz[k], simLaz[rk]);
simLaz[k] = Id;
}
return simDat;
}
public String toDetailedString() {
return toDetailedString(1, 0, simulatePushAll());
}
private String toDetailedString(int k, int sp, S[] dat) {
if (k >= N) return indent(sp) + dat[k];
String s = "";
s += toDetailedString(k << 1 | 1, sp + indent, dat);
s += "\n";
s += indent(sp) + dat[k];
s += "\n";
s += toDetailedString(k << 1 | 0, sp + indent, dat);
return s;
}
private static String indent(int n) {
StringBuilder sb = new StringBuilder();
while (n --> 0) sb.append(' ');
return sb.toString();
}
public String toSimpleString() {
S[] dat = simulatePushAll();
StringBuilder sb = new StringBuilder();
sb.append('[');
for (int i = 0; i < N; i++) {
sb.append(dat[i + N]);
if (i < N - 1) sb.append(',').append(' ');
}
sb.append(']');
return sb.toString();
}
}