一、题意理解

1. 片段定义

给定一个由 + 和 - 组成的字符串 $P$，一个片段是满足以下条件的子串 $P[L\dots R]$：

• 子串内所有字符相同。
• 左边没有字符（$L=1$）或者左边字符与子串字符不同。
• 右边没有字符（$R=N$）或者右边字符与子串字符不同。

即极长同色连续段。

例：++--++ 的片段是 [1,2] (++)、[3,4] (--)、[5,6] (++)。

2. 变换规则

一次变换操作：

1. 找到相邻且长度不同的两个片段。
2. 选择较短的片段，将其所有字符翻转为另一种字符（+ ↔ -）。
3. 翻转后，如果该片段与左右相邻片段字符相同，它们会合并成一个更大的片段。

关键点：

• 只有相邻且长度不同的片段才能操作。
• 总是翻转较短的片段。
• 翻转可能引起片段合并，从而改变片段结构。

3. 问题

给定两个字符串 $s$ 和 $t$，问能否通过若干次变换将 $s$ 变成 $t$。

---

二、变换的规律分析

1. 片段的抽象

我们可以将字符串表示为片段序列：

$$(\text{char}_1, \text{len}_1), (\text{char}_2, \text{len}_2), \dots, (\text{char}_k, \text{len}_k) $$

其中相邻片段字符不同。

变换：

• 选择相邻两个片段 $i$ 和 $i+1$，满足 $\text{len}_i \neq \text{len}_{i+1}$。
• 设较短的长度为 $l$，较长长度为 $L$，$l < L$。
• 将较短片段翻转字符，长度不变。
• 翻转后可能合并：
  • 如果与左边片段字符相同，则合并到左边。
  • 如果与右边片段字符相同，则合并到右边。
  • 也可能同时与左右合并（如果左右字符相同且与翻转后字符相同，但这种情况在相邻操作中不会发生，因为原来相邻字符不同）。

重要性质： 翻转短片段 → 短片段长度不变，但字符改变 → 如果与相邻片段字符相同就合并，意味着短片段消失，长度并入相邻的较长片段。

2. 不变量猜想

变换似乎会减少片段数量，并且每次减少一个短片段。
一个自然的猜想：最终能变成目标 $t$ 的充要条件是 $s$ 与 $t$ 的片段数相同，并且长度序列可以匹配。

但仔细看，字符可能不同，因此需要更精细的条件。

---

三、代码解析

1. 总体思路

代码的核心函数是 cal(l, r)，它判断区间 $[l, r]$ 能否通过变换变成全为 $t[l]$ 的字符（并且这段在 $t$ 中是同色的一个片段）。

也就是说，代码将问题转化为：

1. 将 $t$ 按同色片段切分。
2. 对于 $t$ 的每个同色片段区间 $[l, r]$，检查 $s$ 在该区间能否通过变换变成全 $t[l]$。
3. 如果可以，则将该区间 $s$ 直接赋值为 $t[l]$（模拟已经变换完成），然后继续检查下一个区间。
4. 如果所有区间都可行，输出 Yes，否则 No。

2. cal(l, r) 函数详解

bool cal(int l, int r) {
    if ((l > 1 && s[l] == s[l - 1]) || (r < len && s[r] == s[r + 1]))
        return false;
    // ...
}

首先检查边界条件：如果 $l>1$ 且 $s[l]$ 与 $s[l-1]$ 相同，说明 $s$ 中 $[l,r]$ 不是独立的片段（左边有相同字符），这样无法在区间内独立操作（因为片段定义要求左右不同）。
同理右边也要不同。
这一步保证了 $s$ 中 $[l,r]$ 本身构成一个独立的片段集合的完整区间。

---

2.1 构建初始片段序列

int tmp = 1, cnt = 0;
if (s[l] != t[l])
    siz[++cnt] = 0, op[cnt] = t[l];
for (int i = l + 1; i <= r + 1; i++) {
    if (s[i] != s[i - 1])
        siz[++cnt] = tmp, op[cnt] = s[i - 1], tmp = 1;
    else
        tmp++;
}

这里在构建 $s$ 在 $[l, r]$ 内的片段，但特殊处理：

• 如果 $s[l] \neq t[l]$，在最前面插入一个长度为 0、字符为 $t[l]$ 的虚拟片段。
  这是为了模拟目标字符在开头不同时需要一次变换。

