思路与算法

把特征(l,r)看成有向边，用并查集找忽略方向的连通分量，统计出入度。在每个含边的分量中，所需最少有向迹数为max(1,Σmax(out-in,0))。这些迹之间用新数对连接，最短遗传序列长度为特征数加所有分量的迹数。

正确性说明

每条特征必须至少出现一次。对出度大于入度的顶点，差额需要成为迹的起点，所以正差和是迹数下界；平衡且含边的分量至少1迹。添加从缺入度到缺出度的补边可平衡成欧拉图，删除这些补边恰好得到达到下界的迹分解。跨迹拼接每次只需增加1条新特征边，长度为E+迹数。不同分量或同分量正负差端点不重合，可避免新增(p,p)相邻对。

复杂度

标号上限1000，流式读特征、不存边，时间O(n α(1000)+1000)，空间O(1000)，初始化并查集及度数O(1000)。不重复且l≠r还能推得n≤999000，无需另造较小上限。

易错点

样例“r=a_i+1”应读为下一项a_{i+1}，不是数值加1；题面附了说明。输出是序列顶点个数，所以还要计入每条迹的起点，不只输出补边数。独立小例使用(末项,已覆盖特征集合)状态BFS求真正最短序列。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct DSU {
    vector<int> p, size;
    DSU(int n) : p(n), size(n, 1) {
        iota(p.begin(), p.end(), 0);
    }
    int find(int x) {
        while (x != p[x]) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }
    bool join(int a, int b) {
        a = find(a);
        b = find(b);
        if (a == b)
            return false;
        if (size[a] < size[b])
            swap(a, b);
        p[b] = a;
        size[a] += size[b];
        return true;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    DSU d(1001);
    vector<int> in(1001), out(1001), active(1001);
    for (int i = 0, a, b; i < n; ++i) {
        cin >> a >> b;
        ++out[a];
        ++in[b];
        active[a] = active[b] = 1;
        d.join(a, b);
    }
    vector<int> excess(1001), used(1001);
    for (int i = 1; i <= 1000; ++i)
        if (active[i]) {
            int root = d.find(i);
            used[root] = 1;
            excess[root] += max(0, out[i] - in[i]);
        }
    long long answer = n;
    for (int i = 1; i <= 1000; ++i)
        if (used[i])
            answer += max(1, excess[i]);
    cout << answer << '\n';
}