浙江网站制作公司网站维护费一年多少钱
压制二元组的总价值
对于每一个 a i a_i ai, 看它能压制它前面的多少个元素, 那么它对总价值的贡献就是:
在a数组中:
- a i a_i ai压制了x个数, 贡献为: x ∗ i x*i x∗i
- 被 a i a_i ai所压制的所有数在 a a a中的下标和为 y y y, 贡献为 − y -y −y
树状数组来求:
- 为了快速求出 a i a_i ai压制了几个数, 记录 a i a_i ai前面的所有数在 b b b中的下标 m a p ( a [ i ] ) map(a[i]) map(a[i]),值 t r b [ m a p ( a [ i ] ) ] = 1 trb[map(a[i])]=1 trb[map(a[i])]=1表示它出现过,
这样每次只需通过 s u m ( m a p [ a [ i ] ] ) sum(map[a[i]]) sum(map[a[i]])即可得出它前面已经出现了多少个数.
- 记录 a i a_i ai前面的所有数在b中的下标 m a p ( a [ i ] ) map(a[i]) map(a[i]), 值 t r a [ m a p ( a [ i ] ) ] tra[map(a[i])] tra[map(a[i])]为它在 a a a中的下标 i i i, 每次 s u m sum 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();}}