题目描述

给定一系列“配置”与“删除”操作，每个操作都包含一个或多个数据段（范围）。

• 配置操作：将新下发的范围合并（并集）到已有数据库中，不覆盖已有配置。
• 删除操作：从已有数据库中减去（差集）下发的范围。

最终要求将数据库中的所有区间：

1. 不可再合并；
2. 按从小到大排序；
3. 单个元素的区间以单个数字形式保存。

例如，初始为空，依次下发：

1. algorithm 1-9,10,17-20,15-15
2. undo algorithm 5-11,16

最终结果为 $1-4,15,17-20$。

思路

1. 数据结构：维护一个vector<pair<int,int>> intervals，表示当前已存数据库区间集合。

2. 解析输入：将每个操作行拆分，识别是否为删除（前缀undo），再将“原子数据”如a或a-b转成(a,a)或(a,b)。

3. 合并操作

   • 将待添加的所有区间加入到intervals中；
   • 按左端点升序排序；
   • 依次扫描，将能合并或相邻（若cur.second+1 >= next.first）的区间合并成一个。

4. 删除操作

   • 对于每个现存区间[l,r]，遍历所有待删区间[dl,dr]，在两个区间有重叠时，将[l,r]切分为：

     • (l, dl-1)（若l < dl）
     • (dr+1, r)（若dr < r）

   • 收集所有切分后的区间，再做一次合并与排序以保证结构正确。

5. 输出格式化

   • 对最终intervals，若l==r输出l，否则输出l-r，区间间用逗号隔开；
   • 若空集，输出0。

C++

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

// 将字符串 data 拆分为区间列表
vector<pair<int,int>> parse(const string &data) {
    vector<pair<int,int>> res;
    stringstream ss(data);
    string token;
    while (getline(ss, token, ',')) {
        int dash = token.find('-');
        if (dash == string::npos) {
            int x = stoi(token);
            res.emplace_back(x, x);
        } else {
            int a = stoi(token.substr(0, dash));
            int b = stoi(token.substr(dash+1));
            res.emplace_back(a, b);
        }
    }
    return res;
}

// 对区间列表进行合并（并集）
vector<pair<int,int>> mergeIntervals(vector<pair<int,int>> iv) {
    if (iv.empty()) return {};
    sort(iv.begin(), iv.end());
    vector<pair<int,int>> ans;
    auto [l, r] = iv[0];
    for (int i = 1; i < iv.size(); i++) {
        auto [l2, r2] = iv[i];
        if (r + 1 < l2) {
            ans.emplace_back(l, r);
            l = l2; r = r2;
        } else {
            r = max(r, r2);
        }
    }
    ans.emplace_back(l, r);
    return ans;
}

// 删除操作：从 iv 中减去 del 区间集合
vector<pair<int,int>> subtractIntervals(const vector<pair<int,int>> &iv,
                                        const vector<pair<int,int>> &del) {
    vector<pair<int,int>> cur = iv;
    for (auto [dl, dr] : del) {
        vector<pair<int,int>> tmp;
        for (auto [l, r] : cur) {
            if (r < dl || dr < l) {
                // 无重合，保留
                tmp.emplace_back(l, r);
            } else {
                // 有重合，切分
                if (l < dl) tmp.emplace_back(l, dl - 1);
                if (dr < r) tmp.emplace_back(dr + 1, r);
            }
        }
        cur = move(tmp);
    }
    // 删除后可能产生可合并区间，统一合并
    return mergeIntervals(cur);
}

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

    int n;
    cin >> n;
    vector<pair<int,int>> db;  // 当前数据库区间
    string line;
    getline(cin, line);  // 读掉行尾

    while (n--) {
        getline(cin, line);
        bool isUndo = false;
        string data;
        if (line.rfind("undo", 0) == 0) {
            // 删除操作
            isUndo = true;
            data = line.substr(line.find(' ', 5) + 1);
        } else {
            // 配置操作
            data = line.substr(line.find(' ') + 1);
        }
        auto segs = parse(data);
        if (isUndo) {
            if (!db.empty())
                db = subtractIntervals(db, segs);
        } else {
            // 合并新增区间到 db
            db.insert(db.end(), segs.begin(), segs.end());
            db = mergeIntervals(db);
        }
    }

    // 输出结果
    if (db.empty()) {
        cout << 0;
    } else {
        for (int i = 0; i < db.size(); i++) {
            auto [l, r] = db[i];
            if (l == r) cout << l;
            else cout << l << "-" << r;
            if (i + 1 < db.size()) cout << ",";
        }
    }

    return 0;
}

