← 返回题目列表

AtCoder · past22_m

M. 大序列的反转数

中文机器翻译题面 查看原题

问题陈述

给你两个序列 A=(A_1,\ldots,A_N) 和 B=(B_1,\ldots,B_N) 长度 N.

定义一个序列 C 作为以空序列开始并附加得到的序列 A_i 副本 B_i,结果长度为 \sum_{i=1}^N A_i.

求倒数 C.

什么是反转数? 序列的反转数 C = (C_1, C_2, \dots, C_M) 定义为索引对的数量 (i, j) 这样 1 \leq i < j \leq M 和 C_i > C_j.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^3
  • 1 \leq B_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

输出

打印答案。


示例输入 1

3
4 1 2
10 30 20

示例输出 1

2

序列 C is (10,10,10,10,30,20,20),其反转数为 2.


示例输入 2

4
1000 1000 1000 1000
1 1 1 1

示例输出 2

0

的反转数 C is 0.


示例输入 3

13
3 1 4 1 5 9 2 6 5 3 5 8 9
2 7 1 8 2 8 1 7 2 7 4 5 9

示例输出 3

499