Good Triple
题意翻译
给出01串s,求数对[l,r]个数,使得能找到至少一对[x,k],使1<=x,k<=|s|且l<=x<x+2k<=r且s[x]=s[x+k]=s[x+2k]
题目描述
Toad Rash has a binary string $ s $ . A binary string consists only of zeros and ones.
Let $ n $ be the length of $ s $ .
Rash needs to find the number of such pairs of integers $ l $ , $ r $ that $ 1 \leq l \leq r \leq n $ and there is at least one pair of integers $ x $ , $ k $ such that $ 1 \leq x, k \leq n $ , $ l \leq x < x + 2k \leq r $ , and $ s_x = s_{x+k} = s_{x+2k} $ .
Find this number of pairs for Rash.
输入输出格式
输入格式
The first line contains the string $ s $ ( $ 1 \leq |s| \leq 300\,000 $ ), consisting of zeros and ones.
输出格式
Output one integer: the number of such pairs of integers $ l $ , $ r $ that $ 1 \leq l \leq r \leq n $ and there is at least one pair of integers $ x $ , $ k $ such that $ 1 \leq x, k \leq n $ , $ l \leq x < x + 2k \leq r $ , and $ s_x = s_{x+k} = s_{x+2k} $ .
输入输出样例
输入样例 #1
010101
输出样例 #1
3
输入样例 #2
11001100
输出样例 #2
0
说明
In the first example, there are three $ l $ , $ r $ pairs we need to count: $ 1 $ , $ 6 $ ; $ 2 $ , $ 6 $ ; and $ 1 $ , $ 5 $ .
In the second example, there are no values $ x $ , $ k $ for the initial string, so the answer is $ 0 $ .