2026 ICPC 贵州 省赛

点击查看题面

A. 贵州历史文化名城

题目大意

给定一个由两个小写英文字符串 $a$ 和 $b$ 组成的地名拼音，判断该地名是否属于给定的 10 个“省级历史文化名城”之一。若属于省级历史文化名城，输出 Yes；否则（包括属于国家级历史文化名城或完全不属于名城的情况）输出 No。

数据范围：

• $1\le |a|,|b|\le 6$，字符串仅包含小写英文字母。

---

思路

本题属于典型的静态集合查找（Membership Testing）问题。

1. 集合构建： 根据题意，合法目标集合仅包含 10 座省级历史文化名城。将每个地名的拼音拆解为二元组 $(a,b)$，构成静态集合：

$$\mathcal{S}=\{(\text{"fu"},\text{"quan"}),(\text{"an"},\text{"shun"}),(\text{"zhi"},\text{"jin"}),(\text{"si"},\text{"nan"}),(\text{"an"},\text{"long"}),(\text{"da"},\text{"fang"}),(\text{"pu"},\text{"ding"}),(\text{"li"},\text{"ping"}),(\text{"shi"},\text{"qian"}),(\text{"zhen"},\text{"feng"})\}$$

注意题意明确指出“国家级历史文化名城不算作省级历史文化名城”，因此遵义（zun yi）和镇远（zhen yuan）不计入集合 $\mathcal{S}$。 2. 关系判定： 读取输入的两个拼音字符串 $a$ 和 $b$，通过有序集合 std::set 提供的成员检索函数进行判断：

• 若 $(a,b)\in \mathcal{S}$，输出 Yes；
• 若 $(a,b)\notin \mathcal{S}$，输出 No。

由于数据规模极小（$|\mathcal{S}|=10$ 且字符串长度不超过 $6$），利用红黑树或哈希结构进行查找均可在近乎常数时间内完成。

---

复杂度分析

时间复杂度： 预处理阶段插入 $N=10$ 个有序对，单次查询在基于红黑树的 std::set 中耗时为 $\mathcal{O}(L\log N)$，其中 $L=max(|a|,|b|)\le 6$。由于规模固定且极小，单次判定的实际运行时间为 $\mathcal{O}(1)$。

空间复杂度： 集合仅存储 $N$ 组固定常数字符串二元组，消耗辅助空间大小为 $\mathcal{O}(N\cdot L)$，空间复杂度严格为 $\mathcal{O}(1)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
std::set<std::pair<std::string, std::string>> st = {{"fu", "quan"},  {"an", "shun"},  {"zhi", "jin"}, {"si", "nan"},
                                                    {"an", "long"},  {"da", "fang"},  {"pu", "ding"}, {"li", "ping"},
                                                    {"shi", "qian"}, {"zhen", "feng"}};
void fc() {
    std::string a, b; 
    std::cin >> a >> b; 
    std::cout << (st.count({a, b}) ? "Yes" : "No");
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin>>t;
    while (t--) fc();
    return 0;
}

---

B. 福泉

题目大意

给定 $n$ 盏油灯的初始亮度序列 $a_1,a_2,\dots ,a_n$，接下来经历 $q$ 个夜晚。在第 $t$（$1\le t\le q$）个夜晚，依次执行以下两步操作：

1. 整体衰减：所有油灯亮度减 $1$，即 $a_i\leftarrow max(a_i-1,0)$（$1\le i\le n$）；
2. 单点添油：给定参数 $x_t$ 与 $v_t$。若 $x_t\ne 0$，则将第 $x_t$ 盏油灯的亮度提升至 $max(a_{x_t},v_t)$；若 $x_t=0$，则不执行任何操作。

要求在每个夜晚操作结束后输出当前亮度大于 $0$ 的油灯总数；并在全部 $q$ 个夜晚结束后，输出每盏油灯的最终亮度。

数据范围：

• $1\le n,q\le 2\cdot {10}^5$
• $0\le a_i\le {10}^9$
• $0\le x_t\le n$，$0\le v_t\le {10}^9$，且当 $x_t=0$ 时保证 $v_t=0$

---

思路

