1526.三元环

时间限制:1s 内存限制:256MB

小马给出长度为 n 的正整数序列 f,g,现以如下方式生成 n 个点的有向图:

for i from 1 to n:
  for j from i+1 to n:
    if f[i] < f[j] and g[i] < g[j]:
      add edge from i to j
    else:
      add edge from j to i

试求出图中三元环的个数。

输入格式(从终端/标准输入读取)

第一行包含 $1$ 个正整数 $n(1 ≤ n ≤ 200000, 1 ≤ f_i,g_i ≤ n)$。

第二行包含 $n$ 个正整数,第 $i$ 个正整数表示 $f_i$。

第三行包含 $n$ 个正整数,第 $i$ 个正整数表示 $g_i$。

输出格式(输出至终端/标准输出)

输出共 $1$ 行,输出 $1$ 个整数,表示最终答案。

输入样例

复制
9
3 7 2 1 4 5 9 8 7
2 4 1 5 7 9 2 4 1
 \n
 · · · · · · · · \n
 · · · · · · · · \n

输出样例

复制
4
 \n

说明

(1,8,4),(1,8,7),(7,4,3),(8,4,3)

来源: 2024“钉耙编程”中国大学生算法设计超级联赛(1)

提交题解

Please login first.

© 2025 FAQs