提出 #67755446

---

ソースコード 拡げる

@file:Suppress("unused", "UNUSED_PARAMETER")
@file:OptIn(ExperimentalStdlibApi::class)

import java.io.PrintStream
import java.math.BigDecimal
import java.math.BigInteger
import java.math.MathContext
import java.util.*
import kotlin.concurrent.thread
import kotlin.math.abs
import kotlin.system.exitProcess

/**
 * # Good Luck, Have Fun.
 *  -- GalaxyCat42
 */
fun main() {

    val n = int
    val q = int
    val s = str
    val st = SegTree(n, s)
    repeat(q) {
        when (int) {
            1 -> {
                val i = int-1
                val x = str[0]
                st.update(i, x)
            }
            2 -> {
                val l = int-1
                val r = int
                st.check(l, r).maxLen.println()
            }
        }
    }

}

data class CheckResult(
    val len: Int,
    val lChar: Char,
    val lLen: Int,
    val rChar: Char,
    val rLen: Int,
    val maxLen: Int
)
interface SegTree {
    val size: Int
    fun update(index: Int, value: Char)
    fun check(from: Int, to: Int): CheckResult
    class Body(
        val left: SegTree,
        val right: SegTree,
    ) : SegTree {
        override val size = left.size+right.size
        var cache: CheckResult? = null
        override fun update(index: Int, value: Char) {
            cache = null
            if (index < left.size)
                left.update(index, value)
            else
                right.update(index-left.size, value)
        }
        override fun check(from: Int, to: Int): CheckResult {
            if (from<=0 && size<=to) {
                cache?.let { return it }
                val r = union(
                    left.check(0, left.size),
                    right.check(0, right.size)
                )
                cache = r
                return r
            }
            if (to <= left.size)
                return left.check(from, to)
            if (left.size <= from)
                return right.check(from-left.size, to-left.size)
            return union(
                left.check(from, minOf(to, left.size)),
                right.check(maxOf(from-left.size, 0), to-left.size)
            )
        }
        fun union(l: CheckResult, r: CheckResult): CheckResult {
            if (l.rChar == r.lChar) {
                val ls = l.lLen == l.len
                val rs = r.rLen == r.len
                return when {
                    ls && rs ->
                        CheckResult(
                            l.len+r.len,
                            l.lChar, l.len+r.len,
                            r.rChar, l.len+r.len,
                            l.len+r.len
                        )
                    ls ->
                        CheckResult(
                            l.len+r.len,
                            l.lChar, l.len+r.lLen,
                            r.rChar, r.rLen,
                            maxOf(l.len+r.lLen, r.maxLen)
                        )
                    rs ->
                        CheckResult(
                            l.len+r.len,
                            l.lChar, l.lLen,
                            r.rChar, l.rLen+r.len,
                            maxOf(l.maxLen, l.rLen+r.len)
                        )
                    else ->
                        CheckResult(
                            l.len+r.len,
                            l.lChar, l.lLen,
                            r.rChar, r.rLen,
                            maxOf(l.maxLen, r.maxLen, l.rLen+r.lLen)
                        )
                }
            } else {
                return CheckResult(
                    l.len+r.len,
                    l.lChar, l.lLen,
                    r.rChar, r.rLen,
                    maxOf(l.maxLen, r.maxLen)
                )
            }
        }

        override fun toString() = "$left$right"
    }
    class Tail(var value: Char) : SegTree {
        override val size = 1
        override fun update(index: Int, value: Char) {
            this.value = value
        }
        override fun check(from: Int, to: Int) =
            CheckResult(1, value, 1, value, 1, 1)

        override fun toString() = "$value"
    }
}
fun SegTree(size: Int, source: String, srcIdx: Int = 0): SegTree {
    if (size == 1) return SegTree.Tail(source[srcIdx])
    val first = size/2
    return SegTree.Body(
        SegTree(first, source, srcIdx),
        SegTree(size-first, source, srcIdx+first)
    )
}

