#P11197. [COTS 2021] 赛狗游戏 Tiket

    ID: 10570 Type: RemoteJudge 1000ms 500MiB Tried: 0 Accepted: 0 Difficulty: 6 Uploaded By: Tags>2021O2优化CEOI(中欧)COCI(克罗地亚)

[COTS 2021] 赛狗游戏 Tiket

题目背景

Rebirth.

译自 Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) D2T3。1s,0.5G\texttt{1s,0.5G}

题目描述

圆,焰,光在观看赛狗游戏。

三个人都猜测了狗冲过终点的顺序,即 PiP_i 表示第 ii 只冲过终点的狗的编号。我们假设没有平局。

NN 条狗,因此 PiP_i 构成一个 1N1\sim N 的排列。不妨记第 jj 个人猜测的排列为 P(j)P(j)

此外,最终狗冲过终点的顺序构成排列 TT

计算满足以下条件的数对 (a,b)(a,b) 的数量:

  • TT 中,aabb 前面;
  • 1j3\forall 1\le j\le 3,要么 aa 在所有的 P(j)P(j) 中都在 bb 前面,要么 bb 在所有的 P(j)P(j) 中都在 aa 前面。

输入格式

第一行,一个正整数 NN

第二行,NN 个正整数描述 TT

接下来三行,第 jjNN 个正整数,描述 P(j)P(j)

输出格式

输出一行一个整数,即答案。

3
2 3 1
1 2 3
1 2 3
2 3 1
1
4
3 1 2 4
4 3 2 1
1 2 3 4
1 2 4 3
0
5
1 3 2 4 5
4 3 5 2 1
4 3 1 2 5
1 2 4 3 5
3

提示

样例解释

样例 11 解释:只有 (2,3)(2,3) 满足条件。

数据范围

对于 100%100\% 的数据,保证:

  • 2N5×1052\le N\le 5\times 10^5
  • 1j3\forall 1\le j\le 3P(j)P(j) 构成一个 1N1\sim N 的排列。
  • TT 构成一个 1N1\sim N 的排列。
子任务编号 NN\le 特殊性质 得分
1 1 5000 5\, 000 7 7
2 2 5×105 5\times 10^5 8 8
3 3 5×104 5\times 10^4 29 29
4 4 5×105 5\times 10^5 56 56

特殊性质:P(1)=P(2)P(1)=P(2)。也就是说圆和焰猜的排列是一样的。