結果
| 問題 |
No.2065 Sum of Min
|
| コンテスト | |
| ユーザー |
 遭難者
|
| 提出日時 | 2023-01-12 23:11:33 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 823 ms / 2,000 ms |
| コード長 | 24,986 bytes |
| コンパイル時間 | 3,088 ms |
| コンパイル使用メモリ | 88,464 KB |
| 実行使用メモリ | 95,936 KB |
| 最終ジャッジ日時 | 2024-12-23 15:37:20 |
| 合計ジャッジ時間 | 18,832 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
import java.io.*;
class Main {
private static final void solve() throws IOException {
final int n = ni(), q_ = ni();
var wm = new WaveletMatrix(ni(n));
for (int qq = 0; qq < q_; qq++) {
final int l = ni() - 1, r = ni(), x = ni();
ou.println(wm.count_upper(l, r, x) * (long)x + wm.sum_lower(l, r, x));
}
}
public static void main(String[] args) throws IOException {
solve();
ou.flush();
}
private static final int ni() throws IOException {
return sc.nextInt();
}
private static final int[] ni(int n) throws IOException {
return sc.nextIntArray(n);
}
private static final long nl() throws IOException {
return sc.nextLong();
}
private static final long[] nl(int n) throws IOException {
return sc.nextLongArray(n);
}
private static final String ns() throws IOException {
return sc.next();
}
private static final double nd() throws IOException {
return sc.nextDouble();
}
private static final ContestInputStream sc = new ContestInputStream();
private static final ContestOutputStream ou = new ContestOutputStream();
}
final class WaveletMatrix {
private final int[][] data;
private final long[][] ruia;
private final int n, bit;
WaveletMatrix(int[] d, int bit) {
n = d.length;
this.bit = bit;
int[] dat = d.clone();
data = new int[bit][n];
ruia = new long[bit][n];
int[] que = new int[n];
for (int k = bit - 1; k >= 0; k--) {
int que1 = 0, que2 = n;
for (int i = 0; i < n; i++) {
data[k][i] = dat[i] >> k & 1;
if (data[k][i] == 1)
que[--que2] = dat[i];
else
que[que1++] = dat[i];
}
for (int i = 0; i < que1; i++)
ruia[k][i] = dat[i] = que[i];
for (int i = n - 1, j = que1; i >= que1; i--, j++)
ruia[k][j] = dat[j] = que[i];
for (int i = 1; i < n; i++) {
data[k][i] += data[k][i - 1];
ruia[k][i] += ruia[k][i - 1];
}
}
}
WaveletMatrix(int[] dat) {
this(dat, 31);
}
private final int get(int bi, int id) {
if (id == 0)
return data[bi][0];
return data[bi][id] - data[bi][id - 1];
}
final int access(int idx) {
int ans = 0;
for (int k = bit - 1; k >= 0; k--) {
if (get(k, idx) == 1) {
ans |= 1 << k;
idx = zer(k, n) + one(k, idx);
} else
idx -= data[k][idx];
}
return ans;
}
private final int one(int bi, int l) {
if (l == 0)
return 0;
return data[bi][l - 1];
}
private final int zer(int bi, int l) {
return l - one(bi, l);
}
private final int sum(int bi, int l, int r) {
return one(bi, r) - one(bi, l);
}
private final long one_rui(int bi, int l) {
if (l == 0)
return 0L;
return ruia[bi][l - 1];
}
private final long sum_rui(int bi, int l, int r) {
return one_rui(bi, r) - one_rui(bi, l);
}
public final int kth_smallest(int l, int r, int kth) {
int ans = 0;
for (int k = bit - 1; k >= 0; k--) {
final int s = r - l - sum(k, l, r);
if (kth < s) {
l = zer(k, l);
r = l + s;
} else {
kth -= s;
ans |= 1 << k;
final int ran = r - l - s;
l = zer(k, n) + one(k, l);
r = l + ran;
}
}
return ans;
}
public final int kth_largest(int l, int r, int kth) {
return kth_smallest(l, r, r - l - kth);
}
public final long sum_lower(int l, int r, int lower) {
long ans = 0L;
for (int k = bit - 1; k >= 0; k--) {
final int s = r - l - sum(k, l, r);
final int ran = r - l - s;
if (((lower >> k) & 1) == 1) {
final int ll = zer(k, l);
final int rr = ll + s;
ans += sum_rui(k, ll, rr);
l = zer(k, n) + one(k, l);
r = l + ran;
} else {
l = zer(k, l);
r = l + s;
}
}
return ans;
}
public final int count_lower(int l, int r, int lower) {
int ans = 0;
for (int k = bit - 1; k >= 0; k--) {
final int s = r - l - sum(k, l, r);
if (((lower >> k) & 1) == 1) {
ans += s;
final int ran = r - l - s;
l = zer(k, n) + one(k, l);
r = l + ran;
} else {
l = zer(k, l);
r = l + s;
}
}
return ans;
}
public final int count_upper(int l, int r, int upper) {
return r - l - count_lower(l, r, upper);
}
public final int count(int l, int r, int x) {
return count_lower(l, r, x + 1) - count_lower(l, r, x);
}
public final int next_value(int l, int r, int upper) {
final int cnt = count_lower(l, r, upper + 1);
return kth_smallest(l, r, cnt);
}
public final int perv_value(int l, int r, int lower) {
final int cnt = count_upper(l, r, lower - 1);
return kth_largest(l, r, cnt);
}
}
final class ContestInputStream extends FilterInputStream {
protected final byte[] buf;
protected int pos = 0;
protected int lim = 0;
private final char[] cbuf;
public ContestInputStream() {
super(System.in);
this.buf = new byte[1 << 13];
this.cbuf = new char[1 << 20];
}
boolean hasRemaining() throws IOException {
if (pos < lim)
return true;
lim = in.read(buf);
pos = 0;
return lim > 0;
}
final int remaining() throws IOException {
if (pos >= lim) {
lim = in.read(buf);
pos = 0;
}
return lim - pos;
}
@Override
public final int available() throws IOException {
if (pos < lim)
return lim - pos + in.available();
return in.available();
}
@Override
public final long skip(long n) throws IOException {
if (pos < lim) {
int rem = lim - pos;
if (n < rem) {
pos += n;
return n;
}
pos = lim;
return rem;
}
return in.skip(n);
}
@Override
public final int read() throws IOException {
if (hasRemaining())
return buf[pos++];
return -1;
}
@Override
public final int read(byte[] b, int off, int len) throws IOException {
if (pos < lim) {
int rem = Math.min(lim - pos, len);
for (int i = 0; i < rem; i++)
b[off + i] = buf[pos + i];
pos += rem;
return rem;
}
return in.read(b, off, len);
}
public final char[] readToken() throws IOException {
int cpos = 0;
int rem;
byte b;
l: while ((rem = remaining()) > 0) {
for (int i = 0; i < rem; i++) {
b = buf[pos + i];
if (b <= 0x20) {
pos += i + 1;
cpos += i;
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
break l;
}
cbuf[cpos + i] = (char) b;
}
pos += rem;
cpos += rem;
}
char[] arr = new char[cpos];
for (int i = 0; i < cpos; i++)
arr[i] = cbuf[i];
return arr;
}
public final int readToken(char[] cbuf, int off) throws IOException {
int cpos = off;
int rem;
byte b;
l: while ((rem = remaining()) > 0) {
for (int i = 0; i < rem; i++) {
b = buf[pos + i];
if (b <= 0x20) {
pos += i + 1;
cpos += i;
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
break l;
}
cbuf[cpos + i] = (char) b;
}
pos += rem;
cpos += rem;
}
return cpos - off;
}
public final int readToken(char[] cbuf) throws IOException {
return readToken(cbuf, 0);
}
public final String next() throws IOException {
int cpos = 0;
int rem;
byte b;
l: while ((rem = remaining()) > 0) {
for (int i = 0; i < rem; i++) {
b = buf[pos + i];
if (b <= 0x20) {
pos += i + 1;
cpos += i;
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
break l;
}
cbuf[cpos + i] = (char) b;
}
pos += rem;
cpos += rem;
}
return String.valueOf(cbuf, 0, cpos);
}
public final char[] nextCharArray() throws IOException {
return readToken();
}
public final int nextInt() throws IOException {
if (!hasRemaining())
return 0;
int value = 0;
byte b = buf[pos++];
if (b == 0x2d) {
while (hasRemaining() && (b = buf[pos++]) > 0x20)
value = value * 10 - b + 0x30;
} else {
do {
value = value * 10 + b - 0x30;
} while (hasRemaining() && (b = buf[pos++]) > 0x20);
}
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
return value;
}
public final long nextLong() throws IOException {
if (!hasRemaining())
return 0L;
long value = 0L;
byte b = buf[pos++];
if (b == 0x2d) {
while (hasRemaining() && (b = buf[pos++]) > 0x20)
value = value * 10 - b + 0x30;
} else {
do {
value = value * 10 + b - 0x30;
} while (hasRemaining() && (b = buf[pos++]) > 0x20);
}
if (b == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
return value;
}
public final char nextChar() throws IOException {
if (!hasRemaining())
throw new EOFException();
final char c = (char) buf[pos++];
if (hasRemaining() && buf[pos++] == 0x0d && hasRemaining() && buf[pos] == 0x0a)
pos++;
return c;
}
public final float nextFloat() throws IOException {
return Float.parseFloat(next());
}
public final double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public final boolean[] nextBooleanArray(char ok) throws IOException {
char[] s = readToken();
int n = s.length;
boolean[] t = new boolean[n];
for (int i = 0; i < n; i++)
t[i] = s[i] == ok;
return t;
}
public final boolean[][] nextBooleanMatrix(int h, int w, char ok) throws IOException {
boolean[][] s = new boolean[h][];
for (int i = 0; i < h; i++) {
char[] t = readToken();
int n = t.length;
s[i] = new boolean[n];
for (int j = 0; j < n; j++)
s[i][j] = t[j] == ok;
}
return s;
}
public final String[] nextStringArray(int len) throws IOException {
String[] arr = new String[len];
for (int i = 0; i < len; i++)
arr[i] = next();
return arr;
}
public final int[] nextIntArray(int len) throws IOException {
int[] arr = new int[len];
for (int i = 0; i < len; i++)
arr[i] = nextInt();
return arr;
}
public final int[] nextIntArray(int len, java.util.function.IntUnaryOperator map) throws IOException {
int[] arr = new int[len];
for (int i = 0; i < len; i++)
arr[i] = map.applyAsInt(nextInt());
return arr;
}
public final long[] nextLongArray(int len, java.util.function.LongUnaryOperator map) throws IOException {
long[] arr = new long[len];
for (int i = 0; i < len; i++)
arr[i] = map.applyAsLong(nextLong());
return arr;
}
public final int[][] nextIntMatrix(int h, int w) throws IOException {
int[][] arr = new int[h][w];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
arr[i][j] = nextInt();
return arr;
}
public final int[][] nextIntMatrix(int h, int w, java.util.function.IntUnaryOperator map) throws IOException {
int[][] arr = new int[h][w];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
arr[i][j] = map.applyAsInt(nextInt());
return arr;
}
public final long[] nextLongArray(int len) throws IOException {
long[] arr = new long[len];
for (int i = 0; i < len; i++)
arr[i] = nextLong();
return arr;
}
public final long[][] nextLongMatrix(int h, int w) throws IOException {
long[][] arr = new long[h][w];
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
arr[i][j] = nextLong();
return arr;
}
public final float[] nextFloatArray(int len) throws IOException {
float[] arr = new float[len];
for (int i = 0; i < len; i++)
arr[i] = nextFloat();
return arr;
}
public final double[] nextDoubleArray(int len) throws IOException {
double[] arr = new double[len];
for (int i = 0; i < len; i++)
arr[i] = nextDouble();
return arr;
}
public final char[][] nextCharMatrix(int h, int w) throws IOException {
char[][] arr = new char[h][];
for (int i = 0; i < h; i++)
arr[i] = readToken();
return arr;
}
public final void nextThrow() throws IOException {
next();
return;
}
public final void nextThrow(int n) throws IOException {
for (int i = 0; i < n; i++)
nextThrow();
return;
}
}
final class ContestOutputStream extends FilterOutputStream implements Appendable {
protected final byte[] buf;
protected int pos = 0;
public ContestOutputStream() {
super(System.out);
this.buf = new byte[1 << 13];
}
@Override
public void flush() throws IOException {
out.write(buf, 0, pos);
pos = 0;
out.flush();
}
void put(byte b) throws IOException {
if (pos >= buf.length)
flush();
buf[pos++] = b;
}
int remaining() throws IOException {
if (pos >= buf.length)
flush();
return buf.length - pos;
}
@Override
public void write(int b) throws IOException {
put((byte) b);
}
@Override
public void write(byte[] b, int off, int len) throws IOException {
int o = off;
int l = len;
while (l > 0) {
int rem = Math.min(remaining(), l);
for (int i = 0; i < rem; i++)
buf[pos + i] = b[o + i];
pos += rem;
o += rem;
l -= rem;
}
}
@Override
public ContestOutputStream append(char c) throws IOException {
put((byte) c);
return this;
}
@Override
public ContestOutputStream append(CharSequence csq, int start, int end) throws IOException {
int off = start;
int len = end - start;
while (len > 0) {
int rem = Math.min(remaining(), len);
for (int i = 0; i < rem; i++)
buf[pos + i] = (byte) csq.charAt(off + i);
pos += rem;
off += rem;
len -= rem;
}
return this;
}
@Override
public ContestOutputStream append(CharSequence csq) throws IOException {
return append(csq, 0, csq.length());
}
public ContestOutputStream append(char[] arr, int off, int len) throws IOException {
int o = off;
int l = len;
while (l > 0) {
int rem = Math.min(remaining(), l);
for (int i = 0; i < rem; i++)
buf[pos + i] = (byte) arr[o + i];
pos += rem;
o += rem;
l -= rem;
}
return this;
}
public ContestOutputStream print(char[] arr) throws IOException {
return append(arr, 0, arr.length).newLine();
}
public ContestOutputStream print(boolean value) throws IOException {
if (value)
return append("o");
return append("x");
}
public ContestOutputStream println(boolean value) throws IOException {
if (value)
return append("o\n");
return append("x\n");
}
public ContestOutputStream print(boolean[][] value) throws IOException {
final int n = value.length, m = value[0].length;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
print(value[i][j]);
newLine();
}
return this;
}
public ContestOutputStream print(int value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(int value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(long value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(long value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(float value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(float value) throws IOException {
return append(String.valueOf(value)).newLine();
}
private ContestOutputStream dtos(double x, int n) throws IOException {
if (x < 0) {
append('-');
x = -x;
}
x += Math.pow(10, -n) / 2;
long longx = (long) x;
print(longx);
append('.');
x -= longx;
for (int i = 0; i < n; i++) {
x *= 10;
int intx = (int) x;
print(intx);
x -= intx;
}
return this;
}
public ContestOutputStream print(double value) throws IOException {
return dtos(value, 20);
}
public ContestOutputStream println(double value) throws IOException {
return dtos(value, 20).newLine();
}
public ContestOutputStream print(char value) throws IOException {
return append(value);
}
public ContestOutputStream println(char value) throws IOException {
return append(value).newLine();
}
public ContestOutputStream print(String value) throws IOException {
return append(value);
}
public ContestOutputStream println(String value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream print(Object value) throws IOException {
return append(String.valueOf(value));
}
public ContestOutputStream println(Object value) throws IOException {
return append(String.valueOf(value)).newLine();
}
public ContestOutputStream printYN(boolean yes) throws IOException {
if (yes)
return println("Yes");
return println("No");
}
public ContestOutputStream printAB(boolean yes) throws IOException {
if (yes)
return println("Alice");
return println("Bob");
}
public ContestOutputStream print(CharSequence[] arr) throws IOException {
if (arr.length > 0) {
append(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').append(arr[i]);
}
return this;
}
public ContestOutputStream print(int[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
newLine();
return this;
}
public ContestOutputStream print(int[] arr, int length) throws IOException {
if (length > 0)
print(arr[0]);
for (int i = 1; i < length; i++)
append('\u0020').print(arr[i]);
newLine();
return this;
}
public ContestOutputStream println(int[] arr) throws IOException {
for (int i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream println(int[] arr, int length) throws IOException {
for (int i = 0; i < length; i++)
println(arr[i]);
return this;
}
public ContestOutputStream print(boolean[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
newLine();
return this;
}
public ContestOutputStream print(long[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
newLine();
return this;
}
public ContestOutputStream print(long[] arr, int length) throws IOException {
if (length > 0)
print(arr[0]);
for (int i = 1; i < length; i++)
append('\u0020').print(arr[i]);
newLine();
return this;
}
public ContestOutputStream println(long[] arr, int length) throws IOException {
for (int i = 0; i < length; i++)
println(arr[i]);
return this;
}
public ContestOutputStream println(long[] arr) throws IOException {
for (long i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream print(float[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
return this;
}
public ContestOutputStream println(float[] arr) throws IOException {
for (float i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream print(double[] arr) throws IOException {
if (arr.length > 0) {
print(arr[0]);
for (int i = 1; i < arr.length; i++)
append('\u0020').print(arr[i]);
}
return newLine();
}
public ContestOutputStream println(double[] arr) throws IOException {
for (double i : arr)
print(i).newLine();
return this;
}
public ContestOutputStream print(java.util.ArrayList<?> arr) throws IOException {
if (!arr.isEmpty()) {
final int n = arr.size();
print(arr.get(0));
for (int i = 1; i < n; i++)
print(" ").print(arr.get(i));
}
return newLine();
}
public ContestOutputStream println(java.util.ArrayList<?> arr) throws IOException {
final int n = arr.size();
for (int i = 0; i < n; i++)
println(arr.get(i));
return this;
}
public ContestOutputStream newLine() throws IOException {
return append(System.lineSeparator());
}
public ContestOutputStream endl() throws IOException {
newLine().flush();
return this;
}
public ContestOutputStream print(int[][] arr) throws IOException {
for (int[] i : arr)
print(i);
return this;
}
public ContestOutputStream print(long[][] arr) throws IOException {
for (long[] i : arr)
print(i);
return this;
}
public ContestOutputStream print(char[][] arr) throws IOException {
for (char[] i : arr)
print(i);
return this;
}
public ContestOutputStream print(Object[][] arr) throws IOException {
for (Object[] i : arr)
print(i);
return this;
}
public ContestOutputStream println() throws IOException {
return newLine();
}
public ContestOutputStream print(Object... arr) throws IOException {
for (Object i : arr)
print(i);
return this;
}
public ContestOutputStream println(Object... arr) throws IOException {
for (Object i : arr)
print(i);
return newLine();
}
}