本题的核心矛盾在于全局区间修改（每轮全体减 $1$）与单点查询/修改的结合。若朴素模拟，单轮时间复杂度为 $\mathcal{O}(n)$，总复杂度达 $\mathcal{O}(n\cdot q)$，在 $n,q\le 2\cdot {10}^5$ 的规模下必然超时。

1. 绝对时间轴与偏移量转化（Offset Technique）

注意到“所有数每轮同步减 $1$ 直至为 $0$”的性质，可以转换参考系，避免显式修改所有元素：

• 设当前已经经历了 $t$ 个夜晚（即经历过 $t$ 次整体衰减）。
• 若一盏灯在第 $t_0$ 个夜晚之后的亮度为 $V$，则在第 $t$ 个夜晚（$t\ge t_0$）其实际亮度为：

$$max(0,V-(t-t_0))=max(0,(V+t_0)-t)$$

• 观察可知，$(V+t_0)$ 是一个不随时间 $t$ 改变的绝对熄灭时间阈值。记 $E_i$ 为第 $i$ 盏灯的绝对失效时间点，只要当前时间满足 $t<E_i$，该油灯即处于点亮状态，其实际亮度为 $E_i-t$；一旦 $t\ge E_i$，该灯熄灭，亮度为 $0$。

2. 动态维护有效集合

利用该性质，维护动态数据结构即可：

• 熄灭检测：将所有处于点亮状态油灯的 $E_i$ 存入有序集合（如 std::multiset）。每天开始时使时间戳 $t\leftarrow t+1$，由于集合单调有序，只需不断检查并移除集合中满足 $E\le t$ 的元素。

• 单点加油：对于修改操作 $(x,v)$：

• 计算该灯当前的实际亮度 $v_{\text{cur}}=max(0,E_x-t)$；

• 新亮度为 $v^{\prime }=max(v_{\text{cur}},v)$。若 $v^{\prime }+t>E_x$，说明该操作使该灯的熄灭时间延后；

• 从集合中移除旧的失效时间 $E_x$（若原先未熄灭），并将新的失效时间 $E_x^{\prime }=v^{\prime }+t$ 插入集合，同时更新数组 $E_x\leftarrow E_x^{\prime }$。

• 数量统计：处于点亮状态的油灯总数即为集合当前的元素个数（size()）。

• 最终状态：所有夜晚结束后，遍历所有油灯，第 $i$ 盏灯的最终亮度即为 $max(0,E_i-t)$。

---

复杂度分析

时间复杂度：

• 初始化：将 $n$ 个初始亮度转换为绝对时间并构建集合，复杂度为 $\mathcal{O}(n\log n)$。
• 时间推进与删除：每个油灯在未被加油的情况下至多被移出集合一次；每次有效的单点加油操作最多引入一次删除与一次插入。整个过程中集合操作的总次数不超过 $\mathcal{O}(n+q)$。
• 单次平衡树插入/删除的复杂度为 $\mathcal{O}(\log n)$。
• 因此，总时间复杂度为 $\mathcal{O}((n+q)\log n)$，可在限定时间内稳定通过。

空间复杂度：

