結果
| 問題 |
No.404 部分門松列
|
| コンテスト | |
| ユーザー |
 37zigen
|
| 提出日時 | 2016-08-07 21:18:39 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 1,673 ms / 2,000 ms |
| コード長 | 6,091 bytes |
| コンパイル時間 | 4,444 ms |
| コンパイル使用メモリ | 81,512 KB |
| 実行使用メモリ | 69,184 KB |
| 最終ジャッジ日時 | 2024-11-07 09:16:39 |
| 合計ジャッジ時間 | 35,456 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 31 |
ソースコード
package No400番台;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
public class Q404 {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
void solver() {
int N = ni();
int[] a = na(N);
int[] b = Arrays.copyOf(a, a.length);
Arrays.sort(b);
b = shrink(b);
int n = b.length;
BinaryIndexedTree[] B = new BinaryIndexedTree[2];
B[0] = new BinaryIndexedTree(n);
B[1] = new BinaryIndexedTree(n);
for (int i = 0; i < N; i++) {
a[i] = upper_bound(b, a[i]) + 1;
}
long[] r = new long[n + 1];
long[] l = new long[n + 1];
for (int i = 0; i < N; i++) {
r[a[i]]++;
B[1].add(a[i], 1);
}
r[a[0]]--;
long same = 0;
long[] calc = new long[n + 1];
for (int i = 0; i < N; i++) {
long ans = 0;
B[1].add(a[i], -1);
ans += B[0].sum(a[i] - 1) * B[1].sum(a[i] - 1);
ans += (i - B[0].sum(a[i])) * (N - i - 1 - B[1].sum(a[i]));
ans -= same - l[a[i]] * r[a[i]];
if (i + 1 < N) {
r[a[i + 1]]--;
same += r[a[i]];
same -= l[a[i + 1]];
l[a[i]]++;
}
B[0].add(a[i], 1);
calc[a[i]] += ans;
}
long[] sum = new long[n + 2];
for (int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + calc[i];
}
sum[n + 1] = sum[n];
int q = ni();
long[] L = new long[q];
long[] H = new long[q];
// tr(sum);
// tr(b);
for (int i = 0; i < q; i++) {
L[i] = ni();
H[i] = ni();
int low = lower_bound(b, L[i]) + 1;
int high = upper_bound(b, H[i]) + 1;
if (L[i] > b[n - 1]) {
low = n + 1;
}
if (H[i] >= b[n - 1]) {
high = n + 1;
}
if(H[i]<b[0]){
high=0;
low=0;
}
System.out.println((sum[high] - sum[low]));
// System.out.println(L[i]+" "+H[i]+" "+lower_bound(b, L[i]) + " " +
// upper_bound(b, H[i]));
}
}
int upper_bound(int[] b, long h) {
int min = 0;
int max = b.length;
for (int i = 0; Math.pow(2, i) < b.length + 2; i++) {
int mid = (max + min) / 2;
if (b[mid] > h) {
max = mid;
} else {
min = mid;
}
if (max == min + 1 && b[min] == h)
return min;
}
return min;
}
int lower_bound(int[] b, long l) {
int min = -1;
int max = b.length - 1;
for (int i = 0; Math.pow(2, i) < b.length + 2; i++) {
int mid = (max + min) / 2;
if (b[mid] >= l) {
max = mid;
} else {
min = mid;
}
}
return min;
}
static int[] shrink(int[] arr) {
ArrayList<Integer> d = new ArrayList<>();
d.add(arr[0]);
for (int i = 0; i < arr.length; i++) {
if (d.get(d.size() - 1) == arr[i])
continue;
else {
d.add(arr[i]);
}
}
int[] ret = new int[d.size()];
for (int i = 0; i < ret.length; i++) {
ret[i] = d.get(i);
}
return ret;
}
class BinaryIndexedTree {
int n;
long[] d;
BinaryIndexedTree(int n) {
this.n = n;
d = new long[n + 2];
}
void add(int i, long diff) {
while (i <= n) {
d[i] += diff;
i += (i & (-i));
}
}
// sum[1,i]
long sum(int i) {
long s = 0;
while (i > 0) {
s += d[i];
i -= (i & (-i));
}
return s;
}
// sum[r,l]
long sum(int r, int l) {
return sum(l) - sum(r - 1);
}
}
public static void main(String[] args) throws Exception {
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
new Q404().solver();
out.flush();
}
static long nl() {
try {
long num = 0;
boolean minus = false;
while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
;
if (num == '-') {
num = 0;
minus = true;
} else {
num -= '0';
}
while (true) {
int b = is.read();
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}
static char nc() {
try {
int b = skip();
if (b == -1)
return 0;
return (char) b;
} catch (IOException e) {
}
return 0;
}
static double nd() {
try {
return Double.parseDouble(ns());
} catch (Exception e) {
}
return 0;
}
static String ns() {
try {
int b = skip();
StringBuilder sb = new StringBuilder();
if (b == -1)
return "";
sb.append((char) b);
while (true) {
b = is.read();
if (b == -1)
return sb.toString();
if (b <= ' ')
return sb.toString();
sb.append((char) b);
}
} catch (IOException e) {
}
return "";
}
public static char[] ns(int n) {
char[] buf = new char[n];
try {
int b = skip(), p = 0;
if (b == -1)
return null;
buf[p++] = (char) b;
while (p < n) {
b = is.read();
if (b == -1 || b <= ' ')
break;
buf[p++] = (char) b;
}
return Arrays.copyOf(buf, p);
} catch (IOException e) {
}
return null;
}
private int[] na(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = ni();
return a;
}
private long[] nal(int n) {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nl();
return a;
}
public static byte[] nse(int n) {
byte[] buf = new byte[n];
try {
int b = skip();
if (b == -1)
return null;
is.read(buf);
return buf;
} catch (IOException e) {
}
return null;
}
static int skip() throws IOException {
int b;
while ((b = is.read()) != -1 && !(b >= 33 && b <= 126))
;
return b;
}
static boolean eof() {
try {
is.mark(1000);
int b = skip();
is.reset();
return b == -1;
} catch (IOException e) {
return true;
}
}
static int ni() {
try {
int num = 0;
boolean minus = false;
while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-'))
;
if (num == '-') {
num = 0;
minus = true;
} else {
num -= '0';
}
while (true) {
int b = is.read();
if (b >= '0' && b <= '9') {
num = num * 10 + (b - '0');
} else {
return minus ? -num : num;
}
}
} catch (IOException e) {
}
return -1;
}
static void tr(Object... o) {
System.out.println(Arrays.deepToString(o));
}
}