例子：
$s[l\dots r] = \text{++--}$, $t[l] = \text{-}$，则开头不同，我们插入虚拟片段 $(0, \text{-})$，然后接着 $s$ 的片段 $(2, +), (2, -)$。
这样表示我们希望开头是 $\text{-}$，但 $s$ 开头是 $\text{+}$，因此需要操作把 $\text{+}$ 变成 $\text{-}$。

循环到 $r+1$ 是为了确保最后一个片段长度被记录。

---

2.2 模拟合并过程

for (int i = 1; i < cnt; i++)
    lst[i + 1] = i, nxt[i] = i + 1;
nxt[cnt] = 0;

建立双向链表，每个节点是一个片段。

while (nxt[1]) {
    bool flag = 0;
    for (int i = 1; nxt[i];) {
        int j = nxt[nxt[i]];
        if (siz[i] > siz[nxt[i]] || siz[nxt[i]] < siz[j]) {
            // 合并
            flag = 1;
            // 更新 i 的长度，跳过中间两个节点
        } else
            i = j;
    }
    if (!flag) break;
}

这里在模拟操作：

• 我们看三个连续的片段 $i$, $i+1$, $i+2$（代码中 i, nxt[i], nxt[nxt[i]]）。
• 检查条件：siz[i] > siz[nxt[i]] 或 siz[nxt[i]] < siz[j]。
  这意味着 $i+1$ 是 $i$ 和 $i+2$ 中较短的那一个，因此可以翻转 $i+1$ 与 $i$ 或与 $i+2$ 合并。

合并操作：

• 将 $i$, $i+1$, $i+2$ 合并成一个片段，长度为三者之和，字符为 $i$ 的字符（因为 $i+1$ 被翻转后会与 $i$ 相同合并，再与 $i+2$ 合并）。
• 删除 $i+1$ 和 $i+2$，更新链表。

为什么是三个一起考虑？
因为翻转 $i+1$ 后，它可能与 $i$ 相同，也可能与 $i+2$ 相同，但一次操作只能与一边合并。
但这里代码的合并规则是：如果 $i+1$ 比左右都短，可以一次操作合并到两边？
不对，一次操作只能翻转 $i+1$，它只能与一边合并（除非两边字符相同，但原来 $i$ 与 $i+2$ 字符不同）。
所以代码的合并逻辑其实是在模拟连续操作：先与一边合并，再与另一边合并，效果相当于一次消除 $i+1$。

---

最终条件：

bool opt = nxt[1];
return !opt;

nxt[1] 为 0 表示最后只剩下一个片段，即合并成功，区间能变成统一字符。
否则合并失败，返回 false。

---

3. 主逻辑 solve()

1. 按 $t$ 的同色片段切分区间。
2. 对每个区间调用 cal(l, r)。
3. 如果某个区间失败，输出 No。
4. 如果成功，将该区间的 $s$ 全部赋值为 $t[l]$（为了后续区间边界正确）。
5. 全部成功则输出 Yes。

---

四、算法正确性简要说明

核心思想：
将 $t$ 的每个同色片段区间独立处理。
对于每个区间，我们检查是否能通过“翻转短片段并合并”的操作，将 $s$ 的该区间变成同一种字符（即 $t$ 的字符）。
检查方法：构建片段链表，反复合并“比左右都短”的中间片段，直到只剩下一个片段（成功）或无法合并（失败）。

为什么这样做充分？
因为变换操作只能在相邻且长度不同的片段进行，且总是翻转短的。
如果存在一个片段比左右都短，它一定会被翻转并合并到某一边，从而减少片段数。
模拟这个过程，如果最终能合并成一个片段，说明可行。

---

五、复杂度

• 每个区间 cal 的复杂度是 $O(\text{片段数})$，因为每次合并减少至少一个片段。
• 总复杂度 $O(\sum |s_i|)$，符合数据范围 $10^6$。

---

六、总结

这道题的关键在于：

1. 片段化表示字符串。
2. 独立处理目标字符串的每个同色区间。
3. 模拟合并：反复消除比左右都短的片段，检查能否合并成单个片段。
4. 正确性基于变换的性质：短片段迟早会被翻转合并。

代码的实现使用链表模拟合并，高效且思路清晰。