题解：环状DNA基因标记的最大恰当基因类数（括号序列+差分计数）

一、题目核心转化

题目中“结构恰当的基因类”本质是 合法括号序列：

• 基因标记 s_i 对应左括号（值为 +1），e_i 对应右括号（值为 -1）。
• 合法括号序列的充要条件：
  1. 左括号总数 = 右括号总数（s_count[i] = e_count[i]）；
  2. 任意前缀的左括号数 ≥ 右括号数（前缀和非负）。

问题转化为：将环状序列从某个位置切开（转化为线性序列），统计最多能满足上述条件的基因类数，并找到最小切开位置。

二、关键分析

1. 候选基因类筛选

首先过滤掉 s_count[i] ≠ e_count[i] 的基因类，这类基因无论怎么切都不可能是合法括号序列，仅保留满足总数相等的候选类。

2. 合法切开位置的数学推导

对于候选基因类 i，其标记按原序列位置排序为 vec = [(pos₀, val₀), (pos₁, val₁), ..., (posₖ₋₁, valₖ₋₁)]（val=±1），计算前缀和数组 pre（pre[0]=0，pre[m] = pre[m-1] + val[m-1]）。

由于 s_count[i] = e_count[i]，前缀和最终为 pre[k] = 0。要使切开后序列的前缀和均非负，需满足：

• 切开位置对应的前缀和 pre[s] 是 pre[0..k] 中的最小值（此时所有后续前缀和均 ≥ pre[s]）。

3. 合法区间映射与差分计数

每个候选基因类 i 的合法切开位置对应一个或多个区间，通过 差分数组 统计每个位置被多少个候选类覆盖：

• 对每个满足 pre[s] = min_pre 的 s，映射为 0-based 切开位置区间 [a, b]；
• 差分数组 diff[a] += 1，diff[b+1] -= 1，最终通过前缀和得到每个位置的覆盖数。

三、算法步骤

1. 输入解析与统计：读取序列，统计每个基因类的 s/e 数量，存储标记的位置和值。
2. 候选类筛选：仅保留 s_count[i] = e_count[i] 的基因类。
3. 前缀和与最小前缀和计算：对每个候选类，计算前缀和数组，找到最小前缀和 min_pre。
4. 合法区间映射：将每个满足条件的 s 映射为切开位置区间，更新差分数组。
5. 差分前缀和与结果查找：计算差分数组的前缀和，找到覆盖数最大且最小的切开位置（转换为 1-based 输出）。

四、C++ 代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    // 存储每个基因类的标记列表（pos, val），val=1(s)/-1(e)
    unordered_map<int, vector<pair<int, int>>> gene_marks;
    // 统计每个基因类的s和e数量
    unordered_map<int, int> s_count, e_count;

    for (int pos = 0; pos < n; ++pos) {
        string token;
        cin >> token;
        char c = token[0];
        int gene = stoi(token.substr(1));
        int val = (c == 's') ? 1 : -1;
        gene_marks[gene].emplace_back(pos, val);
        c == 's' ? s_count[gene]++ : e_count[gene]++;
    }

    // 差分数组：diff[p] 对应0-based切开位置p的覆盖数增量
    vector<int> diff(n + 2, 0);

    for (auto &entry : gene_marks) {
        int gene = entry.first;
        auto &marks = entry.second;
        int s = s_count[gene], e = e_count[gene];
        if (s != e) continue; // 筛选候选基因类

        int k = marks.size();
        vector<int> pre(k + 1, 0);
        for (int i = 0; i < k; ++i) {
            pre[i + 1] = pre[i] + marks[i].second;
        }

        int min_pre = *min_element(pre.begin(), pre.end());
        // 遍历所有满足pre[s_idx] == min_pre的s_idx，映射为合法区间
        for (int s_idx = 0; s_idx <= k; ++s_idx) {
            if (pre[s_idx] != min_pre) continue;

            int a, b;
            if (s_idx == 0) {
                // 区间：[0, marks[0].first]
                a = 0;
                b = marks[0].first;
            } else if (s_idx == k) {
                // 区间：(marks.back().first, n-1]
                a = marks.back().first + 1;
                b = n - 1;
            } else {
                // 区间：(marks[s_idx-1].first, marks[s_idx].first]
                a = marks[s_idx - 1].first + 1;
                b = marks[s_idx].first;
            }

            // 确保区间有效
            if (a > b) continue;
            // 更新差分数组
            diff[a]++;
            if (b + 1 <= n) diff[b + 1]--;
        }
    }

    // 计算前缀和，找到最大覆盖数和最小切开位置（0-based）
    int max_cnt = 0, best_p0 = 0, current = 0;
    for (int p0 = 0; p0 < n; ++p0) {
        current += diff[p0];
        // 优先选覆盖数大的，覆盖数相同时选较小的p0
        if (current > max_cnt || (current == max_cnt && p0 < best_p0)) {
            max_cnt = current;
            best_p0 = p0;
        }
    }

    // 转换为题目要求的1-based切开位置
    cout << best_p0 + 1 << " " << max_cnt << "\n";

    return 0;
}

五、代码解释

1. 输入处理：解析每个标记的类型、基因类和位置，统计 s/e 数量，存储标记信息。
2. 候选类筛选：跳过 s/e 数量不相等的基因类，减少无效计算。
3. 前缀和计算：对每个候选类，计算标记序列的前缀和，找到最小前缀和（关键筛选条件）。
4. 区间映射：将合法的 s_idx 映射为切开位置区间，通过差分数组高效标记覆盖情况。
5. 结果计算：通过差分前缀和得到每个位置的覆盖数，找到最优切开位置（1-based 转换）。

六、时间复杂度与空间复杂度

• 时间复杂度：O(n)。所有步骤的操作均与标记总数 n 线性相关（前缀和计算、区间映射等均为线性遍历）。
• 空间复杂度：O(n)。存储标记信息、前缀和数组和差分数组均需线性空间。

该算法高效处理了 n ≤ 1e6 的数据规模，确保在时间和空间上均满足要求。