AcWing 4709. Java BIT/fenwick tree 树状数组 8611ms
原题链接
困难
import java.util.*;
import java.io.*;
class Main {
static PrintWriter pw;
void solve(int n, int[] a) {
Fenwick fen = new Fenwick(n + 3);
int[] u = removeDuplicatedSorted(a);
long[] L = new long[n], R = new long[n];
for (int i = 0; i < n; i++) a[i] = lower_bound(u, a[i]) + 1;
for (int i = 0; i < n; i++) {
L[i] = i - fen.query(a[i]);
fen.update(a[i], 1);
}
fen.reset();
for (int i = n - 1; i >= 0; i--) {
R[i] = fen.query(a[i] - 1);
fen.update(a[i], 1);
}
long res = 0;
for (int i = 0; i < n; i++) res += L[i] * R[i];
pr(res);
}
class Fenwick {
int n;
int[] a;
Fenwick(int n) {
this.n = n;
a = new int[n];
}
long query(int i) {
long sum = 0;
for (i++; i > 0; i = parent(i)) sum += a[i];
return sum;
}
void update(int i, int v) {
for (i++; i < n; i = next(i)) a[i] += v;
}
int parent(int x) {
return x - lowestOneBit(x);
}
int next(int x) {
return x + lowestOneBit(x);
}
int lowestOneBit(int x) {
return x & -x;
}
void reset() {
Arrays.fill(a, 0);
}
}
int lower_bound(int[] a, int x) {
int low = 0, high = a.length;
while (low < high) {
int mid = low + high >>> 1;
if (a[mid] < x) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
int[] removeDuplicatedSorted(int[] a) {
TreeSet<Integer> ts = new TreeSet<>();
for (int x : a) ts.add(x);
int[] res = new int[ts.size()];
int p = 0;
for (int x : ts) res[p++] = x;
return res;
}
private void run() {
// read_write_file(); // comment this before submission
FastScanner fs = new FastScanner();
int n = fs.nextInt();
int[] a = fs.readArray(n);
solve(n, a);
}
private final String INPUT = "input.txt";
private final String OUTPUT = "output.txt";
void read_write_file() {
FileInputStream instream = null;
PrintStream outstream = null;
try {
instream = new FileInputStream(INPUT);
outstream = new PrintStream(new FileOutputStream(OUTPUT));
System.setIn(instream);
System.setOut(outstream);
} catch (Exception e) {
}
}
public static void main(String[] args) {
pw = new PrintWriter(System.out);
new Main().run();
pw.close();
}
<T> void pr(T t) {
pw.println(t);
}
class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
}
void tr(Object... o) {
pw.println(Arrays.deepToString(o));
}
}