operator fun IntArray.minus(value: Int) = apply { it-value }
val Boolean.i get() = if (this) 1 else 0
fun Int.log() = when (this) {
    0 -> throw ArithmeticException()
    in 0 until 10 -> 0
    in 0 until 100 -> 1
    in 0 until 1000 -> 2
    in 0 until 10000 -> 3
    in 0 until 100000 -> 4
    in 0 until 1000000 -> 5
    in 0 until 10000000 -> 6
    in 0 until 100000000 -> 7
    in 0 until 1000000000 -> 8
    else -> 9
}

fun <T> Sequence<T>.countEach() = mutableMapOf<T, Int>().also { for (i in this) it.incr(i) }

// region struct
interface RollingHash {
    val size: Int
    operator fun get(from: Int, to: Int): Int
    data class Merger(
        val p: Int, val m: Int
    ) {
        fun merge(x: Int, y: Int, rc: Int): Int =
            ((x.toLong()*(m mod p).pow(rc).value+y)%p).toIntExact()
    }
    class Body(
        private val left: RollingHash,
        private val right: RollingHash,
        override val size: Int,
        private val min: Int,
        private val max: Int,
        private val mid: Int,
        private val merger: Merger
    ) : RollingHash {
        private val fullCache = merger.merge(left[min, mid], right[mid, max], max-mid)
        override fun get(from: Int, to: Int): Int {
            if (from<=min && max<=to) return fullCache
            if (from==to) return 0
            if (to <= mid)
                return left[from, to]
            if (mid <= from)
                return right[from, to]
            return merger.merge(left[from, mid], right[mid, to], to-mid)
        }
    }
    class Tail(private val value: Int = 0) : RollingHash {
        override val size get() = 1
        override fun get(from: Int, to: Int): Int {
            if (from==to) return 0
            return value
        }
    }
}
fun RollingHash(source: List<Int>): RollingHash {
    val merger = RollingHash.Merger(((1 e 9) + 7).toIntExact(), 998244353)
    fun struct(min: Int, max: Int): RollingHash {
        val siz = max-min
        if (siz<=1) return RollingHash.Tail(source[min])
        val mid = (min+max) shr 1
        return RollingHash.Body(
            struct(min, mid), struct(mid, max),
            siz, min, max, mid, merger
        )
    }
    return struct(0, source.size)
}
interface LST {
    val size: Int
    fun get(index: Int): Int
    fun set(index: Int, value: Int)
    fun max(from: Int, to: Int): Int
    class Body(
        private val left: LST,
        private val right: LST,
        override val size: Int,
        private val mid: Int,
    ) : LST {
        // 応急処置
        private var max = Int.MIN_VALUE
        override fun get(index: Int): Int {
            return if (index < mid)
                left.get(index)
            else
                right.get(index-mid)
        }
        override fun set(index: Int, value: Int) {
            if (index < mid)
                left.set(index, value)
            else
                right.set(index-mid, value)
            if (max < value)
                max = value
        }
        override fun max(from: Int, to: Int): Int {
            if (from <= 0 && size <= to)
                return max
            var max = Int.MIN_VALUE
            if (from < mid)
                max = maxOf(max, left.max(from, to))
            if (mid < to)
                max = maxOf(max, right.max(from-mid, to-mid))
            return max
        }
        override fun toString() = (0 until size).map { get(it) }
            .joinToString(prefix = "[", postfix = "]")
    }
    class Tail(private var value: Int = 0) : LST {
        override val size get() = 1
        override fun get(index: Int): Int = value
        override fun set(index: Int, value: Int) {
            this.value = value
        }
        override fun max(from: Int, to: Int): Int = value
        override fun toString() = "[$value]"
    }
}
fun LST(size: Int): LST {
    fun struct(min: Int, max: Int): LST {
        val siz = max-min
        if (siz<=1) return LST.Tail(Int.MIN_VALUE)
        val mid = siz/2
        return LST.Body(
            struct(min, min+mid), struct(min+mid, max),
            siz, mid
        )
    }
    return struct(0, size)
}

