算法配置

题意

系统支持多种算法，每种用正整数 ID 标识。管理员可以分批启用或禁用算法：

  • algorithm ：启用指定范围内的所有算法
  • undo algorithm ：禁用指定范围内的所有算法

其中 由逗号分隔，可以是单个 ID（如 8）或闭区间（如 1-100）。

给定 条操作记录，按顺序执行后，输出最终处于"启用"状态的所有算法 ID。输出时需要合并为最简的、无重叠的、升序排列的区间格式。若没有启用的算法，输出空行。

思路

核心问题是什么？维护一组不重叠的区间，支持"添加区间"和"删除区间"两种操作。

先想添加区间 怎么做。假设我们已经有一组排好序的不重叠区间，新加的 可能和若干个已有区间重叠或相邻（比如已有 ，新加 ，它们能合并成 ）。所以要找到所有与 有交集的区间，把它们和 合并成一个大区间。

再想删除区间 怎么做。找到所有与 有交集的区间，把它们"切掉"与 重叠的部分。一个区间 被切后，可能留下左边的 和/或右边的 。

具体实现上，因为区间始终保持有序且不重叠，可以用以下方式：

  1. 有序容器（C++ 用 set>，Java 用 TreeMap）：利用二分查找快速定位受影响的区间。
  2. 线性扫描（Python / JS）：由于数据规模不大，直接遍历所有区间也能通过。每次操作后重建区间列表。

每条操作记录解析出"启用/禁用"和区间列表，逐个区间执行添加或删除即可。

最后遍历区间列表，单点 输出为 l，否则输出 l-r，逗号分隔。

时间复杂度：设最终区间数为 ，每次操作最坏 ，总共 。

代码

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

set<pair<int,int>> intervals;

void addRange(int l, int r) {
    if (l > r) return;
    int nl = l, nr = r;
    auto it = intervals.lower_bound({l, l});
    if (it != intervals.begin()) {
        --it;
        if (it->second < l - 1) ++it;
    }
    while (it != intervals.end() && it->first <= r + 1) {
        nl = min(nl, it->first);
        nr = max(nr, it->second);
        it = intervals.erase(it);
    }
    intervals.insert({nl, nr});
}

void removeRange(int l, int r) {
    if (l > r) return;
    auto it = intervals.lower_bound({l, l});
    if (it != intervals.begin()) {
        --it;
        if (it->second < l) ++it;
    }
    vector<pair<int,int>> toAdd;
    while (it != intervals.end() && it->first <= r) {
        int il = it->first, ir = it->second;
        it = intervals.erase(it);
        if (il < l) toAdd.push_back({il, l - 1});
        if (ir > r) toAdd.push_back({r + 1, ir});
    }
    for (auto& p : toAdd) intervals.insert(p);
}