Python

import sys

def parse(data):
    segs = []
    for token in data.split(','):
        if '-' in token:
            a, b = map(int, token.split('-'))
        else:
            a = b = int(token)
        segs.append((a, b))
    return segs

def merge_intervals(iv):
    if not iv: return []
    iv.sort()
    res = []
    l, r = iv[0]
    for nl, nr in iv[1:]:
        if r + 1 < nl:
            res.append((l, r))
            l, r = nl, nr
        else:
            r = max(r, nr)
    res.append((l, r))
    return res

def subtract_intervals(iv, dels):
    cur = iv
    for dl, dr in dels:
        tmp = []
        for l, r in cur:
            if r < dl or dr < l:
                tmp.append((l, r))
            else:
                if l < dl:
                    tmp.append((l, dl-1))
                if dr < r:
                    tmp.append((dr+1, r))
        cur = tmp
    return merge_intervals(cur)

def main():
    n = int(sys.stdin.readline())
    db = []
    for _ in range(n):
        line = sys.stdin.readline().strip()
        if line.startswith("undo"):
            data = line.split(maxsplit=2)[2]
            segs = parse(data)
            if db:
                db = subtract_intervals(db, segs)
        else:
            data = line.split(maxsplit=1)[1]
            segs = parse(data)
            db.extend(segs)
            db = merge_intervals(db)
    if not db:
        print(0)
    else:
        print(','.join(f"{l}-{r}" if l!=r else str(l) for l, r in db))

if __name__ == "__main__":
    main()

Java

import java.util.*;

public class Main {
    // 解析“a”或“a-b”格式的字符串
    static List<int[]> parse(String data) {
        List<int[]> res = new ArrayList<>();
        for (String token : data.split(",")) {
            if (token.contains("-")) {
                String[] parts = token.split("-");
                res.add(new int[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])});
            } else {
                int x = Integer.parseInt(token);
                res.add(new int[]{x, x});
            }
        }
        return res;
    }

    // 合并区间
    static List<int[]> mergeIntervals(List<int[]> iv) {
        if (iv.isEmpty()) return new ArrayList<>();
        iv.sort(Comparator.comparingInt(a -> a[0]));
        List<int[]> ans = new ArrayList<>();
        int l = iv.get(0)[0], r = iv.get(0)[1];
        for (int i = 1; i < iv.size(); i++) {
            int nl = iv.get(i)[0], nr = iv.get(i)[1];
            if (r + 1 < nl) {
                ans.add(new int[]{l, r});
                l = nl; r = nr;
            } else {
                r = Math.max(r, nr);
            }
        }
        ans.add(new int[]{l, r});
        return ans;
    }

    // 删除区间
    static List<int[]> subtractIntervals(List<int[]> iv, List<int[]> dels) {
        List<int[]> cur = iv;
        for (int[] del : dels) {
            int dl = del[0], dr = del[1];
            List<int[]> tmp = new ArrayList<>();
            for (int[] seg : cur) {
                int l = seg[0], r = seg[1];
                if (r < dl || dr < l) {
                    tmp.add(new int[]{l, r});
                } else {
                    if (l < dl) tmp.add(new int[]{l, dl - 1});
                    if (dr < r) tmp.add(new int[]{dr + 1, r});
                }
            }
            cur = tmp;
        }
        return mergeIntervals(cur);
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        List<int[]> db = new ArrayList<>();
        while (n-- > 0) {
            String line = sc.nextLine();
            boolean isUndo = line.startsWith("undo");
            String data = isUndo
                ? line.split(" ", 3)[2]
                : line.split(" ", 2)[1];
            List<int[]> segs = parse(data);
            if (isUndo) {
                if (!db.isEmpty()) {
                    db = subtractIntervals(db, segs);
                }
            } else {
                db.addAll(segs);
                db = mergeIntervals(db);
            }
        }
        if (db.isEmpty()) {
            System.out.print(0);
        } else {
            StringJoiner sj = new StringJoiner(",");
            for (int[] seg : db) {
                if (seg[0] == seg[1]) sj.add(String.valueOf(seg[0]));
                else sj.add(seg[0] + "-" + seg[1]);
            }
            System.out.print(sj.toString());
        }
    }
}

