Luogu P16034：NavigableMap 与连锁更新

发表于 分类于 阅读次数：

Luogu P16034：NavigableMap 与连锁更新

题目地址：P16034

这题使用 NavigableMap 维护有序 key 及其计数。当某个 key 的计数达到 5 后，它会被移除，同时把相邻 key 的计数各增加 1；相邻 key 达到阈值后继续递归处理。

实现要点

  • 使用 TreeMap 维护 key 的有序关系。
  • 通过 lowerKey 和 higherKey 找到左右邻居。
  • 用 TreeSet 保存待处理的 key，避免递归过程中反复扫描整个 Map。
  • 每次处理完一个达到阈值的 key 后再从 Map 中删除。

Java 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.NavigableMap;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        new Main().run();
    }

    private void run() throws Exception {
        FastScanner scanner = new FastScanner(System.in);
        StringBuilder output = new StringBuilder();

        int c = scanner.nextInt();
        int m = scanner.nextInt();
        int n = scanner.nextInt();

        NavigableMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < m; i++) {
            map.put(scanner.nextInt(), scanner.nextInt());
        }

        for (int i = 0; i < n; i++) {
            TreeSet<Integer> pending = new TreeSet<>();
            int key = scanner.nextInt();
            int value = map.get(key) + 1;
            map.put(key, value);

            if (value == 5) {
                pending.add(key);
                cascade(map, pending);
            }
            output.append(map.size()).append('\n');
        }

        System.out.print(output);
    }

    private void cascade(
        NavigableMap<Integer, Integer> map,
        TreeSet<Integer> pending
    ) {
        while (!pending.isEmpty()) {
            int key = pending.pollFirst();
            if (!map.containsKey(key)) {
                continue;
            }

            Integer left = map.lowerKey(key);
            Integer right = map.higherKey(key);

            if (left != null) {
                int value = map.get(left) + 1;
                map.put(left, value);
                if (value >= 5) {
                    pending.add(left);
                }
            }
            if (right != null) {
                int value = map.get(right) + 1;
                map.put(right, value);
                if (value >= 5) {
                    pending.add(right);
                }
            }
            map.remove(key);
        }
    }

    private static final class FastScanner {
        private final InputStream input;
        private final byte[] buffer = new byte[1 << 16];
        private int pointer;
        private int length;

        FastScanner(InputStream input) {
            this.input = new BufferedInputStream(input);
        }

        private int read() throws IOException {
            if (pointer >= length) {
                length = input.read(buffer);
                pointer = 0;
                if (length <= 0) {
                    return -1;
                }
            }
            return buffer[pointer++];
        }

        int nextInt() throws IOException {
            int character;
            do {
                character = read();
            } while (character <= ' ' && character != -1);

            int sign = 1;
            if (character == '-') {
                sign = -1;
                character = read();
            }

            int value = 0;
            while (character >= '0' && character <= '9') {
                value = value * 10 + character - '0';
                character = read();
            }
            return value * sign;
        }
    }
}

踩坑记录

这题最后卡在两个细节上：快读实现，以及对已删除 key 的重复处理。使用 map.remove() 后，如果后续又对同一个 key 做 put，需要确认这是否符合题目的连锁规则；不必要的删除和重复插入都可能导致 TLE。