Subtask 1

Ta xét mọi xâu con của ~s~ và kiểm tra đó có là một papalindrome không.

Xét một xâu con từ ~i~ đến ~j~ của ~s~, ta kiểm tra xâu con này có là một papalindrome hay không bằng cách:

• Kiểm tra xâu con từ ~i~ đến ~j~ có đối xứng hay không. Đặt ~len~ = ~j - i + 1~, để xâu con từ ~i~ đến ~j~ đối xứng, ~s_{i+k-1} = s_{j-k+1}~ với mọi ~1 \leq k \leq len~.
• Kiểm tra mọi vị trí chẵn của xâu con từ ~i~ đến ~j~ có giống nhau hay không, tương đương với việc ~s_{i+1} = s_{i+3} = s_{i+5} = ...~.

Độ phức tạp: ~O(n^3)~.

Subtask 2

Ý tưởng giống như Subtask 1, tuy nhiên ta thực hiện prepare để có thể kiểm tra trong ~O(1)~.

Ta có mảng ~isPalin[i][j]~ = ~0~/~1~ với ý nghĩa xâu con từ ~i~ đến ~j~ có đối xứng hay không.

• ~isPalin[i][i]~ = ~1~.
• ~isPalin[i][i+1]~ = ~(s_i == s_{i+1})~.
• ~isPalin[i][j]~ = ~(isPalin[i+1][j-1]~ ~\&\&~ ~s_i == s_j)~ với ~i + 1 < j~.

Nhận thấy các vị trí ~i+1, i+3, i+5, ...~ có tính chẵn lẻ giống nhau, ta chuẩn bị hai mảng ~odd~ và ~even~ với ~odd[i][j]~ là giá trị của các vị trí lẻ trong đoạn từ ~i~ đến ~j~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau, ~even[i][j]~ là giá trị của các vị trí chẵn trong đoạn từ ~i~ đến ~j~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau.

Ta tính mảng ~odd~ như sau:

• ~odd[i][i+1]~ = ~s_i~ nếu ~i~ lẻ, ngược lại = ~s_{i+1}~.
• ~odd[i][j]~ = ~odd[i][j-1]~ nếu ~j~ chẵn hoặc ~odd[i][j-1] == s_j~, ngược lại = ~-1~.

Ta tính mảng ~even~ giống mảng ~odd~.

Sử dụng ba mảng ~isPalin, odd, even~ ta có thể for mọi xâu con ~i~ đến ~j~ của ~s~ và check trong O(~1~).

Độ phức tạp: ~O(n^2)~.

Subtask 3

Xét một xâu papalindrome ~t~ có độ dài ~2*m~, ta có:

• ~t_1 = t_{2*m}~, ~t_2 = t_{2*m-1}~, ~t_3 = t_{2*m-2}~, ...
• Lại có ~t_2 = t_4 = ... = t_{2*m}~ ~\Rightarrow~ ~t_1 = t_2 = ... = t_{2*m}~.

~\Rightarrow~ Xâu papalindrome độ dài chẵn là xâu có tất cả các kí tự giống nhau, có thể dễ dàng tính được.

Với xâu papalindrome độ dài lẻ, với mỗi vị trí ~i~, ta đi tính ~len_i~ là giá trị lớn nhất sao cho xâu ~s_{i-len_i+1...i+len_i-1}~ là xâu palindrome. Để tính ~len_i~, ta có thể dùng thuật toán Manacher hoặc Binary Search kết hợp Hashing.

Ta sử dụng thuật toán RMQ để tính hai mảng ~odd~ và ~even~ với ~odd[i][j]~ là giá trị ở vị trí lẻ trong đoạn ~i...i+2^j-1~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau, ~even[i][j]~ là giá trị các vị trí chắn trong đoạn ~i...i+2^j-1~ hoặc ~-1~ nếu có ít nhất hai giá trị khác nhau.