• 静态数组 arr 用于记录每盏灯的失效时间阈值，占用空间 $\mathcal{O}(n)$。
• std::multiset 中同时存在的元素数量最多为 $n$，占用空间 $\mathcal{O}(n)$。
• 总空间复杂度严格为 $\mathcal{O}(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

class ST {
   private:
    std::multiset<int> s;
    std::vector<int> arr;
    int t;

   public:
    void init(std::vector<int>& a) {
        arr = a;
        for (int i : a)
            if (i) s.insert(i);
        t = 0;
    }
    void day() {
        t++;
        while (s.size() && *s.begin() <= t) {
            s.erase(*s.begin());
        }
    }
    void add(int x, int val) {
        if (val + t > arr[x]) {
            auto it = s.find(arr[x]);
            if (it != s.end()) s.erase(it);
            if (val) s.insert(val + t);
            arr[x] = val + t;
        }
    }

    int get(int i) { return std::max(0, arr[i] - t); }

    int size() { return s.size(); }

    void print() {
        for (int x : s) std::cout << x << " ";
        std::cout << endl;
    }
};
void fc() {
    int n, q;
    std::cin >> n >> q;
    std::vector<int> a(n);
    for (int& i : a) std::cin >> i;

    ST st;
    st.init(a);
    while (q--) {
        int x, v;
        std::cin >> x >> v;
        st.day();
        if (x) st.add(x - 1, v);

        std::cout << st.size() << '\n';

        // for (int i = 0; i < n; i++) {
        //     std::cout << st.get(i) << " ";
        // }
        // std::cout << "\n";
        // st.print();
    }

    for (int i = 0; i < n; i++) {
        std::cout << st.get(i) << " ";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    // std::cin>>t;
    while (t--) fc();
    return 0;
}

---

C. 安顺

题目大意

渠首至渠尾共有 $n$ 个分水口，坐标满足 $x_1<x_2<\cdots <x_n$。巡管人于时刻 $0$ 从坐标 $x_1$ 出发，以速度 $1$ 匀速行走，可在任意时刻折返。在时刻 $0$，所有分水口均被视为刚被巡视过。

对每个分水口 $x_i$，任意两次相邻巡视的时间间隔不得超过 $t_i$。判断是否存在一条无限长的巡渠路线满足所有条件。若存在输出 Yes，否则输出 No。

数据范围：

• $1\le n\le 2\cdot {10}^5$
• $1\le x_1<x_2<\cdots <x_n\le {10}^9$
• $1\le t_i\le {10}^9$

---

思路

本题的核心在于分析无限周期巡视过程中，端点覆盖对内部各点施加的刚性几何约束。

1. 往返距离与时间下界约束

若存在一条无限长的巡渠路线，则整条渠道的两端极值点 $x_1$ 与 $x_n$ 必然要被访问无限多次。

考虑任意分水口 $x_i$（$1\le i\le n$）：

• 巡管人离开 $x_i$ 前往右端点 $x_n$ 并最终返回 $x_i$，所经历的最短物理路程为往返距离 $2(x_n-x_i)$；
• 巡管人离开 $x_i$ 前往左端点 $x_1$ 并最终返回 $x_i$，所经历的最短物理路程为往返距离 $2(x_i-x_1)$。

因行进速度为 $1$，路程即为时间。为保证巡视间隔不超标，必须满足以下两个必要条件：

$$2(x_n-x_i)\le t_i\text{且}2(x_i-x_1)\le t_i$$

2. 区间等价转化

将上述两不等式变形为以 $x_i$ 为中心的区间形式：

$$x_n-\frac{t_i}{2}\le x_i\le x_1+\frac{t_i}{2}$$

定义边界有效区间端点：

$$x=x_n-\lfloor \frac{t_i}{2}\rfloor ,y=x_1+\lfloor \frac{t_i}{2}\rfloor$$

由于坐标差 $(x_n-x_i)$ 与 $(x_i-x_1)$ 均为整数，利用下取整的整除性质可知：

$$x_i<x⟺x_n-x_i>\lfloor \frac{t_i}{2}\rfloor ⟺2(x_n-x_i)>t_i$$$$x_i>y⟺x_i-x_1>\lfloor \frac{t_i}{2}\rfloor ⟺2(x_i-x_1)>t_i$$

因此，使用整数除法 t / 2 进行边界判定与原数学命题严格充要等价。

3. 充分性与判定策略

若每个分水口均满足 $x\le x_i\le y$，则采取在端点 $x_1$ 和 $x_n$ 之间往复折返（$x_1\to x_n\to x_1\to \dots$）的巡视路线，任意分水口 $x_i$ 的两次相邻访问间隔交替为 $2(x_n-x_i)$ 和 $2(x_i-x_1)$，均不超过 $t_i$。

因此，只需在线性扫描中检查是否存在点满足 $x_i<x$ 或 $x_i>y$：

• 若存在任意一点越界，则无解，输出 No；
• 若全部点均在合法区间内，则有解，输出 Yes。

---

复杂度分析

时间复杂度：

• 读取坐标序列耗时 $\mathcal{O}(n)$。
• 单次遍历比对各分水口的坐标与允许区间端点，耗时 $\mathcal{O}(n)$。
• 总时间复杂度为 $\mathcal{O}(n)$。

空间复杂度：

• 使用长度为 $n$ 的动态数组存储坐标序列，空间复杂度为 $\mathcal{O}(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void fc() {
    int n;
    std::cin>>n;

    // 读取所有分水口的坐标
    std::vector<ll>a(n);
    for(int i=0;i<n;i++)std::cin>>a[i];
    
    // 左右两端的极值坐标
    ll start=a[0],end=a[n-1];

    for(int i=0;i<n;i++){
        ll t;std::cin>>t;

        // 计算当前分水口允许的合法坐标区间 [x, y]
        ll x=end-t/2,y=start+t/2;

        // 若当前坐标超出有效覆盖范围，则无法维持无限巡渠
        if(a[i]<x||a[i]>y){
            std::cout<<"No\n";return;
        }
    }
    std::cout<<"Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //std::cin>>t;
    while (t--) fc();
    return 0;
}

---

D. 织金

题目大意

设有 $n$ 段菌床，当前菌丝量序列为 $a_1,a_2,\dots ,a_n$，目标菌丝量序列为 $b_1,b_2,\dots ,b_n$，每段菌床的容纳上限为 $M$。 每次操作可任选一段连续菌床 $[l,r]$（$1\le l\le r\le n$），对所有 $i\in [l,r]$ 执行 $a_i\leftarrow min(2a_i,M)$。 求使序列 $a$ 变为序列 $b$ 所需的最少操作次数；若不可能，输出 $-1$。

数据范围：

• $T$ 组测试数据（$1\le T\le {10}^4$）

• $1\le n\le 2\cdot {10}^5$，$\sum n\le 2\cdot {10}^5$

• $1\le M\le {10}^9$

• $0\le a_i,b_i\le M$

---

思路

1. 可行性判定（剪枝）

由于操作本质为区间非严格单调递增变换，单点状态的转移存在极强的代数约束：

• 单调性约束：若存在 $b_i<a_i$，由于数值不可逆减，必定无解。
• 零元不可变性：当 $a_i=0$ 时，由 $min(2\times 0,M)=0$ 可知其状态始终不变，因此若 $b_i>0$ 则无解；反之若 $b_i=0$，则不论覆盖多少次均合法。
• 未触顶精度约束：当 $a_i>0$ 且 $b_i<M$ 时，数值从未被上限截断，其演化必须严格通过翻倍实现。因此必须满足 $a_i\mid b_i$ 且 $\frac{b_i}{a_i}=2^k$（即商为 $2$ 的整数次幂）。
• 触顶可行性：当 $a_i>0$ 且 $b_i=M$ 时，只要操作次数充足，必定能满足 $a_i\cdot 2^k\ge M$ 并被上限截断至 $M$。

2. 操作次数的区间差分模型

设第 $i$ 段菌床实际被操作的次数为 $c_i$。在区间 $[l,r]$ 执行加 $1$ 操作，对应将全 $0$ 序列构造为目标序列 $c$。由经典的差分性质可知，所需的最少区间操作次数为：

$$\sum _{i=1}^{n}max(0,c_i-c_{i-1})(c_0=0)$$

3. 动态松弛与贪心决策

分析每个位置操作次数 $c_i$ 的取值自由度：

• 当 $a_i>0$ 且 $b_i<M$ 时，$c_i$ 具有唯一确定性，必须严格等于下界：

$$c_i=L_i={\log }_2\left(\frac{b_i}{a_i}\right)$$

• 当 $a_i=0$ 且 $b_i=0$ 时，该位置被操作任意次均不改变其数值，其下界 $L_i=0$；
• 当 $a_i>0$ 且 $b_i=M$ 时，只需翻倍至不小于 $M$ 即可，故 $c_i$ 可取任意满足 $c_i\ge L_i=\lceil {\log }_2\left(\lceil \frac{M}{a_i}\rceil \right)\rceil$ 的非负整数。

对于能够自由取值的位置（$b_i=M$ 或 $a_i=0$），考察包含 $c_i$ 的贡献项：

$$g(c_i)=max(0,c_i-c_{i-1})+max(0,c_{i+1}-c_i)$$

• 若 $c_i\in [L_i,c_{i-1}]$，第一项为 $0$，第二项随 $c_i$ 增大单调不增；
• 若 $c_i>c_{i-1}$，第一项以导数 $+1$ 递增，第二项导数为 $-1$ 或 $0$，总导数恒大于等于 $0$。

因此，令 $c_i=max(L_i,c_{i-1})$ 是局部且全局的最优选择——它完全消除了自 $c_{i-1}$ 产生的阶梯上升惩罚，并最大程度地垫高了当前高度以辅助后续位置。从左至右一次线性扫描即可完成最优构造。

---

复杂度分析

时间复杂度：

• 状态合法性校验与向上对数计算均为常数时间操作。
• 差分累加与贪心维护仅需单次遍历数组。
• 每组测试数据耗时 $\mathcal{O}(n)$，总时间复杂度为 $\mathcal{O}(\sum n)$，能够极为充裕地通过全部测试点。

空间复杂度：

• 使用固定长度的全局静态数组维护序列 $a,b,c$，空间复杂度为 $\mathcal{O}(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 5;
int n;
ll m;
ll a[N], b[N], c[N];

int clog2(ll x) {
    ll k = 1;
    int res = 0;
    while (k < x) k <<= 1, res++;
    return res;
}

inline bool Is2(ll x) { return (x & (x - 1)) == 0; }
bool isOk() {
    for (int i = 1; i <= n; i++) {
        if (b[i] < a[i]) return false;
        if (a[i] == 0) {
            if (b[i]) return false;
            continue;
        }
        if (b[i] % a[i] == 0 && Is2(b[i] / a[i])) continue;
        if (b[i] == m) continue;

        return false;
    }
    return true;
}
void Qc() {
    for (int i = 1; i <= n; i++) {
        c[i] = (a[i] == 0 ? 0 : clog2((b[i] + a[i] - 1) / a[i]));
    }
}

int Q() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        if (b[i] == m || a[i] == 0) {
            c[i] =  std::max(c[i],c[i-1]);
        }
        ans += std::max(0LL,c[i] - c[i - 1]);

        
    }
    return ans;
}

void fc() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i++) std::cin >> a[i];
    for (int i = 1; i <= n; i++) std::cin >> b[i];

    if (!isOk()) {
        std::cout << "-1\n";
        return;
    }

    Qc();

    // for (int i = 1; i <= n; i++) std::cout << c[i] << " ";
    // std::cout << '\n';

    std::cout << Q() << "\n";

    // for (int i = 1; i <= n; i++) std::cout << c[i] << " ";
    // std::cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin >> t;
    while (t--) fc();
    return 0;
}

