12440: 二叉树经
内存限制：256 MB
时间限制：1.000 S
提交：2
解决：0
评测方式：文本比较
命题人：
题目描述
【题目背景】
> 如是我闻。一时，泽拉图在西北旺，奈特伊斯会议室，与欧艾伊阿二十人俱。泽拉图言：“于意云何？前序遍历与后序遍历，可得二叉树不？”众皆言：“不也。”泽拉图言：“于意云何？若有二叉树，非叶结点皆有二子结点，则仅有前序遍历，可得二叉树不？”众皆言：“不也。”泽拉图言：“于意云何？若有二叉树，非叶结点皆有二子结点，且彰所有叶子结点，则仅有前序遍历，可得二叉树不？”众皆言：“可也。”——《二叉树经》
【题目描述】
二叉树的非叶结点用`a`表示，叶子结点用`b`表示。Zeratul需要的是满足“所有的非叶结点都有两个子结点”的二叉树。
现在Zeratul给出了一个`ab`组成的字符串$s_{1\dots n}$，你需要计算出所有的子串，使得这个子串可能是某个符合上述性质二叉树的前序遍历。
输出所有符合条件的不同子串的长度之和。
子串$s_{L_1\dots R_1}$和子串$s_{L_2 \dots R_2}$不同，当且仅当$L_1 \neq L_2$或$R_1 \neq R_2$。
输入
输入包括一行，代表一个`ab`组成的字符串$s_{1\dots n}$。
输出
输出一个整数代表答案。
样例输入 复制
ababb样例输出 复制
11提示
样例解释：满足条件的子串是：$[1,5],[2,2],[3,5],[4,4],[5,5]$。长度之和是$11$。
| 测试点 | $n$ | 特殊性质 |
| :----: | :--------: | :-------------------------------------: |
| 1~2 | $\le 10^6$ | $s$是一个满二叉树的前序遍历 |
| 3~4 | $\le 10^6$ | $s$是一个完全二叉树的前序遍历 |
| 5~8 | $\le 10^3$ | $s$是一个满足题目性质的二叉树的前序遍历 |
| 9~12 | $\le 10^6$ | $s$是一个满足题目性质的二叉树的前序遍历 |
| 13~16 | $\le 10^3$ | 无特殊性质 |
| 17~20 | $\le 10^6$ | 无特殊性质 |