data class Vec2I(val x: Int, val y: Int) {
    val i get() = x
    val j get() = y
    companion object;
    infix fun castTo(`_`: Vec2L.Companion) = Vec2L(x.toLong(),y.toLong())
    infix fun castTo(`_`: Companion) = this
    infix fun castTo(`_`: Vec2BD.Companion) = Vec2BD(bd(x), bd(y))
    //    infix fun castTo(`_`: Fraction.Companion) = Fraction(bi(x), bd(y))
    operator fun plus(other: Vec2I) = Vec2I(x+other.x, y+other.y)
    operator fun minus(other: Vec2I) = Vec2I(x-other.x, y-other.y)
    operator fun unaryMinus() = Vec2I(-x, -y)
    operator fun times(scale: Int) = Vec2I(x*scale, y*scale)
    fun adjacents() = listOf(x+1 to y, x-1 to y, x to y+1, x to y-1)
    fun checkBound(w: Int, h: Int) = x in 0 until w && y in 0 until h
    fun toPair() = Pair(x, y)
    fun manhattan() = abs(x) + abs(y)
    override fun toString(): String = "($x, $y)"
    fun println() = "$x $y".println()
    operator fun iterator(): Iterator<Int> = (x..y).iterator()
}
fun UnionFind(size: Int) = UnionFind(size, UFMeta.NOP)
class UnionFind<T>(
    @Suppress("MemberVisibilityCanBePrivate")
    val size: Int,
    private val meta: UFMeta<T>
) {
    class Group<T>(val id: Int, val elements: List<Int>, val metadata: T) {
        override fun toString() = "Group(gid=$id)"
    }
    data class UnionResult<T>(val success: Boolean, val group: Group<T>)
    private val _groups: MutableMap<Int, Group<T>> = mutableMapOf()
    val groups: Map<Int, Group<T>> get() = _groups
    private val groupId: IntArray
    private val validGroup: MutableSet<Group<T>> = Collections.newSetFromMap(IdentityHashMap())
    init {
        for (i in 0 until size) {
            val group = Group(i, mutableListOf(i), meta.init(i))
            _groups[i] = group
            validGroup += group
        }
        groupId = IntArray(size) { it }
    }
    fun find(element: Int): Group<T> = _groups[groupId[element]] ?: throw NoSuchElementException()
    fun union(group1: Group<T>, group2: Group<T>): UnionResult<T> {
        if (group1 == group2) return UnionResult(false, group1)
        if (group1 !in validGroup || group2 !in validGroup) throw NullPointerException()
        validGroup -= group1
        validGroup -= group2
        return if (group1.elements.size < group2.elements.size)
            unionInternal(group1, group2)
        else
            unionInternal(group2, group1)
    }
    private fun unionInternal(g1: Group<T>, g2: Group<T>): UnionResult<T> {
        val merged = meta.merge(g1.metadata, g2.metadata)
        (g2.elements as MutableList).addAll(g1.elements)
        for (x in g1.elements)
            groupId[x] = g2.id
        _groups.remove(g1.id)
        val group = Group(g2.id, g2.elements, merged)
        _groups[g2.id] = group
        validGroup += group
        return UnionResult(true, group)
    }
    fun groups() = _groups.values
}
interface UFMeta<T> {
    fun init(id: Int): T
    fun merge(t1: T, t2: T): T
    companion object {
        val NOP = object : UFMeta<Unit> {
            override fun init(id: Int) = Unit
            override fun merge(t1: Unit, t2: Unit) = Unit
        }
    }
}
data class Vec2L(val x: Long, val y: Long) : Comparable<Vec2L> {
    companion object;
    infix fun castTo(`_`: Vec2I.Companion) = Vec2I(x.toIntExact(),y.toIntExact())
    infix fun castTo(`_`: Companion) = this
    infix fun castTo(`_`: Vec2BD.Companion) = Vec2BD(bd(x), bd(y))
    //    infix fun castTo(`_`: Fraction.Companion) = Fraction(bd(x), bd(y))
    operator fun plus(other: Vec2L) = Vec2L(x+other.x, y+other.y)
    operator fun minus(other: Vec2L) = Vec2L(x-other.x, y-other.y)
    operator fun unaryMinus() = Vec2L(-x, -y)
    operator fun times(scale: Int) = Vec2L(x*scale, y*scale)
    operator fun times(scale: Long) = Vec2L(x*scale, y*scale)
    fun toPair() = Pair(x, y)
    fun manhattan() = abs(x) + abs(y)
    override fun toString(): String = "($x, $y)"
    fun println() = "$x $y".println()
    override fun compareTo(other: Vec2L): Int {
        x.compareTo(other.x).let { if (it != 0) return it }
        return y.compareTo(other.y)
    }
}
data class Vec2BD(val x: BigDecimal, val y: BigDecimal) {
    companion object;
    operator fun plus(other: Vec2BD) = Vec2BD(x+other.x, y+other.y)
    operator fun minus(other: Vec2BD) = Vec2BD(x-other.x, y-other.y)
    operator fun unaryMinus() = Vec2BD(-x, -y)
    operator fun times(scale: BigDecimal) = Vec2BD(x*scale, y*scale)
    fun toPair() = Pair(x, y)
    override fun toString(): String = "($x, $y)"
    fun println() = "$x $y".println()
}
infix fun Int.mod(mod: Int) = ModInt(this, mod)
data class ModInt(val value: Int, val mod: Int) {
    @Suppress("MemberVisibilityCanBePrivate")
    companion object {
        fun modPow(x: Long, a: Long, mod: Long): Long {
            if (a <= 1) return if (a == 1L) x else (if (a == 0L) 1 else 0).toLong()
            if ((a and 1L) != 0L) return (x * modPow(x, a - 1, mod)) % mod
            val t = modPow(x, a shr 1, mod)
            return (t * t) % mod
        }
        fun modPow2(a: Long, mod: Long): Long {
            if (a <= 1) return if (a == 1L) 2 else if (a == 0L) 1 else 0
            if ((a and 1L) != 0L) return (modPow2(a - 1, mod) shl 1) % mod
            val t = modPow2(a shr 1, mod)
            return (t * t) % mod
        }
        fun modInv(x: Long, mod: Long): Long = modPow(x, mod - 2, mod)
        fun modFrac(a: Long, b: Long, mod: Long): Long = modInv(b, mod) * a % mod
    }
    private fun assertModulus(other: ModInt): Int {
        if (mod != other.mod)
            throw IllegalArgumentException("this and other has different modulus: $mod, ${other.mod}")
        return mod
    }
    operator fun plus(other: ModInt): ModInt {
        val l = value.toLong() + other.value
        return ModInt((if (mod < l) l-mod else l).toInt(), assertModulus(other))
    }
    operator fun minus(other: ModInt): ModInt {
        val l = value.toLong() - other.value
        return ModInt((if (l < 0) l+mod else l).toInt(), assertModulus(other))
    }
    operator fun times(other: ModInt): ModInt =
        ModInt((value.toLong()*other.value%mod).toInt(), assertModulus(other))
    operator fun times(other: Int): ModInt =
        ModInt((value.toLong()*other%mod).toInt(), mod)
    operator fun div(other: ModInt): ModInt =
        ModInt(modFrac(value.toLong(), other.value.toLong(), mod.toLong()).toInt(), assertModulus(other))
    infix fun pow(other: Int): ModInt =
        ModInt(modPow(value.toLong(), other.toLong(), mod.toLong()).toInt(), mod)
    infix fun pow(other: Long): ModInt =
        ModInt(modPow(value.toLong(), other, mod.toLong()).toInt(), mod)
}
/** **注意：BITは1-indexedです** */
@Suppress("MemberVisibilityCanBePrivate")
class IntBIT(val size: Int) {
    private val data = IntArray(size)
    private val digits = size.takeHighestOneBit().countTrailingZeroBits()+1
    /** inclusive */
    fun sumUntil(index: Int): Long {
        if (index < 1) return 0
        var i = index
        var sum = 0L
        for (j in digits) {
            if (!i.bit(j)) continue
            sum += this[i]
            i = i xor (1 shl j)
        }
        return sum
    }
    fun addAt(index: Int, value: Int) {
        var i = index
        for (j in digits) {
            if (!i.bit(j)) continue
            if (i in indices)
                this[i]+=value
            i += 1 shl j
        }
    }
    private operator fun get(i: Int) = data[i-1]
    private operator fun set(i: Int, v: Int) { data[i-1]=v }
    private val indices get() = 1..size
    override fun toString() = (0..size).joinToString(", ", "[", "]") { sumUntil(it).toString() }
}
// endregion
// region 便宜
fun IntArray.boxed(): Array<Int> = Array(size) { this[it] }
fun LongArray.boxed(): Array<Long> = Array(size) { this[it] }
fun DoubleArray.boxed(): Array<Double> = Array(size) { this[it] }
fun <T> Iterable<T>.adjacents(): Iterable<Pair<T,T>> = Iterable {
    class AdjacentIterator<T>(first: T, private val iterator: Iterator<T>) : Iterator<Pair<T,T>> {
        var current: T = first
        override fun hasNext(): Boolean = iterator.hasNext()
        override fun next(): Pair<T,T> {
            val next = iterator.next()
            val result = current to next
            current = next
            return result
        }
    }
    val itr = iterator()
    if (!itr.hasNext())
        return@Iterable Collections.emptyIterator()
    return@Iterable AdjacentIterator(itr.next(), itr)
}
infix fun <T,U,V> Pair<T,U>.to(value:V)=Triple(first,second,value)
infix fun Int.to(value: Int) = Vec2I(this, value)
infix fun Long.to(value: Long) = Vec2L(this, value)
infix fun BigDecimal.to(value: BigDecimal) = Vec2BD(this, value)
fun Long.toIntExact(): Int = toIntExactOrNull() ?: throw ArithmeticException("$this is out of range")
fun Long.toIntExactOrNull(): Int? {
    val v = this.toInt()
    if (v.toLong() != this) return null
    return v
}
infix fun Long.castTo(`_`: Int.Companion): Int = toInt()
fun <T> Iterable<T>.refs(): Map<T, Int> = mutableMapOf<T,Int>().also { forEachIndexed { i, v -> it[v]=i } }
fun <T> Iterable<T>.multiRefs(): Map<T, List<Int>> = mutableMapOf<T, MutableList<Int>>()
    .also { forEachIndexed { i, v -> it.computeIfAbsent(v) { mutableListOf() }.add(i) } }