---

K. 石阡

题目大意

给定一个长度为 $n$ 的仅由小写英文字母组成的字符串 $s$。定义一个字符串为“双色”当且仅当其包含的不同字符种类数不超过 2 种。求字符串 $s$ 中既是回文串又是双色的子串总数。只要子串在原串中的区间 $[L,R]$ 不同，即视为不同的子串。

数据范围：

• 测试数据组数 $T$ 满足 $1\le T\le {10}^4$。
• 单组字符串长度 $n$ 满足 $1\le n\le {10}^6$。
• 保证所有测试数据的 $n$ 之和满足 $\sum n\le {10}^6$。

---

思路

本题要求统计同时满足回文性和字符集大小限制（$\le 2$）的子串数量。若直接枚举所有回文子串并验证其字符集，最坏情况下回文子串数量可达 $O(n^2)$ 级别，必然超时。需要结合回文对称性与区间字符集的单调性进行优化。

1. 回文对称性与字符集等价转化

若一个子串 $s[L..R]$ 是回文串，则其前半段与后半段呈镜像对称。

这意味着：回文串 $s[L..R]$ 中所包含的字符集合，与其右半边（即从对称中心到右端点）所包含的字符集合严格相同。

由此，判断一个回文串是否为双色串，等价于判断其从中心向右延伸的半边子串包含的字符种类数是否不超过 2。

