>>109550237
struct SegTree {
var best: [Int]
var pre: [Int]
var suf: [Int]
var len: [Int]
var leftChar: [Character]
var rightChar: [Character]
let size: Int
init(_ s: [Character]) {
let n = s.count
self.size = n
best = Array(repeating: 0, count: 2 * n)
pre = Array(repeating: 0, count: 2 * n)
suf = Array(repeating: 0, count: 2 * n)
leftChar = Array(repeating: "*", count: 2 * n)
rightChar = Array(repeating: "*", count: 2 * n)
len = Array(repeating: 0, count: 2 * n)
for (i, char) in s.enumerated() {
let v = i + size
pre[v] = 1; suf[v] = 1; best[v] = 1; len[v] = 1
update(i, char)
}
}
public mutating func update(_ i: Int,_ char: Character) {
var v = i + size
leftChar[v] = char; rightChar[v] = char
v /= 2
while v > 0 {
let left = 2 * v, right = 2 * v + 1
len[v] = len[left] + len[right]
leftChar[v] = leftChar[left]; rightChar[v] = rightChar[right]
pre[v] = pre[left]; suf[v] = suf[right]
best[v] = max(best[left], best[right])
if rightChar[left] == leftChar[right] {
best[v] = max(best[v], suf[left] + pre[right])
if pre[left] == len[left] { pre[v] = len[left] + pre[right] }
if suf[right] == len[right] { suf[v] = len[right] + suf[left] }
}
v /= 2
}
}
public func q() -> Int { print(best, leftChar, rightChar); return best[1] }
}
