混合饮料

时间限制: 1500 ms 内存限制: 131072 kb
总通过人数: 0 总提交人数: 0

题目描述

方奶奶 有 $n$ 杯饮料,每杯饮料有三个属性,分别是美观值、美味值和营养值。

记 $a_i,b_i, c_i$ 分别为第 $i$ 杯饮料的美观值、美味值和营养值,则 $1\le a_i,b_i,c_i \le n$ 且不存在两杯不同的饮料它们的 $a_i$ 相同,或 $b_i$ 相同,或 $c_i$ 相同。

方奶奶 想用其中一杯或一杯以上的饮料制作出一杯新的混合饮料,这杯新的饮料的美观值、美味值和营养值,分别等于成为其成分的饮料的美观值、美味值和营养值中的最大值。

即如果组成这杯新的混合饮料的指标集为 $S\subseteq \{1,\dots,n\} (S \neq \emptyset)$ ,则新的混合饮料的美观值、美味值和营养值分别为 $\max\limits_{i\in S}a_i$,$\max\limits_{i\in S}b_i$ 和$\max\limits_{i\in S}c_i$ 。

现在 方奶奶 想要知道,通过这种方式可以得到多少种不同的新饮料(两种饮料被认为相同当且仅当其美观值、美味值和营养值都相同)。

在探讨可能性的时候不认为任何一杯饮料被实际消耗掉了。

输入

第一个数为数据组数 $T$ 。

接下来 $T$ 块,每块描述一组测试数据。

每组数据第一行为一个正整数 $n$ ,保证 $1\le n \le 10^5$ 。

接下来 $3$ 行,每行一个 $1$ 到 $n$ 的排列,分别为 $\{a_n\}$,$\{b_n\}$,$\{c_n\}$ 。

保证 $T\le15$ ,$\sum n\le5\times10^5$ 。

输出

对于每组数据,输出一行,格式为 Case #number: result,其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据,而 $\mathrm{result}$ 为该组数据的答案,也即 方奶奶 可以得到的不同的饮料数。

输入样例

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

输出样例

Case #1: 37

相关推荐