树状数组
一阵子忙完了!奖励自己一个新的数据结构BIT
感觉实现的思想是很奇妙的,lowbit
函数
下面是一个模板题,但是对我来说也有点难度
思路就是边更新边获取答案,然后能相同的原理就行
当然线段树完全可以做,不过显然树状数组更加简单
import java.util.*;
public class Main {
static Scanner in = new Scanner(System.in);
static int n;
static long[] a;
static BIT b1, b2;
public static void main(String[] args) {
read();
//前缀MAX
long[] pp = gp();
//前缀MIN
long[] ll = gl();
System.out.printf("%d %d", V(pp), U(ll));
}
public static long V (long[] pp) {
long[] tmp = new long[n + 1];
long res = 0;
b2 = new BIT(tmp, n);
for(int i = 1; i <= n; ++i) {
if(a[i] > 1)
res += b2.query(1, a[i] - 1);
b2.add(a[i], pp[i]);
}
return res;
}
public static long U (long[] ll) {
long[] tmp = new long[n + 1];
long res = 0;
b2 = new BIT(tmp, n);
for(int i = 1; i <= n; ++i) {
if(a[i] < n)
res += b2.query(a[i] + 1, n);
b2.add(a[i], ll[i]);
}
return res;
}
public static long[] gp() {
long[] tmp = new long[n + 1];
long[] pp = new long[n + 1];
b1 = new BIT(tmp, n);
for(int i = 1; i <= n; ++i) {
if(a[i] < n)
pp[i] = b1.query(a[i] + 1, n);
b1.add(a[i], 1);
}
return pp;
}
public static long[] gl() {
long[] tmp = new long[n + 1];
long[] ll = new long[n + 1];
b1 = new BIT(tmp, n);
for(int i = 1; i <= n; ++i) {
if(a[i] > 1)
ll[i] = b1.query(1, a[i] - 1);
b1.add(a[i], 1);
}
return ll;
}
public static void read() {
n = in.nextInt();
a = new long[n + 1];
for(int i = 1; i <= n; ++i)
a[i] = in.nextInt();
}
}
class BIT {
long[] a, c;
int n;
public BIT(long[] a, int n) {
this.a = a; this.n = n;
c = new long[n + 1];
}
public void init() {
for(int i = 1; i <= n; ++i) {
c[i] = a[i];
for(int k = i - 1; k > i - lowbit(i); k -= lowbit(k))
c[i] += c[k];
}
}
public void add(long x, long k) {
for(int i = (int)x; i <= n; i += lowbit(i))
c[i] += k;
}
public long query(long l, long r) {
return q(r) - q(l - 1);
}
public long q(long x) {
long res = 0;
for(int i = (int)x; i > 0; i -= lowbit(i))
res += c[i];
return res;
}
public int lowbit(int a) {
return a & (-a);
}
}