三元环
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/524288K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小马给出长度为 $n$ 的正整数序列 $f,g$，现以如下方式生成 $n$ 个点的有向图：
<pre><code class="html">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</code></pre>
试求出图中三元环的个数。
<pre><code class="html">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</code></pre>
试求出图中三元环的个数。
Input
第一行包含 $1$ 个正整数 $n$（$1 \leq n \leq 200000,1 \leq f_i,g_i \leq n$）。
第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $f_i$。
第三行包含 $n$ 个正整数，第 $i$ 个正整数表示 $g_i$。
第二行包含 $n$ 个正整数，第 $i$ 个正整数表示 $f_i$。
第三行包含 $n$ 个正整数，第 $i$ 个正整数表示 $g_i$。
Output
输出共 $1$ 行，输出 $1$ 个整数，表示最终答案。
Sample Input
9 3 7 2 1 4 5 9 8 7 2 4 1 5 7 9 2 4 1
Sample Output
4
Hint
$(1,8,4),(1,8,7),(7,4,3),(8,4,3)$
Source
2024“钉耙编程”中国大学生算法设计超级联赛（1）