2. 双指针维护双色最远右端点

对于给定的起始位置 $l$，随着右端点 $r$ 向右移动，区间 $s[l..r]$ 包含的字符种类数具有单调不减性。

因此，可以利用滑动窗口（双指针）算法，预处理出数组 $max\mathrm{\_}r[l]$，表示以 $l$ 为左端点且满足字符种类数不超过 2 的最远右端点下标。双指针左右端点均单调递增，可在 $O(n)$ 时间内完成预处理。

3. Manacher 算法统一处理回文中心

使用经典的 Manacher 算法，在字符之间插入分隔符 '#' 将原串长度扩展为 $2n+1$ 级别，统一处理奇回文与偶回文。算法在线性时间复杂度内求出每个插值中心 $i$ 的最大回文半径数组 $p[i]$。

4. 统计合法子串贡献

对于扩展串中的每一个回文中心 $i$：

• 根据中心位置的奇偶性，映射出原串中对应的右半边起始下标 $l$，以及该中心最远能向右扩展到的原串下标 $r$：

• 若 $i$ 为奇数（对应原串字符间的缝隙，即偶回文）：起点 $l=\lfloor \frac{i+1}{2}\rfloor -1$，最远右端点 $r=l+\lfloor \frac{p[i]-1}{2}\rfloor -1$；

