力扣第 159 场双周赛

比赛时间 2025-06-21。本场周赛国服共 32 人 AK。

《紫罗兰永恒花园》

果然“成长”是一个
具有普世性的主题
所以对 30 岁 40 岁的
男观众和女观众来说
是非常受欢迎的主题

—— ABC Animation 首席执行官：西出将之

T1. 最小相邻交换至奇偶交替（4 分）

解题思路

统计奇数和偶数的频次，再分类讨论。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minSwaps(int[] nums) {
        int[] cnt = new int[2];
        for (int v : nums) cnt[v % 2]++;

        if (Math.abs(cnt[0] - cnt[1]) > 1) return -1;
        if (cnt[0] == cnt[1]) {
            return Math.min(getAns(nums, 0), getAns(nums, 1));
        } else if (cnt[0] > cnt[1]) { // 第一个偶数
            return getAns(nums, 0);
        } else {
            return getAns(nums, 1);
        }
    }

    // st:0 偶数开头 st:1 奇数开头
    private int getAns(int[] nums, int st) {
        int ans = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] % 2 == 0) {
                ans += Math.abs(i - st);
                st += 2;
            }
        }
        return ans;
    }
}

T2. 找到最大三角形面积（4 分）

解题思路

枚举平行于 x 轴情况：底边长度 为 maxXInY - minXInY，高度为 max(y - minY, maxY - y)。平行于 y 轴情况同理。

时间复杂度：O(n)。

参考代码

class Solution {
    public long maxArea(int[][] coords) {
        return Math.max(getAns(coords, 0), getAns(coords, 1));
    }

    // xy_type:0=x 1=y
    private long getAns(int[][] coords, int xy_type) {
        long minY = Integer.MAX_VALUE, maxY = Integer.MIN_VALUE;
        Map<Integer, Integer> minXForY = new HashMap<>();
        Map<Integer, Integer> maxXForY = new HashMap<>();
        for (int[] p : coords) {
            int x = p[xy_type], y = p[1 - xy_type];
            if (y < minY) minY = y;
            if (y > maxY) maxY = y;
            minXForY.merge(y, x, Math::min);
            maxXForY.merge(y, x, Math::max);
        }
        long ans = -1;
        // 处理平行于x轴的边的情况
        for (Map.Entry<Integer, Integer> entry : minXForY.entrySet()) {
            int y = entry.getKey();
            int minXInY = entry.getValue();
            int maxXInY = maxXForY.get(y);
            long base = maxXInY - minXInY;
            if (base <= 0) continue; // 底边长度无效
            long height = Math.max(y - minY, maxY - y);
            if (height <= 0) continue; // 高无效
            ans = Math.max(ans, base * height);
        }
        return ans;
    }
}

T3. 计数质数间隔平衡子数组（5 分）

解题思路

预处理质数 + 滑动窗口最大值最小值。

时间复杂度：O(n)。

参考代码

class Solution {
    static final int MAX_N = (int) 1e5;
    static boolean[] np;

    static {
        np = new boolean[MAX_N + 1];
        np[1] = true;
        for (int i = 2; i * i <= MAX_N; i++) {
            if (!np[i]) {
                for (int j = i * i; j <= MAX_N; j += i) {
                    np[j] = true;
                }
            }
        }
    }

    public int primeSubarray(int[] nums, int k) {
        int n = nums.length, l = 0, r = 0, ans = 0;
        Deque<Integer> maxQ = new ArrayDeque<>(); // maxQ.getFirst() 为区间内最大值下标
        Deque<Integer> minQ = new ArrayDeque<>(); // minQ.getFirst() 为区间内最小值下标

        // 上上个质数位置 last2
        int last = -1, last2 = -1;
        while (r < n) {
            if (!np[nums[r]]) {
                // 1、入
                last2 = last;
                last = r;

                // 这里加不加 = 都可以
                while (!maxQ.isEmpty() && nums[r] > nums[maxQ.getLast()]) maxQ.removeLast();
                maxQ.addLast(r);
                while (!minQ.isEmpty() && nums[r] < nums[minQ.getLast()]) minQ.removeLast();
                minQ.addLast(r);

                while (!maxQ.isEmpty() && !minQ.isEmpty()
                        && nums[maxQ.getFirst()] - nums[minQ.getFirst()] > k) {
                    if (maxQ.getFirst() <= l) maxQ.removeFirst();
                    if (minQ.getFirst() <= l) minQ.removeFirst();
                    l++;
                }
            }
            // 3、更新答案。当右端点固定时，左端点合法范围 [l, last2]
            ans += last2 - l + 1;
            r++;
        }
        return ans;
    }
}

T4. 第 K 小的路径异或和（6 分）

解题思路 & 参考代码

