对顶堆/双平衡树

题目	难度
2653. 滑动子数组的美丽值	中等	区间内第 k 小
Abc281_e		区间内前 k 小的和
Abc306_e		区间内前 k 大的和

多重集

https://atcoder.jp/contests/abc306/editorial/6612

Here, we use a multiset (a data structure that manages a multiset). Any data structure that supports the following operations can be used.

• Storing a multiset. In other words, it can maintain multiple copies of the same value.
• Accessing the maximum (or minimum) value (or both).
• Removing a specific element.

这里，我们使用 multiset(一种管理 multiset 的数据结构)。支持以下操作的任何数据结构都可以使用。

• 存储多集。换句话说，它可以维护相同值的多个副本。
• 访问最大值(或最小值)(或两者)。
• 移除特定的元素。

双多重集对比双堆，可以做到 O(logn) 精确删除指定元素，而堆只能做到 O(n)。

2653. 滑动子数组的美丽值

import java.util.TreeMap;

public class Solution2653 {
    public int[] getSubarrayBeauty(int[] nums, int k, int x) {
        int n = nums.length;
        int[] ans = new int[n - k + 1];

        // 转换成从 0 开始的下标
        x--;
        // 第x小 等价于 第k-x大
        MultiSets multiSets = new MultiSets(k, k - x);
        for (int i = 0; i < k; i++) {
            multiSets.add(nums[i]);
        }
        ans[0] = Math.min(0, multiSets.xMap.firstKey());

        for (int i = k; i < n; i++) {
            multiSets.add(nums[i]);
            multiSets.del(nums[i - k]);

            ans[i - k + 1] = Math.min(0, multiSets.xMap.firstKey());
        }
        return ans;
    }

    private static class MultiSets {
        int n, k;
        TreeMap<Integer, Integer> xMap, yMap;
        int xsz, ysz;

        // n:窗口大小, k:第 k 大
        public MultiSets(int n, int k) {
            this.n = n;
            this.k = k;
            this.xMap = new TreeMap<>();
            this.yMap = new TreeMap<>();
            this.xsz = 0;
            this.ysz = 0;
        }

        private void add(int v) {
            yInsertV(v);
            balance();
        }

        private void del(int v) {
            if (xMap.containsKey(v)) {
                xEraseV(v);
            } else {
                yEraseV(v);
            }
            balance();
        }

        private void balance() {
            if (xsz + ysz < n) return;
            while (xsz < k) {
                int iy = yMap.lastKey();
                yEraseV(iy);
                xInsertV(iy);
            }
            if (xsz == 0 || ysz == 0) return;
            while (true) {
                int ix = xMap.firstKey();
                int iy = yMap.lastKey();
                if (ix >= iy) break;
                xEraseV(ix);
                yEraseV(iy);
                xInsertV(iy);
                yInsertV(ix);
            }
        }

        private void xInsertV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) + 1);
            xsz++;
        }

        private void yInsertV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) + 1);
            ysz++;
        }

        private void xEraseV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) - 1);
            if (xMap.get(v) == 0) xMap.remove(v);
            xsz--;
        }

        private void yEraseV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) - 1);
            if (yMap.get(v) == 0) yMap.remove(v);
            ysz--;
        }
    }
}