Chặt nhị phân tìm được vị trí ~p_1~ là vị trí chẵn nhỏ nhất ~\geq i - len_i + 1~ thỏa mãn ~l_1 = i - p_1 + 1~ thì tất cả các vị trí lẻ trong khoảng ~i - l_1 + 1 ... i + l_1 - 1~ bằng nhau, đáp án của ta cộng vào số lượng vị trí chẵn trong khoảng ~p_1...i~. Ta làm tương tự để tính ~p_2~ lẻ và tính đáp án.

Code mẫu

//TrungNotChung
#include <bits/stdc++.h>
#define pii pair<int , int>
#define fi first
#define se second
#define BIT(x,i) (1&((x)>>(i)))
#define MASK(x)  (1LL<<(x))
#define CNT(x) __builtin_popcountll(x)
#define task "tnc"  

using namespace std;
const int N = (int)2e5+228;
const int logn = 18;

int n, len[N];
char a[N];
int odd[N][logn+1], even[N][logn+1];
int cnt[N];

int combine(int x, int y)
{
    if(x == 0) return y;
    if(y == 0) return x;
    if(x == y) return x;
    return -1;
}

void manacher_odd()
{
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        len[i] = max(0, min(r - i, len[l + (r - i)]));
        while(a[i - len[i]] == a[i + len[i]]) {
            len[i]++;
        }
        if(i + len[i] > r) {
            l = i - len[i], r = i + len[i];
        }
    }
}

int getOdd(int l, int r)
{
    int k = log2(r - l + 1);
    return combine(odd[l][k], odd[r-MASK(k)+1][k]);
}

int getEven(int l, int r)
{
    int k = log2(r - l + 1);
    return combine(even[l][k], even[r-MASK(k)+1][k]);
}

bool check1(int mid, int len)
{
    int l = mid - (len * 2) + 1, r = mid + (len * 2) - 1;
    if(l >= r) return true;
    if(mid & 1) return getOdd(l, r) != -1;
    return getEven(l, r) != -1;
}

bool check2(int mid, int len)
{
    int l = mid - (len * 2 - 1) + 1, r = mid + (len * 2 - 1) - 1;
    // if(mid == 7) cout << len << " " << l << " " << r << " " << getEven(l, r) << '\n';
    if(l >= r) return true;
    if(mid & 1) return getEven(l, r) != -1;
    return getOdd(l, r) != -1;
}

void solve()
{
    cin >> n;
    a[0] = -1, a[n+1] = -2;
    for(int i=1; i<=n; ++i)
        cin >> a[i];
    long long res = 0;
    int cur = 0;
    for(int i=1; i<=n; ++i)
    {
        if(a[i] != a[i-1]) cur = 1;
        else ++cur;
        res += cur / 2;
    }
    // cout << res << '\n';
    for(int i=1; i<=n; ++i)
        if(i&1) odd[i][0] = a[i];
        else even[i][0] = a[i];
    for(int j=1; MASK(j) <= n; ++j)
        for(int i=1; i+MASK(j)-1 <= n; ++i)
        {
            odd[i][j] = combine(odd[i][j-1], odd[i+MASK(j-1)][j-1]);
            even[i][j] = combine(even[i][j-1], even[i+MASK(j-1)][j-1]);
        }
    manacher_odd();

    for(int i=1; i<=n; ++i)
    {
        int l = 1, r = len[i]/2, tmp = 0;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(check1(i, mid))
                tmp = mid, l = mid + 1;
            else r = mid - 1;
        }
        res += tmp;
        cnt[i] += tmp;
        // cout << len[i] << " " << tmp << " ";
        l = 1, r = (len[i] + 1) / 2, tmp = 0;
        while(l <= r)
        {
            int mid = (l+r)/2;
            if(check2(i, mid))
                tmp = mid, l = mid + 1;
            else r = mid - 1;
        }
        // cout << tmp << '\n';
        res += tmp;
        cnt[i] += tmp;
    }
    cout << res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // #ifndef ONLINE_JUDGE
    // freopen(task".inp","r",stdin);
    // freopen(task".out","w",stdout);
    // #endif // ONLINE_JUDGE
    solve();
    return 0;
}