离散化 + 树上启发式合并 + 树状数组。

时间复杂度：O(n log^2 n)。

class Solution {
    List<Integer>[] g;
    int[] vals;
    Map<Integer, List<int[]>> queryMap;
    Map<Integer, Integer> map;
    BIT tr;
    int[] xor, sz, heavy, distinct, cntArr, ans;

    public int[] kthSmallest(int[] par, int[] vals, int[][] queries) {
        int n = vals.length;
        int q = queries.length;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 1; i < n; i++) {
            g[par[i]].add(i);
        }
        this.vals = vals;

        xor = new int[n];
        sz = new int[n];
        heavy = new int[n];
        Arrays.fill(heavy, -1);
        calcXor(0, 0);

        dfs2(0);

        queryMap = new HashMap<>();
        for (int i = 0; i < q; i++) {
            int u = queries[i][0];
            int kj = queries[i][1];
            queryMap.computeIfAbsent(u, k -> new ArrayList<>()).add(new int[]{kj, i});
        }

        int[] allXor = Arrays.copyOf(xor, n);
        Arrays.sort(allXor);
        int m = 0;
        for (int i = 1; i < n; i++) {
            if (allXor[i] != allXor[m]) {
                allXor[++m] = allXor[i];
            }
        }
        distinct = Arrays.copyOf(allXor, m + 1);
        map = new HashMap<>();
        for (int i = 0; i <= m; i++) {
            map.put(distinct[i], i + 1);
        }
        int M = m + 1;

        tr = new BIT(M);
        cntArr = new int[M + 1];
        ans = new int[q];

        dfs(0, true);
        return ans;
    }

    private void calcXor(int u, int prevXor) {
        xor[u] = prevXor ^ vals[u];
        for (int v : g[u]) {
            calcXor(v, xor[u]);
        }
    }

    private void dfs2(int u) {
        sz[u] = 1;
        int maxSize = 0;
        for (int v : g[u]) {
            dfs2(v);
            sz[u] += sz[v];
            if (sz[v] > maxSize) {
                maxSize = sz[v];
                heavy[u] = v;
            }
        }
    }

    private void add(int u) {
        int x = xor[u];
        int id = map.get(x);
        if (cntArr[id] == 0) {
            tr.add(id, 1);
        }
        cntArr[id]++;
    }

    private void remove(int u) {
        int x = xor[u];
        int id = map.get(x);
        cntArr[id]--;
        if (cntArr[id] == 0) {
            tr.add(id, -1);
        }
    }

    private void addTree(int u) {
        Deque<int[]> st = new ArrayDeque<>();
        st.push(new int[]{u, 0});
        while (!st.isEmpty()) {
            int[] curInfo = st.pop();
            int node = curInfo[0];
            int idx = curInfo[1];
            if (idx == 0) {
                add(node);
            }
            if (idx < g[node].size()) {
                int next = g[node].get(idx);
                st.push(new int[]{node, idx + 1});
                st.push(new int[]{next, 0});
            }
        }
    }

    private void removeTree(int u) {
        Deque<int[]> st = new ArrayDeque<>();
        st.push(new int[]{u, 0});
        while (!st.isEmpty()) {
            int[] curInfo = st.pop();
            int node = curInfo[0];
            int idx = curInfo[1];
            if (idx == 0) {
                remove(node);
            }
            if (idx < g[node].size()) {
                int next = g[node].get(idx);
                st.push(new int[]{node, idx + 1});
                st.push(new int[]{next, 0});
            }
        }
    }

    private void dfs(int u, boolean keep) {
        for (int v : g[u]) {
            if (v == heavy[u]) continue;
            dfs(v, false);
        }
        if (heavy[u] != -1) {
            dfs(heavy[u], true);
        }
        add(u);
        for (int v : g[u]) {
            if (v == heavy[u]) continue;
            addTree(v);
        }
        if (queryMap.containsKey(u)) {
            for (int[] q : queryMap.get(u)) {
                int kj = q[0];
                int idx = q[1];
                int total = tr.query(tr.n);
                if (total < kj) {
                    ans[idx] = -1;
                } else {
                    int left = 1, right = tr.n;
                    while (left < right) {
                        int mid = left + (right - left) / 2;
                        if (tr.query(mid) >= kj) {
                            right = mid;
                        } else {
                            left = mid + 1;
                        }
                    }
                    ans[idx] = distinct[left - 1];
                }
            }
        }
        if (!keep) {
            removeTree(u);
        }
    }

    static class BIT {
        int n;
        int[] tree;

        public BIT(int n) {
            this.n = n;
            tree = new int[n + 1];
        }

        int lb(int x) {
            return x & -x;
        }

        void add(int pos, int val) {
            for (; pos <= n; pos += lb(pos)) tree[pos] += val;
        }

        int query(int pos) {
            int ret = 0;
            for (; pos > 0; pos -= lb(pos)) ret += tree[pos];
            return ret;
        }
    }
}

