XÂU ĐỐI ĐỐI XỨNG

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

constexpr int N = 3e5 + 5;
constexpr ll base = 37;
constexpr ll mod = 1e9 + 3;

// Fenwick Tree để tính tổng nhanh
struct FenwickTree
{
    int a[N], n;
    FenwickTree()
    {
        memset(a, 0, sizeof a);
    }

    void Update(int p, int v)
    {
        for (; p <= n; p += p & -p)
            a[p] += v;
    }

    int Get(int p)
    {
        int ans(0);
        for (; p; p -= p & -p)
            ans += a[p];
        return ans;
    }

    int Get(int l, int r)
    {
        return Get(r) - Get(l - 1);
    }
} f;

int n, l[N], ans(0), piv(0);
string s;
ll has[N], rhas[N], Pow[N];

// Chuẩn bị cho quá trình hash
void HASH(string s)
{
    Pow[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        has[i] = (has[i - 1] * base + s[i] - 'a' + 1) % mod;                       // Hash xuôi
        rhas[n - i + 1] = (rhas[n - i + 2] * base + s[n - i + 1] - 'a' + 1) % mod; // Hash ngược
        Pow[i] = Pow[i - 1] * base % mod;
    }
}

void Read()
{
    cin >> s;
    n = s.size();
    f.n = n;
    s = " " + s;
    HASH(s);
}

// Get hash xuôi
ll Get(int x, int y)
{
    return ((has[y] - has[x - 1] * Pow[y - x + 1]) % mod + mod) % mod;
}

// Get hash ngược
ll rGet(int x, int y)
{
    return ((rhas[x] - rhas[y + 1] * Pow[y - x + 1]) % mod + mod) % mod;
}

void Solve()
{
    // *Tính l_i = Bán kính palindrome tâm (i, i+1)
    for (int i = 1; i < n; ++i)
    {
        // low, mid, high
        int le = 0, minh, hoang = n;

        while (le <= hoang)
        {
            minh = (le + hoang) / 2;
            if (minh <= i && minh <= n - i && Get(i - minh + 1, i + minh) == rGet(i - minh + 1, i + minh))
                le = minh + 1;
            else
                hoang = minh - 1;
        }

        l[i] = hoang;
    }

    // Như anh đã nói hôm trước, điều kiện để thằng j có thể là tâm của palindrome bên phải của palindpalindrome tâm i là:
    /*
        i < j <= i + l_i
        l_j >= j - i
        j - i <= i + l_i - j
    */
    /*
        - i < j <= (i * 2 + l_i) / 2
        - j - l_j <= i
    */

    // Nếu anh thêm các "tâm" vào theo thứ tự (j-l[j]) tăng dần, anh sẽ bỏ được điều kiện 2; chỉ cần kiểm tra điều kiện 1
    vector<int> b;
    b.reserve(n);

    for (int i = 1; i < n; ++i)
        if (l[i] > 0)
            b.emplace_back(i);

    sort(b.begin(), b.end(), [&](const int &x, const int &y)
         { return x - l[x] < y - l[y]; });

    for (int i = 1, j = 0; i < n; ++i)
        if (l[i] > 0)
        {
            while (j < (int)b.size() && b[j] - l[b[j]] <= i)
            {
                f.Update(b[j], 1);
                ++j;
            }

            // low, mid, high
            int lee = i, Min, ho = (i * 2 + l[i]) / 2;
            int sum = f.Get(i + 1, ho);

            while (lee <= ho)
            {
                Min = (lee + ho) / 2;
                if (f.Get(i + 1, Min) < sum)
                    lee = Min + 1;
                else
                    ho = Min - 1;
            }

            if (ans < (lee - i) * 4)
            {
                ans = (lee - i) * 4;
                piv = i;
            }
        }

    if (ans == 0)
        cout << "-1";
    else
        cout << s.substr(piv - ans / 2 + 1, ans);

    cerr << "\n"
         << ans << " " << piv;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}