题目理解

我们有三种初始基因序列 $S_A$, $S_B$, $S_C$（长度均为 $N$），可以通过杂交产生新的序列。杂交规则是：对于每个位置 $i$，如果亲本两个字符相同，则后代字符相同；如果不同，则后代字符是第三个不同的字符。

给定一个初始序列 $T_0$ 和 $Q$ 次修改操作，每次将序列的 $[L_j, R_j]$ 区间内所有字符改为 $C_j$。对于每次修改后得到的序列 $T_j$，判断是否能通过初始三朵花的序列经过任意次杂交得到。

---

关键观察

1. 杂交运算的代数性质

杂交运算可以看作是在字符集 $\{\texttt{J}, \texttt{O}, \texttt{I}\}$ 上定义的一种运算。通过观察运算表可以发现：

• 这个运算满足交换律
• 每个字符都是自身的逆元（$\text{杂交}(x, x) = x$）
• 运算具有类似异或的性质：$\text{杂交}(a, b) = c$ 当且仅当 $\text{杂交}(a, c) = b$ 且 $\text{杂交}(b, c) = a$

2. 序列杂交的向量化表示

我们可以将每个字符映射到 $\mathbb{Z}_3$ 中的元素（例如：$\texttt{J} \to 0$, $\texttt{O} \to 1$, $\texttt{I} \to 2$）。那么杂交运算就变成了 $\mathbb{Z}_3$ 上的加法运算：

$$\text{杂交}(a, b) = -(a + b) \mod 3$$

其中负号表示加法逆元。

3. 可达序列的判定条件

设三个初始序列为 $A$, $B$, $C$。对于任意目标序列 $T$，考虑它们的差序列：

令 $X = \text{杂交}(A, B)$，$Y = \text{杂交}(A, C)$，$Z = \text{杂交}(B, C)$。

通过代数运算可以证明：一个序列 $T$ 可以通过初始序列杂交得到，当且仅当存在 $\alpha, \beta \in \mathbb{Z}_3$ 使得：

$$T = A + \alpha \cdot X + \beta \cdot Y \quad (\text{在} \mathbb{Z}_3 \text{上}) $$

其中 $X$ 和 $Y$ 线性无关（即它们不是倍数关系）。

---

算法设计

1. 预处理

映射到整数

int char_to_int(char c) {
    if(c == 'J') return 0;
    if(c == 'O') return 1;
    return 2; // 'I'
}

计算基向量

计算两个关键的差向量 $X$ 和 $Y$：

for(int i = 0; i < n; i++) {
    X[i] = (3 - (A[i] + B[i]) % 3) % 3;  // 杂交(A,B)
    Y[i] = (3 - (A[i] + C[i]) % 3) % 3;  // 杂交(A,C)
}

哈希预处理

为了快速判断序列是否可达，我们使用哈希来存储所有可达序列：

• 将所有可达序列的哈希值存入集合
• 通过 BFS 生成所有可达序列

2. 查询处理

线段树维护当前序列

由于需要支持区间修改，使用线段树维护当前序列 $T$ 的哈希值：

struct SegmentTree {
    struct Node {
        int hash;    // 区间哈希值
        int lazy;    // 懒惰标记（区间赋值）
        int len;     // 区间长度
    };
    
    void push_up(int p) {
        // 合并左右子树的哈希值
        t[p].hash = (t[ls(p)].hash * pow_base[t[rs(p)].len] 
                    + t[rs(p)].hash) % MOD;
    }
    
    void update(int l, int r, int p, int val) {
        // 区间赋值为val
        if(区间完全包含) {
            设置懒惰标记;
            t[p].hash = 预计算的哈希值[val][长度];
            return;
        }
        下传标记;
        递归更新;
        合并哈希值;
    }
};

快速查询

对于每个查询，计算当前序列 $T$ 的哈希值，判断是否在可达集合中：

if(reachable_set.count(T.get_hash())) 
    cout << "Yes\n";
else 
    cout << "No\n";

---

算法正确性

1. 线性空间的性质

可达序列构成一个 $\mathbb{Z}_3$ 上的线性空间，由 $A$, $X$, $Y$ 张成。由于 $X$ 和 $Y$ 通常线性无关，这个空间的维度为 3，包含 $3^N$ 个序列。

2. 哈希的可靠性

使用双哈希或大质数哈希可以几乎完全避免碰撞，确保判断的准确性。

3. 生成算法的完备性

通过 BFS 生成所有可达序列是完备的，因为：

• 初始序列可达
• 如果 $S$ 和 $T$ 可达，那么 $\text{杂交}(S, T)$ 也可达
• BFS 会探索所有可能的杂交组合

---

复杂度分析

时间复杂度

• 预处理（生成可达序列）：

  • 最坏情况：$O(3^N)$，但实际上由于线性空间的限制，可达序列数最多为 $\min(3^N, 3^{\text{rank}})$，其中 $\text{rank} \leq 3$
  • 在实际数据中，通常很快收敛

• 每次查询：

  • 线段树更新：$O(\log N)$
  • 哈希查询：$O(1)$

总复杂度：$O(3^{\min(N,3)} + Q \log N)$，对于 $N \leq 2\times 10^5$，$3^{\min(N,3)} \leq 27$ 很小。

空间复杂度

• 可达序列哈希集合：$O(3^{\min(N,3)}) \leq O(27)$
• 线段树：$O(N)$
• 预计算的哈希值：$O(N)$

---

代码实现要点

1. 哈希函数设计

const int MOD1 = 1000000007, MOD2 = 1000000009;
const int BASE1 = 137, BASE2 = 151;

pair<int, int> get_hash(string s) {
    int h1 = 0, h2 = 0;
    for(char c : s) {
        h1 = (1LL * h1 * BASE1 + c) % MOD1;
        h2 = (1LL * h2 * BASE2 + c) % MOD2;
    }
    return {h1, h2};
}

2. BFS 生成可达序列

queue<string> q;
set<pair<int, int>> visited;

for(auto &s : initial_strings) {
    auto h = get_hash(s);
    if(!visited.count(h)) {
        visited.insert(h);
        q.push(s);
    }
}

while(!q.empty()) {
    string cur = q.front(); q.pop();
    
    for(auto &s : all_strings) {
        string nxt = hybrid(cur, s);
        auto h = get_hash(nxt);
        
        if(!visited.count(h)) {
            visited.insert(h);
            q.push(nxt);
        }
    }
}

3. 线段树的优化

预计算每个字符的哈希值前缀，加速区间赋值操作：

// 预计算：hash_char[c][len] = cccc... (len个c) 的哈希值
for(char c : {'J', 'O', 'I'}) {
    for(int len = 1; len <= n; len++) {
        hash_char[c][len] = (hash_char[c][len-1] * BASE + c) % MOD;
    }
}

---

算法标签

• 线段树
• 广度优先搜索
• 模运算
• 向量
• 枚举

---

总结

本题通过代数转化和数据结构优化，将看似复杂的杂交问题转化为高效的动态维护问题。关键在于发现可达序列的线性结构，并利用哈希和线段树实现快速判定。