val MATH_CONTEXT: MathContext = MathContext.DECIMAL128
fun bd(value: Int) = BigDecimal(value)
fun bd(value: Long) = BigDecimal(value)
fun bd(value: Double) = BigDecimal(value)
operator fun BigDecimal.plus(value: BigDecimal): BigDecimal = add(value, MATH_CONTEXT)
operator fun BigDecimal.minus(value: BigDecimal): BigDecimal = subtract(value, MATH_CONTEXT)
operator fun BigDecimal.times(value: BigDecimal): BigDecimal = multiply(value, MATH_CONTEXT)
operator fun BigDecimal.div(value: BigDecimal): BigDecimal = divide(value, MATH_CONTEXT)
fun bi(value: Int): BigInteger = BigInteger.valueOf(value.toLong())
fun bi(value: Long): BigInteger = BigInteger.valueOf(value)
fun linear(x1: Int, y1: Int, x2: Int, y2: Int, x: Int): Double =
    ((y2-y1)*(x-x1)+y1*(x2-x1)).toDouble()/(x2-x1)
tailrec fun gcd(x: Long, y: Long): Long {
    if (x==0L || y==0L) return 0L
    if (x==y) return x
    return gcd(y, x%y)
}
fun D2Array<Char>.find(ch: Char): Vec2I {
    for (x in indices)
        for (y in this[x].indices)
            if (this[x,y] == ch)
                return x to y
    throw NoSuchElementException()
}
fun <T> MutableMap<T, Int>.incr(value: T) { this[value]=(this[value]?:0)+1 }
fun <T> MutableMap<T, Int>.decr(value: T) { if(1==this[value]) remove(value) else this[value]=(this[value]?:0)-1 }
fun Double.toString(precision: Int): String = String.format("%.${precision}f", this)
fun <T> hyperstacked(func: ()->T): T = HSWorker(func).get()
private class HSWorker<T>(private val func: ()->T) {
    private val lock = Object()
    @Volatile private var b = false
    @Volatile private var r: Any? = null
    @Suppress("UNCHECKED_CAST")
    fun get(): T {
        Thread(null, { r = func();synchronized(lock) { b = true;lock.notify() } }, "", 128*1024*1024).start()
        if (b) return r as T
        synchronized(lock) { if (b) return r as T;lock.wait() }
        return r as T
    }
}
private operator fun Int.iterator() = (0 until this).iterator()
private operator fun Int.contains(other: Int) = other in 0 until this
private operator fun Long.contains(other: Long) = other in 0 until this
// endregion
// region 定数絡み
infix fun Int.e(exp: Int): Long = toLong() e exp
infix fun Long.e(exp: Int): Long {
    var self = this
    if (0 < exp)
        for (i in 0 until exp)
            self *= 10
    else if (exp < 0)
        for (i in exp until 0)
            self /= 10
    return self
}
const val mod = 998244353L
const val Yes = "Yes"
const val No = "No"
const val Takahashi = "Takahashi"
const val Aoki = "Aoki"
const val Draw = "Draw"
const val Never = "-1"
// endregion
// region hack
@Suppress("FunctionName") fun WA(): Nothing { "\uD883\uDEDE\uD883\uDEDE麺".println(); exitProcess(0) }
@Suppress("FunctionName") fun RE(): Nothing { exitProcess(1) }
@Suppress("FunctionName") fun TLE(): Nothing { while (true) Object().also { synchronized(it) {it.wait()} } }
// endregion
// region 高速入出力のおまじない
// 変数名は全角スペース(どう足掻いても使うことはない)→単純に初期化ブロックとしての役割
val ATCODER = System.getenv("ATCODER") != null
val AUTO_FLUSH = !ATCODER
@Suppress("ObjectPropertyName", "NonAsciiCharacters")
val `　` = run {
    val out = PrintStream(System.out, AUTO_FLUSH)
    System.setOut(out)
    if (!AUTO_FLUSH)
        Runtime.getRuntime().addShutdownHook(thread(start = false) {
            out.flush()
        })
    "(C) 2024 GalaxyCat42"
}
private val scanner = Scanner(System.`in`.buffered())
val int: Int get() = scanner.nextInt()
val long: Long get() = scanner.nextLong()
val str: String get() = scanner.next()
val char: Char get() = str[0]
val line: String get() = scanner.nextLine()
@Suppress("ClassName")
object ints {
    operator fun invoke(n: Int) = IntArray(n).also { for (i in it.indices) it[i]=int }
    infix fun of(n: Int) = this(n)
    operator fun invoke(w: Int, h: Int) = arrayMultiDim(w, h, value=0).also {
        for (y in 0 until h)
            for (x in 0 until w)
                it[x,y]=int
    }
    infix fun of(size: Vec2I) = this(size.x, size.y)
}
infix fun Int.of(`_`: ints) = ints(this)
infix fun Int.of(`_`: longs) = longs(this)
infix fun Vec2I.of(`_`: ints) = ints(x, y)
@Suppress("ClassName")
object longs {
    operator fun invoke(n: Int) = LongArray(n).also { for (i in it.indices) it[i]=long }
    infix fun of(n: Int) = this(n)
}
@Suppress("ClassName")
object chars {
    operator fun invoke(w: Int, h: Int) = arrayMultiDim(w, h, '\u0000').also {
        for (y in 0 until h) {
            val s = str.toCharArray()
            for (x in 0 until w)
                it[x,y]=s[x]
        }
    }
    infix fun of(size: Vec2I) = this(size.x, size.y)
}
fun inty(acc: Int): Long {
    var s = str
    val negative = s[0]=='-'
    if (negative) s=s.substring(1)
    val x = s.split('.')
    if (x.size == 1) return x[0].toLong() e acc
    val pow = acc-x[1].length
    return (x[1].toLong() e pow) + (x[0].toLong() e acc)
}
fun Boolean.println() { println(if (this) Yes else No) }
fun <T> Array<T>.println() { println(joinToString(" "))}
fun IntArray.println() { println(joinToString(" "))}
fun LongArray.println() { println(joinToString(" "))}
fun <T> Iterable<T>.println() { println(joinToString(" "))}
fun Any?.println() { println(this) }
fun flush() = System.out.flush()
// endregion
// region 便宜
inline fun IntArray.apply(func: (Int)->Int): IntArray = also { repeat(it.size) { i -> it[i]=func(it[i]) } }
inline fun LongArray.apply(func: (Long)->Long): LongArray = also { repeat(it.size) { i -> it[i]=func(it[i]) } }
inline fun <T> Array<T>.apply(func: (T)->T): Array<T> = also { repeat(it.size) { i -> it[i]=func(it[i]) } }
inline fun findFirst(min:Int,max:Int,predicate:(Int)->Boolean):Int{var a=min;var b=max;while(b-a!=1){val c=(a+b)/2;if(predicate(c))b=c else a=c};return b}
inline fun findFirst(min:Long,max:Long,predicate:(Long)->Boolean):Long{var a=min;var b=max;while(b-a!=1L){val c=(a+b)/2;if(predicate(c))b=c else a=c};return b}
infix fun Int.bit(bit: Int): Boolean = this and (1 shl bit) != 0
/// region experimental
inline fun <T:Any> bfs(from: T, lookup: (current: T) -> Collection<T>, acceptor: (value: T, depth: Int)->Unit) {
    val deque: Deque<T?> = LinkedList()
    deque.add(from)
    deque.add(null)
    var d=0
    val arrived: MutableSet<T> = Collections.newSetFromMap(IdentityHashMap())
    while (deque.isNotEmpty()) {
        val value = deque.pollFirst()
        if (value == null) {
            d++
            continue
        }
        if (value in arrived) continue
        deque.addAll(lookup(value))
        acceptor(value, d)
    }
}
/// endregion
// endregion
// region 多次元配列絡み
typealias D1Array<T> = Array<T>
typealias D2Array<T> = Array<D1Array<T>>
typealias D3Array<T> = Array<D2Array<T>>
typealias D4Array<T> = Array<D3Array<T>>
typealias D5Array<T> = Array<D4Array<T>>
typealias D6Array<T> = Array<D5Array<T>>
typealias D7Array<T> = Array<D6Array<T>>
typealias D8Array<T> = Array<D7Array<T>>
inline fun <reified T> arrayMultiDim(dim1:Int,value:T):D1Array<T> =Array(dim1){value}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,value:T):D2Array<T> =Array(dim1){arrayMultiDim(dim2,value)}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,dim3:Int,value:T):D3Array<T> =Array(dim1){arrayMultiDim(dim2,dim3,value)}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,dim3:Int,dim4:Int,value:T):D4Array<T> =Array(dim1){arrayMultiDim(dim2,dim3,dim4,value)}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,value:T):D5Array<T> =Array(dim1){arrayMultiDim(dim2,dim3,dim4,dim5,value)}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,value:T):D6Array<T> =Array(dim1){arrayMultiDim(dim2,dim3,dim4,dim5,dim6,value)}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,dim7:Int,value:T):D7Array<T> =Array(dim1){arrayMultiDim(dim2,dim3,dim4,dim5,dim6,dim7,value)}
inline fun <reified T> arrayMultiDim(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,dim7:Int,dim8:Int,value:T):D8Array<T> =Array(dim1){arrayMultiDim(dim2,dim3,dim4,dim5,dim6,dim7,dim8,value)}
operator fun <T> D2Array<T>.get(dim1:Int,dim2:Int):T=this[dim1][dim2]
operator fun <T> D3Array<T>.get(dim1:Int,dim2:Int,dim3:Int):T=this[dim1][dim2,dim3]
operator fun <T> D4Array<T>.get(dim1:Int,dim2:Int,dim3:Int,dim4:Int):T=this[dim1][dim2,dim3,dim4]
operator fun <T> D5Array<T>.get(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int):T=this[dim1][dim2,dim3,dim4,dim5]
operator fun <T> D6Array<T>.get(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int):T=this[dim1][dim2,dim3,dim4,dim5,dim6]
operator fun <T> D7Array<T>.get(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,dim7:Int):T=this[dim1][dim2,dim3,dim4,dim5,dim6,dim7]
operator fun <T> D8Array<T>.get(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,dim7:Int,dim8:Int):T=this[dim1][dim2,dim3,dim4,dim5,dim6,dim7,dim8]
operator fun <T> D2Array<T>.set(dim1:Int,dim2:Int,value:T){this[dim1][dim2]=value}
operator fun <T> D3Array<T>.set(dim1:Int,dim2:Int,dim3:Int,value:T){this[dim1][dim2,dim3]=value}
operator fun <T> D4Array<T>.set(dim1:Int,dim2:Int,dim3:Int,dim4:Int,value:T){this[dim1][dim2,dim3,dim4]=value}
operator fun <T> D5Array<T>.set(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,value:T){this[dim1][dim2,dim3,dim4,dim5]=value}
operator fun <T> D6Array<T>.set(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,value:T){this[dim1][dim2,dim3,dim4,dim5,dim6]=value}
operator fun <T> D7Array<T>.set(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,dim7:Int,value:T){this[dim1][dim2,dim3,dim4,dim5,dim6,dim7]=value}
operator fun <T> D8Array<T>.set(dim1:Int,dim2:Int,dim3:Int,dim4:Int,dim5:Int,dim6:Int,dim7:Int,dim8:Int,value:T){this[dim1][dim2,dim3,dim4,dim5,dim6,dim7,dim8]=value}
// endregion
// region 穴の開いた憎悪
fun primeUntil(to:Int)=mutableListOf<Int>().apply{val b=BitSet(to);for(i in 2..<to){if(b[i])continue;add(i);for(j in 0..<to step i)b.set(j)}}
@Suppress("ClassName","NonAsciiCharacters")data class `𰻞`<T>(val n:T,val v:Long):Comparable<`𰻞`<T>>{override fun compareTo(other:`𰻞`<T>)=v.compareTo(other.v)}
inline fun<T>dijkstra(size:Int,getId:(T)->Int,getChildren:(T)->Iterable<T>,costBetween:(from:T,to:T)->Long,vararg initial:T)=run{val r=LongArray(size){-1};val q=PriorityQueue<`𰻞`<T>>();for(x in initial)q+=`𰻞`(x,0);while(!q.isEmpty()){val (n,c)=q.remove();r[getId(n)]!=-1L&&continue;r[getId(n)]=c;for(d in getChildren(n)){r[getId(d)]!=-1L&&continue;q+=`𰻞`(d,c+costBetween(n,d))}};r.asList()}
fun List<Int>.rot(min:Int,max:Int)=run{val d=-min+1;val b=IntBIT(max-min+1);var r=0L;var j=0;forEach{b.addAt(it+d,1);r+=j++-b.sumUntil(it+d)};r}
fun List<Int>.rot() = rot(min(),max())
//fun List<Int>.compress(): Pair<List<Int>, Map<Int, Int>> {
//
//}
// endregion

提出情報

ジャッジ結果