小红的伪回文子串（hard）
题号：NC275314
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

本题和easy版的唯一区别是数据范围不同！

定义一个字符串的“伪回文值”是：修改最少字符数量使得其变成回文串的修改次数。例如，"abca"的伪回文值是1。任何回文串的伪回文值是0。

现在小红拿到了一个字符串，她希望你求出所有连续子串的伪回文值之和。你能帮帮她吗？

输入描述:

一个仅包含小写字母的字符串。长度不超过200000

输出描述:

所有连续子串的回文值之和。

示例1

输入

复制 
abca

输出

复制 
6

说明

所有长度不小于2的子串的伪回文值都是1。其余子串伪回文值是0。
示例2

输入

复制 
acac

输出

复制 
5