• 若 $i$ 为偶数（对应原串具体字符，即奇回文）：起点 $l=\frac{i}{2}-1$，最远右端点 $r=l+\lfloor \frac{p[i]}{2}\rfloor -1$。

• 在以 $i$ 为中心的所有回文子串中，其右半段在原串的端点区间为 $[l,r]$。

• 结合双色限制，合法右端点的上限为 $min(max\mathrm{\_}r[l],r)$。

• 因此，该中心对答案的贡献即为合法右端点的数量：

$$max(0,min(max\mathrm{\_}r[l],r)-l+1)$$

将所有回文中心的贡献求和即为最终结果。

---

复杂度分析

• 时间复杂度：

• 字符串扩展与 Manacher 算法：复杂度为 $O(n)$；

• 双指针求解 $max\mathrm{\_}r$ 数组：左右指针均只单调向前移动，复杂度为 $O(n)$；

• 遍历扩展中心统计贡献：单次判定为 $O(1)$，总复杂度为 $O(n)$；

• 对于多组测试数据，总时间复杂度为 $O(\sum n)$，可以在时限内高效通过。

• 空间复杂度：

• 扩展字符串数组 exp_s 及回文半径数组 p 长度为 $2n+O(1)$，空间复杂度为 $O(n)$；

• 存储最远端点的 max_r 数组大小为 $N$，空间复杂度为 $O(n)$；

• 总额外空间复杂度为 $O(n)$。

---

参考代码

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N=1e6+5;

int n;
std::string s;
char exp_s[(N<<1)+3];
int p[(N<<1)+3],max_r[N];
int idx=0;
void expand() {
    idx=2;
    exp_s[0]='$';exp_s[1]='#';
    for (int i = 0; i < s.size(); i++) exp_s[idx++]= s[i],exp_s[idx++]= '#';
    exp_s[idx++]= '%';
}
void get_Manacher_mx() {
    for (int i = 1, r = 0, c = 0; i < idx - 1; i++) {
        p[i] = (r > i) ? min(p[2 * c - i], r - i) : 1;
        while (exp_s[i - p[i]] == exp_s[i + p[i]]) p[i]++;
        if (i + p[i] > r) {
            r = i + p[i];
            c = i;
        }
    }
}

void get_max_r(){
    int cnt[26]={0};
    int d=0;
    for(int i=0,j=0;i<n;i++){
        while(j<n){
            if(cnt[s[j]-'a']==0&&d==2)break;
            if(cnt[s[j]-'a']++ == 0)d++;
            j++;
        }
        max_r[i]=j-1;
        if(--cnt[s[i]-'a']==0)d--;
    }
}

void fc() {
    std::cin>>n>>s; 

    expand();
    get_Manacher_mx();
    get_max_r();

    ll ans=0;
    for(int i=2;i<idx-2;i++){
        if(i&1){
            int l=(i+1)/2-1,r=l+(p[i]-1)/2-1;
            ans+=std::min(max_r[l],r)-l+1;
        }else{
            int l=i/2-1,r=l+p[i]/2-1;
            ans+=std::min(max_r[l],r)-l+1;
        }
    }

    std::cout<<ans<<"\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    std::cin>>t;
    while (t--) fc();
    return 0;
}

---