离散化 + 树上启发式合并 + 线段树上二分。

class Solution {
    List<Integer>[] g;
    int[] vals;
    int[] xor, size, son, ans;
    List<int[]>[] queryGroup;

    static class Node {
        Node l, r;
        int sum;
    }

    public int[] kthSmallest(int[] par, int[] vals, int[][] queries) {
        int n = vals.length;
        int q = queries.length;
        g = new ArrayList[n];
        Arrays.setAll(g, e -> new ArrayList<>());
        for (int i = 1; i < n; i++) {
            g[par[i]].add(i);
        }
        this.vals = vals;

        xor = new int[n];
        calcXor(0, 0);
        List<Integer> allValsList = new ArrayList<>();
        for (int x : xor) {
            allValsList.add(x);
        }
        Collections.sort(allValsList);
        Map<Integer, Integer> map = new HashMap<>();
        int idx = 0;
        List<Integer> distinctVals = new ArrayList<>();
        for (int i = 0; i < allValsList.size(); i++) {
            if (i == 0 || !allValsList.get(i).equals(allValsList.get(i - 1))) {
                int x = allValsList.get(i);
                map.put(x, idx);
                distinctVals.add(x);
                idx++;
            }
        }
        int valSize = distinctVals.size();

        size = new int[n];
        son = new int[n];
        Arrays.fill(son, -1);
        dfs1(0);

        queryGroup = new ArrayList[n];
        Arrays.setAll(queryGroup, e -> new ArrayList<>());
        for (int i = 0; i < q; i++) {
            int u = queries[i][0];
            int k = queries[i][1];
            queryGroup[u].add(new int[]{i, k});
        }

        ans = new int[q];
        dfs2(0, true, map, distinctVals, valSize);

        return ans;
    }

    private void calcXor(int u, int prevXor) {
        xor[u] = prevXor ^ vals[u];
        for (int v : g[u]) {
            calcXor(v, xor[u]);
        }
    }

    void dfs1(int u) {
        size[u] = 1;
        for (int v : g[u]) {
            dfs1(v);
            size[u] += size[v];
            if (son[u] == -1 || size[v] > size[son[u]]) {
                son[u] = v;
            }
        }
    }

    Node dfs2(int u, boolean keep, Map<Integer, Integer> map, List<Integer> distinctVals, int valSize) {
        Node root = null;
        if (son[u] != -1) {
            root = dfs2(son[u], true, map, distinctVals, valSize);
        }
        for (int v : g[u]) {
            if (v == son[u]) continue;
            Node childTree = dfs2(v, false, map, distinctVals, valSize);
            root = merge(root, childTree, 0, valSize - 1);
        }
        int x = map.get(xor[u]);
        root = insert(root, 0, valSize - 1, x);
        for (int[] q : queryGroup[u]) {
            int qIdx = q[0];
            int k = q[1];
            if (root == null || root.sum < k) {
                ans[qIdx] = -1;
            } else {
                int pos = query(root, 0, valSize - 1, k);
                ans[qIdx] = distinctVals.get(pos);
            }
        }
        if (!keep) {
            return root;
        }
        return root;
    }

    Node merge(Node a, Node b, int l, int r) {
        if (a == null) return b;
        if (b == null) return a;
        if (l == r) {
            a.sum = 1;
            return a;
        }
        int mid = (l + r) >>> 1;
        a.l = merge(a.l, b.l, l, mid);
        a.r = merge(a.r, b.r, mid + 1, r);
        a.sum = (a.l != null ? a.l.sum : 0) + (a.r != null ? a.r.sum : 0);
        return a;
    }

    Node insert(Node root, int l, int r, int x) {
        if (root == null) {
            root = new Node();
        }
        if (l == r) {
            root.sum = 1;
            return root;
        }
        int mid = (l + r) >>> 1;
        if (x <= mid) {
            root.l = insert(root.l, l, mid, x);
        } else {
            root.r = insert(root.r, mid + 1, r, x);
        }
        root.sum = (root.l != null ? root.l.sum : 0) + (root.r != null ? root.r.sum : 0);
        return root;
    }

    int query(Node root, int l, int r, int k) {
        if (l == r) {
            return l;
        }
        int mid = (l + r) >>> 1;
        int leftSum = (root.l != null) ? root.l.sum : 0;
        if (leftSum >= k) {
            return query(root.l, l, mid, k);
        } else {
            return query(root.r, mid + 1, r, k - leftSum);
        }
    }
}

（全文完）