题解 | #金条切割#

c题java直接用莫队都能过

import java.io.*;
import java.util.Arrays;

import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException  {
//         Scanner sc = new Scanner(System.in);
        Reader sc = new Reader();
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        int[][] q = new int[m][];
        for (int i = 0; i < m; ++i) {
            q[i] = new int[]{sc.nextInt() - 1, sc.nextInt() - 1, i};
        }
        int block = 1;
        while((block + 1L) * (block + 1) <= n) ++block;
        final int bb = block;
        Arrays.sort(q, (x, y) -> {
            int b1 = x[0] / bb, b2 = y[0] / bb;
            if (b1 != b2) return b1 - b2;
            return b1 % 2 == 0? x[1] - y[1]: y[1] - x[1];
        });
        int l = 0, r = -1;
        long res = 0;
        int[] map = new int[1000_001];
        long[] ans = new long[m];
        for (int[] qq: q) {
            while (l < qq[0]) {
                int x = a[l++];
                map[x]--;
                if (map[x] == k) res += x;
                else if (map[x] == k - 1) res -= x;
            }
            while(l > qq[0]) {
                int x = a[--l];
                map[x]++;
                if (map[x] == k) res += x;
                else if (map[x] == k + 1) res -= x;
            }
            while (r < qq[1]) {
                int x = a[++r];
                map[x]++;
                if (map[x] == k) res += x;
                else if (map[x] == k + 1) res -= x;
            }
            while(r > qq[1]) {
                int x = a[r--];
                map[x]--;
                if (map[x] == k) res += x;
                else if (map[x] == k - 1) res -= x;
            }
            ans[qq[2]] = res;
//             System.out.println(l + " " + r + " " + Arrays.toString(Arrays.copyOf(map, 10)));
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; ++i) {
            sb.append(ans[i]).append('\n');
        }
        System.out.print(sb);
    }
}
class Reader {
    InputStream in = System.in;
    byte[] buffer = new byte[1024];
    int cur = 0, len = 0;
    private byte nextByte() {
        if (cur >= len) {
            try {
                cur = 0;
                this.len = this.in.read(buffer);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        if (len == 0) {
            return -1;
        }
        return buffer[cur++];
    }
    int nextInt() {
        int res = 0;
        int c = 0;
        while ((c = nextByte()) != -1 && !Character.isDigit((char)c))
            ;
        do {
            res = res * 10 + c - '0';
        } while ((c = nextByte()) != -1 && Character.isDigit(c));
        return res;
    }
}