题目内容

在数通设备进行配置下发时，可能会遇到需要下发一个或多个数据段的场景。例如在配置某协议支持的算法类型时，需要下发配置

如 “$algorithm$ $1-10,15-20$"，用于表明支持的所有算法段范围为 "$1-10,15-20$"。

为了简化用户操作，数据下发往往同时支持散列及段下发模式，同时对数据段的顺序不做要求，也即允许"$algorithm$ $1-9,10,17-20,15-15$”的方式。下发后的数据会整理合并保存在数据库中，合并结果满足以下条件：

1.数据段无法继续合并。

2.数据段从小到大排列。

3.长度为 $1$ 的数据段保存为单个数字形式。

举例来说，"$algorithm$ $1-9,10,17-20,15-15$"下发后数据库中储存的数据为“$1-10,15,17-20$"。

数据合并规则：

• 在数据库已有数据的情况下，用户新下发的配置不会覆盖已有配置，而是将新增的数据段命并到已有数据中

• 例如:数据库中已存在”$1-10,15-20$"时，再下发"$algorithm$ $5-11$"时数据库数据，会合并更新为"$1-11$ , $15-20$"。

数据删除规则：

• 用户下发删除配置时，从已有范围中删除与下发范围重合的范围

• 例如:数据库中已存在”$1-10,15-20$"时，再下发"$undo$ $algorithm$ $5- 11,16$"时，数据库会更新为"$1-4,15,17-20$"。 任务：给定一系列配置/删除操作，输出最后的数据库更新结果。

输入描述

第一行为 $1$ 个整数 $n$ ，表示下发操作的数量，$n<=100$

接下来 $n$ 行每行包含 $1$ 个字符串，表明下发的配置/删除操作。配置操作格式为"$algorithm$ 数据"，删除操作 "$undo$ $algorithm$ 数据"，数据格式如下所示。

字符串数据格式描述：

1.原子数据，单个正整数(“$a$”)、正整数-正整数("$a-b$")，其中 $a<=b$ ，每个数的范围为 $1-65536$

2.字符里组成由原子数据拼接 “,” 组成 ("$a-b,c,d-e$")

注：

1.用例保证所有输入均合法，输入不保证原子数据排序

2.原子数据段的数量不超过 $100$

3.数据库中数据为空时，删除操作视为无效操作

输出描述

$1$ 个字符串，表明合并保存后的数据库结果。数据格式与输入中描述字符串数据格式相同。

若最终数据库为空，输出 $0$

样例1

输入

3
undo algorithm 1-100
algorithm 15-20,1-10
undo algorithm 6,7,8,9-10

输出

1-5,15-20

说明

数据库初始为空

配置 $undo$ $algorithm$ $1-100 =>$无效，仍为空

配置 $algorithm$ $1-10,15-20=>1-10,15-20$

配置 $undo$ $algorithm$ $6,7,8,9-10 =>1-5,15-20$

样例2

输入

2
algorithm 1-10,15-20
algorithm 5-11

输出

1-11,15-20

说明

数据库初始为空

配置 $algorithm$ $1-10,15-20=>1-10,15-20$

配置 $algorithm$ $5-11 =>1-11,15-20$