珂朵莉的数列
树状数组
题目描述：给你一串数字序列，求所有区间的逆序对。
解题分析：对于每一个逆序对，计算它的贡献，也就是所有包含这个逆序对的区间。用树状数组来维护，不过得先离散化。数据太大，longlong无法表示，上的java
代码如下：
import java.math.BigInteger;
import java.net.SocketPermission;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static final int maxn = 1000000 + 10;
static long[] num = new long[maxn], b = new long[maxn],arr = new long[maxn];
static int n;
static int lowbit(int i) {
return i & -i;
}
static long sum(int i) {
long ans = 0;
while(i != 0) {
ans += arr[i];
i -= lowbit(i);
}
return ans;
}
static void add(int i,long v) {
while(i < maxn) {
arr[i] += v;
i += lowbit(i);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
for(int i = 1; i <= n; i++) {
num[i] = sc.nextLong();
b[i] = num[i];
arr[i] = 0;
}
Arrays.sort(b,1,n + 1);
for(int i = 1; i <= n; i++) {
num[i] = Arrays.binarySearch(b, 1 ,n + 1,num[i]);
}
BigInteger ans = new BigInteger("0");
for(int i = 1; i <= n; i++) {
ans = ans .add(new BigInteger(String.valueOf((n - i + 1) * (sum(maxn-1) - sum((int)num[i])))));
add((int)num[i],(long)i);
}
System.out.println(ans);
}
}
华为成长空间 479人发布
