压制二元组的总价值

压制二元组的总价值

对于每一个$a_i$, 看它能压制它前面的多少个元素, 那么它对总价值的贡献就是:

在a数组中:

1. $a_i$压制了x个数, 贡献为:$x\ast i$
2. 被$a_i$所压制的所有数在$a$中的下标和为$y$, 贡献为$-y$

树状数组来求:

1. 为了快速求出$a_i$压制了几个数, 记录$a_i$前面的所有数在$b$中的下标$map(a[i])$,值$trb[map(a[i])]=1$表示它出现过,

​ 这样每次只需通过$sum(map[a[i]])$即可得出它前面已经出现了多少个数.

2. 记录$a_i$前面的所有数在b中的下标$map(a[i])$, 值$tra[map(a[i])]$为它在$a$中的下标$i$, 每次$sum$即可得出它所压制的所有数的下标和.

import java.io.*;
import java.util.*;public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer stmInput = new StreamTokenizer(br);static int N = 200010;static long tra[] = new long[N], trb[] = new long[N];static int a[] = new int[N], b[] = new int[N];static HashMap<Integer, Integer> map = new HashMap<>();static int n;public static int readInt() throws IOException {stmInput.nextToken();return (int) stmInput.nval;}public static int lowbit(int x){return x & -x;}public static void add(int x, int c, long tr[]){for (int i = x; i <= n; i += lowbit(i)) {tr[i] += c;}}public static long sum(int x, long tr[]){long res = 0;for (int i = x; i >= 1; i -= lowbit(i)) {res += tr[i];}return res;}public static void solve() throws IOException{n = readInt();for (int i = 1; i <= n; i++) {a[i] = readInt();}for (int i = 1; i <= n; i++) {b[i] = readInt();map.put(b[i], i);}long ans = 0;for (int i = 1; i <= n; i++) {// 1.ai压制了多少个数ans += i * sum(map.get(a[i]), tra);add(map.get(a[i]), 1, tra);// 2.被ai压制的所有数在a中的下标和ans -= sum(map.get(a[i]), trb);add(map.get(a[i]), i, trb);}pw.println(ans);}public static void main(String[] args) throws IOException {int T = 1;while(T-- != 0){solve();}pw.flush();pw.close();br.close();}}