vector<pair<int,int>> parseRanges(const string& s) {
    vector<pair<int,int>> res;
    stringstream ss(s);
    string token;
    while (getline(ss, token, ',')) {
        auto pos = token.find('-');
        if (pos != string::npos) {
            int a = stoi(token.substr(0, pos));
            int b = stoi(token.substr(pos + 1));
            res.push_back({a, b});
        } else {
            res.push_back({stoi(token), stoi(token)});
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n; cin.ignore();
    for (int i = 0; i < n; i++) {
        string line; getline(cin, line);
        bool undo = false;
        string rangeStr;
        if (line.substr(0, 4) == "undo") {
            undo = true;
            rangeStr = line.substr(15);
        } else {
            rangeStr = line.substr(10);
        }
        auto ranges = parseRanges(rangeStr);
        for (auto& [l, r] : ranges) {
            undo ? removeRange(l, r) : addRange(l, r);
        }
    }
    string result;
    for (auto& [l, r] : intervals) {
        if (!result.empty()) result += ",";
        result += (l == r) ? to_string(l) : to_string(l) + "-" + to_string(r);
    }
    cout << result << endl;
}

import java.util.*;
import java.io.*;

public class Main {
    static TreeMap<Integer, Integer> intervals = new TreeMap<>();

    static void addRange(int l, int r) {
        if (l > r) return;
        int nl = l, nr = r;
        Integer key = intervals.floorKey(r + 1);
        while (key != null && intervals.get(key) >= l - 1) {
            nl = Math.min(nl, key);
            nr = Math.max(nr, intervals.get(key));
            intervals.remove(key);
            key = intervals.floorKey(r + 1);
        }
        key = intervals.ceilingKey(l - 1);
        while (key != null && key <= r + 1) {
            nr = Math.max(nr, intervals.get(key));
            nl = Math.min(nl, key);
            intervals.remove(key);
            key = intervals.ceilingKey(l - 1);
        }
        intervals.put(nl, nr);
    }

    static void removeRange(int l, int r) {
        if (l > r) return;
        List<int[]> toAdd = new ArrayList<>();
        Integer key = intervals.floorKey(r);
        while (key != null) {
            int ir = intervals.get(key);
            if (ir < l) break;
            intervals.remove(key);
            if (key < l) toAdd.add(new int[]{key, l - 1});
            if (ir > r) toAdd.add(new int[]{r + 1, ir});
            key = intervals.floorKey(r);
        }
        for (int[] p : toAdd) intervals.put(p[0], p[1]);
    }

    static List<int[]> parseRanges(String s) {
        List<int[]> res = new ArrayList<>();
        for (String part : s.split(",")) {
            int idx = part.indexOf('-');
            if (idx != -1) {
                res.add(new int[]{Integer.parseInt(part.substring(0, idx)),
                                  Integer.parseInt(part.substring(idx + 1))});
            } else {
                int v = Integer.parseInt(part);
                res.add(new int[]{v, v});
            }
        }
        return res;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        for (int i = 0; i < n; i++) {
            String line = br.readLine().trim();
            boolean undo = line.startsWith("undo");
            String rangeStr = undo ? line.substring(15) : line.substring(10);
            for (int[] range : parseRanges(rangeStr)) {
                if (undo) removeRange(range[0], range[1]);
                else addRange(range[0], range[1]);
            }
        }
        StringBuilder sb = new StringBuilder();
        for (var e : intervals.entrySet()) {
            if (sb.length() > 0) sb.append(",");
            sb.append(e.getKey().equals(e.getValue()) ?
                      e.getKey() : e.getKey() + "-" + e.getValue());
        }
        System.out.println(sb);
    }
}

import sys

def main():
    data = sys.stdin.buffer.read().decode().split('\n')
    idx = 0
    n = int(data[idx]); idx += 1

    intervals = []  # 有序、不重叠的 (l, r) 列表

    def add_range(l, r):
        if l > r: return
        nl, nr = l, r
        new = []
        merged = False
        for il, ir in intervals:
            if ir < l - 1:
                new.append((il, ir))
            elif il > r + 1:
                if not merged:
                    new.append((nl, nr)); merged = True
                new.append((il, ir))
            else:
                nl = min(nl, il); nr = max(nr, ir)
        if not merged:
            new.append((nl, nr))
        intervals.clear(); intervals.extend(new)

    def remove_range(l, r):
        if l > r: return
        new = []
        for il, ir in intervals:
            if ir < l or il > r:
                new.append((il, ir))
            else:
                if il < l: new.append((il, l - 1))
                if ir > r: new.append((r + 1, ir))
        intervals.clear(); intervals.extend(new)

    def parse_ranges(s):
        res = []
        for part in s.split(','):
            if '-' in part:
                a, b = part.split('-')
                res.append((int(a), int(b)))
            else:
                v = int(part); res.append((v, v))
        return res

    for _ in range(n):
        line = data[idx]; idx += 1
        if line.startswith('undo'):
            undo, rs = True, line[15:]
        else:
            undo, rs = False, line[10:]
        for l, r in parse_ranges(rs):
            remove_range(l, r) if undo else add_range(l, r)

    parts = [str(l) if l == r else f"{l}-{r}" for l, r in intervals]
    print(",".join(parts))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', l => lines.push(l.trim()));
rl.on('close', () => {
    let idx = 0;
    const n = parseInt(lines[idx++]);
    let intervals = [];

    function addRange(l, r) {
        if (l > r) return;
        let nl = l, nr = r;
        const nw = [];
        let merged = false;
        for (const [il, ir] of intervals) {
            if (ir < l - 1) nw.push([il, ir]);
            else if (il > r + 1) {
                if (!merged) { nw.push([nl, nr]); merged = true; }
                nw.push([il, ir]);
            } else { nl = Math.min(nl, il); nr = Math.max(nr, ir); }
        }
        if (!merged) nw.push([nl, nr]);
        intervals = nw;
    }

    function removeRange(l, r) {
        if (l > r) return;
        const nw = [];
        for (const [il, ir] of intervals) {
            if (ir < l || il > r) nw.push([il, ir]);
            else {
                if (il < l) nw.push([il, l - 1]);
                if (ir > r) nw.push([r + 1, ir]);
            }
        }
        intervals = nw;
    }

    function parseRanges(s) {
        return s.split(',').map(p => {
            const d = p.indexOf('-');
            return d !== -1
                ? [parseInt(p.substring(0, d)), parseInt(p.substring(d + 1))]
                : [parseInt(p), parseInt(p)];
        });
    }

    for (let i = 0; i < n; i++) {
        const line = lines[idx++];
        const undo = line.startsWith('undo');
        const rs = undo ? line.substring(15) : line.substring(10);
        for (const [l, r] of parseRanges(rs)) {
            undo ? removeRange(l, r) : addRange(l, r);
        }
    }

    console.log(intervals.map(([l, r]) => l === r ? `${l}` : `${l}-${r}`).join(','));
});