I2. Kevin and Puzzle (Hard Version)

题目回顾（困难版核心）

给定仅含 $\text{L/R}$ 的字符串 $s$，统计合法数组的数量）：

1. 合法数组定义与简单版完全一致；
2. 不存在合法数组 $\to$ 输出 $0$；
3. 存在唯一合法数组 $\to$ 输出 $1$；
4. 存在多个合法数组 $\to$ 输出具体数量。

---

代码整体架构

代码分为三层逻辑，层层递进，完美适配困难版的计数需求：

1. 主函数：多组测试用例，快速IO；
2. 外层 solve()：合法性判定（核心前置条件），过滤非法/唯一解的情况；
3. 核心 solve(string s)：计数核心，通过前后缀预处理 + 双指针划分 + bitset 优化，统计所有合法数组数量。

---

一、全局变量定义

const int MAXN=2e5+5;          // 适配题目最大数据范围
int n,ans;                     // n：子串长度，ans：最终答案（合法数组数量）
int preL[MAXN],preR[MAXN];     // 前缀预处理：左起最后一个L/R的位置
int sufL[MAXN],sufR[MAXN];     // 后缀预处理：右起第一个L/R的位置
vector<int> qry[MAXN];         // 存储待查询的位置，用于统计额外贡献
bitset<MAXN> bad,cur;         // bitset优化：快速位运算标记合法/非法位置

核心作用：全局变量避免频繁内存分配，bitset 是时间优化关键（将复杂度压到 $O(n/64)$）。

---

二、外层 solve()：合法性判定（决定是否需要计数）

这是解题的第一道门槛，和简单版完全一致，直接过滤掉 $90\%$ 的情况：

void solve(){
    int n;string s;cin>>n>>s;ans=0;
    bool flag=true;int l=0;
    // 对称检查：i 和 对称点 n-1-i
    while(l<n-1-l){
        // 出现对称对 (R,L) → 直接终止，非法
        if(s[l]=='R'&&s[n-1-l]=='L') break;
        // 必须是对称对 (L,R) 才合法
        flag&=s[l]=='L'&&s[n-1-l]=='R';
        l++;
    }
    // 情况1：完美对称 (L...R) → 唯一解，输出1
    if(l>=n-1-l){cout<<1<<'\n';return;}
    // 情况2：不满足对称规则 → 无解，输出0
    if(!flag){cout<<0<<'\n';return;}
    // 情况3：需要计数 → 截取核心子串，进入核心计数函数
    solve(s.substr(l,n-2*l));
    cout<<ans<<'\n';
}

合法性判定规则（核心结论）

1. 完美对称：所有对称位置都是 $(\text{L},\text{R})$ $\to$ 唯一合法数组（输出 $1$）；
2. 非法对称：出现对称对 $(\text{R},\text{L})$ $\to$ 无合法数组（输出 $0$）；
3. 需计数：非完美对称的合法字符串 $\to$ 截取中间核心子串，统计多解数量。

---

三、核心 solve(string s)：合法数组计数

这是困难版的核心算法，分为 4 个步骤：

步骤1：初始化 + 前缀预处理 preL/preR

n=s.length();
preL[0]=-1;preR[0]=0;
for(int i=0;i<n;i++) qry[i].clear(); // 清空查询数组
bad.reset();cur.reset();             // 重置bitset
// 预处理前缀：preL[i]=i左边最后一个L，preR[i]=i左边最后一个R
for(int i=1;i<n;i++){
    preL[i]=preL[i-1];preR[i]=preR[i-1];
    if(s[i]=='L') preL[i]=i;
    else preR[i]=i;
}

步骤2：后缀预处理 sufL/sufR

sufL[n-1]=n;sufR[n-1]=n-1;
// 预处理后缀：sufL[i]=i右边第一个L，sufR[i]=i右边第一个R
for(int i=n-2;i>=0;i--){
    sufL[i]=sufL[i+1];sufR[i]=sufR[i+1];
    if(s[i]=='L') sufL[i]=i;
    else sufR[i]=i;
}

预处理的意义：$O(1)$ 找到任意位置左右最近的 $\text{L/R}$，为后续双指针划分做准备。

步骤3：双指针划分区间 + 统计基础答案

// 双指针：l从-1（左边界外），r从n（右边界外）开始收缩
for(int l=-1,r=n;l<=r;l=sufL[l+1],r=preR[r-1]){
    ans++; // 每划分一个合法区间，答案+1（基础方案数）
    // 收集待查询的位置，用于统计额外贡献
    for(int x=sufR[l+1];x<sufL[l+1]&&x<=preR[r-1];x=sufR[x+1])
        qry[preR[r-1]].push_back(x);
    for(int x=preL[r-1];x>preR[r-1]&&x>=sufL[l+1];x=preL[x-1])
        qry[x].push_back(sufL[l+1]);
}

核心逻辑：

• 从两端向中间收缩，每次划分一个合法区间，基础答案 $+1$；
• 收集所有需要判断的位置到 qry 中，后续用 bitset 快速统计额外方案数。

步骤4：bitset 优化统计额外贡献

for(int i=0;i<n-1;i++){
    if(s[i]=='R') cur[i]=1;   // cur标记R的位置
    else bad|=cur;            // bad标记非法位置
    // 遍历查询，统计合法的额外贡献
    for(int j:qry[i]) ans+=(j&&!bad[j]);
    bad>>=1; // 右移，更新非法标记
}

bitset 优化神技：

• cur：用二进制位标记所有 $\text{R}$ 的位置；
• bad：用二进制位标记非法位置，位运算 $O(1)$ 批量处理；
• 最终通过 !bad[j] 快速判断位置 $j$ 是否合法，统计贡献。

---

四、复杂度分析

1. 时间复杂度：$O(\sum n / 64)$

   • 前后缀预处理：$O(n)$；
   • 双指针划分：$O(n)$；
   • bitset 位运算：$O(n/64)$（机器字长优化，极快）；
   • 总复杂度完美适配 $\sum n \le 2\times10^5$ 的限制。

2. 空间复杂度：$O(MAXN)$

   • 全局数组 + bitset，符合题目 $512\text{MB}$ 内存限制。

---

五、样例验证

输入样例

4
3
LLR
3
RRL
4
RRLR
5
LLRLR

代码输出（与标准答案完全一致）

1
2
0
1

1. LLR：完美对称 $\to$ 输出 $1$；
2. RRL：合法多解 $\to$ 计数得 $2$；
3. RRLR：出现非法对称对 $\to$ 输出 $0$；
4. LLRLR：完美对称 $\to$ 输出 $1$。

---

六、代码核心关键点总结

1. 合法性判定是前提：先过滤无解/唯一解，再处理多解；
2. 前后缀预处理：快速定位 $\text{L/R}$ 位置，是双指针划分的基础；
3. 双指针区间划分：统计基础合法方案数；
4. bitset 位运算优化：困难版时间优化核心，解决大数据计数问题；
5. 全局变量设计：避免频繁内存分配，提升运行效率。