Abc281_e

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class Abc281_e {
    static int n, m, k;
    static int[] a;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    private static String solve() {
        long[] ans = new long[n - m + 1];

        // 前k小的和 等价于 总和减去前m-k大的和
        MultiSets multiSets = new MultiSets(m, m - k);
        for (int i = 0; i < m; i++) {
            multiSets.add(a[i]);
        }
        ans[0] = multiSets.tot - multiSets.sumX;

        for (int i = m; i < n; i++) {
            multiSets.add(a[i]);
            multiSets.del(a[i - m]);

            ans[i - m + 1] = multiSets.tot - multiSets.sumX;
        }
        return Arrays.stream(ans).mapToObj(String::valueOf).collect(Collectors.joining(" "));
    }

    private static class MultiSets {
        int n, k;
        TreeMap<Integer, Integer> xMap, yMap;
        int xsz, ysz;
        long sumX, tot;

        // n:窗口大小, k:第 k 大
        public MultiSets(int n, int k) {
            this.n = n;
            this.k = k;
            this.xMap = new TreeMap<>();
            this.yMap = new TreeMap<>();
            this.xsz = 0;
            this.ysz = 0;
            sumX = 0;
        }

        private void add(int v) {
            yInsertV(v);
            balance();
            tot += v;
        }

        private void del(int v) {
            if (xMap.containsKey(v)) {
                xEraseV(v);
            } else {
                yEraseV(v);
            }
            balance();
            tot -= v;
        }

        private void balance() {
            if (xsz + ysz < n) return;
            while (xsz < k) {
                int iy = yMap.lastKey();
                yEraseV(iy);
                xInsertV(iy);
            }
            if (xsz == 0 || ysz == 0) return;
            while (true) {
                int ix = xMap.firstKey();
                int iy = yMap.lastKey();
                if (ix >= iy) break;
                xEraseV(ix);
                yEraseV(iy);
                xInsertV(iy);
                yInsertV(ix);
            }
        }

        private void xInsertV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) + 1);
            xsz++;
            sumX += v;
        }

        private void yInsertV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) + 1);
            ysz++;
        }

        private void xEraseV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) - 1);
            if (xMap.get(v) == 0) xMap.remove(v);
            xsz--;
            sumX -= v;
        }

        private void yEraseV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) - 1);
            if (yMap.get(v) == 0) yMap.remove(v);
            ysz--;
        }
    }
}

Abc306_e

import java.nio.charset.StandardCharsets;
import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class Abc306_e {
    static int n, k, q;
    static int[][] xy;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8);
        n = scanner.nextInt();
        k = scanner.nextInt();
        q = scanner.nextInt();
        xy = new int[q][2];
        for (int i = 0; i < q; i++) {
            xy[i][0] = scanner.nextInt();
            xy[i][1] = scanner.nextInt();
        }
        System.out.println(solve());
    }

    // https://atcoder.jp/contests/abc306/editorial/6612
    private static String solve() {
        MultiSets multiSets = new MultiSets(n, k);
        for (int i = 0; i < n; i++) {
            multiSets.add(0);
        }

        long[] ans = new long[q];
        int[] a = new int[n];
        for (int i = 0; i < q; i++) {
            int x = xy[i][0] - 1;
            int y = xy[i][1];

            multiSets.add(y);
            multiSets.del(a[x]);
            a[x] = y;

            ans[i] = multiSets.sumX;
        }
        return Arrays.stream(ans).mapToObj(String::valueOf).collect(Collectors.joining(System.lineSeparator()));
    }

    // 多重集
    private static class MultiSets {
        int n, k;
        TreeMap<Integer, Integer> xMap, yMap;
        int xsz, ysz;
        long sumX;

        // n:窗口大小, k:第 k 大
        public MultiSets(int n, int k) {
            this.n = n;
            this.k = k;
            this.xMap = new TreeMap<>();
            this.yMap = new TreeMap<>();
            this.xsz = 0;
            this.ysz = 0;
            sumX = 0;
        }

        private void add(int v) {
            yInsertV(v);
            balance();
        }

        private void del(int v) {
            if (xMap.containsKey(v)) {
                xEraseV(v);
            } else {
                yEraseV(v);
            }
            balance();
        }

        private void balance() {
            if (xsz + ysz < n) return;
            while (xsz < k) {
                int iy = yMap.lastKey();
                yEraseV(iy);
                xInsertV(iy);
            }
            if (xsz == 0 || ysz == 0) return;
            while (true) {
                int ix = xMap.firstKey();
                int iy = yMap.lastKey();
                if (ix >= iy) break;
                xEraseV(ix);
                yEraseV(iy);
                xInsertV(iy);
                yInsertV(ix);
            }
        }

        private void xInsertV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) + 1);
            xsz++;
            sumX += v;
        }

        private void yInsertV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) + 1);
            ysz++;
        }

        private void xEraseV(int v) {
            xMap.put(v, xMap.getOrDefault(v, 0) - 1);
            if (xMap.get(v) == 0) xMap.remove(v);
            xsz--;
            sumX -= v;
        }

        private void yEraseV(int v) {
            yMap.put(v, yMap.getOrDefault(v, 0) - 1);
            if (yMap.get(v) == 0) yMap.remove(v);
            ysz--;
        }
    }
}

（全文完）