Java题解 | 算法配置

非算法竞赛出生，只听说过线段树没用过，这里给一个力大砖飞的解法

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static TreeMap<Integer, Integer> mp = new TreeMap<>();
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int ruleNum = in.nextInt();
        for (int i = 0; i < ruleNum; i++) {
            String str = in.next();
            int status = 0;
            if(str.contains("undo")){
                status  = 0;
                in.next();
            }
            else{
                status = 1;
            }
            String[] ranges = in.next().split(",");
            for (String s : ranges) {
                String[] startEnd = s.split("-");
                if (startEnd.length == 1)updateTree(Integer.parseInt(startEnd[0]),Integer.parseInt(startEnd[0]), status);
                else updateTree(Integer.parseInt(startEnd[0]), Integer.parseInt(startEnd[1]),status);
            }
        }
        int lastbegin = -1;
        int lastend = -2;
        for (Map.Entry<Integer, Integer>entry : mp.entrySet()) {
            if(lastend < entry.getKey() - 1){
                if(lastend < 0){}
                else{
                    //当区间无交集，即输出结果
                    if(lastend == lastbegin)System.out.print(lastbegin + ",");
                    else System.out.print(lastbegin + "-" + lastend + ",");
                }
                lastbegin = entry.getKey();
                lastend = Math.max(entry.getValue(),lastend);
            }
            else{
                //当区间有交集，合并区间，TreeMap保证了左端点单调严格递增
                lastend = Math.max(entry.getValue(),lastend);
            }
        }
        if(lastbegin == -1)return ;
        else if(lastend == lastbegin)System.out.print(lastbegin);
        else System.out.print(lastbegin + "-" + lastend);

    }
    public static void updateTree(int start, int end, int  ops) {
        if (ops == 1) {
            //由于Hashmap键唯一，因此合并区间
            if(mp.containsKey(start))mp.put(start,Math.max(mp.get(start),end));
            else mp.put(start, end);
            return;
        }
        TreeMap<Integer, Integer> mp1 = new TreeMap<>();
        mp1.putAll(mp);
        for (Map.Entry<Integer, Integer>entry : mp1.entrySet()) {
            if(entry.getKey() >= start && entry.getValue() <= end){
                //被禁用区间包围
                mp.remove(entry.getKey());
            }
            else if(entry.getKey() < start && entry.getValue() > end){
                //包围禁用区间
                mp.put(entry.getKey(),start - 1);
                //由于Hashmap键唯一，因此合并区间
                if(mp.containsKey(end + 1))mp.put(end + 1,Math.max(mp.get(end + 1),entry.getValue()));
                else mp.put(end + 1,entry.getValue());
                
            }
            else if(entry.getKey() < start && entry.getValue() >= start && entry.getValue() <= end){
                //entry.start,start,entry.end,end
                mp.put(entry.getKey(),start - 1);
            }
            else if(end >= entry.getKey() && end < entry.getValue() && start <= entry.getKey()){
                //start, entry.start,end,entry.end
                mp.remove(entry.getKey());
                //由于Hashmap键唯一，因此合并区间
                if(mp.containsKey(end + 1))mp.put(end + 1,Math.max(mp.get(end + 1),entry.getValue()));
                else mp.put(end + 1,entry.getValue());
            }
        }
    }
}