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;
}
}