Measuring Problem Difficulty

Time Limit:5000MS  Memory Limit:65536K
Total Submit:14 Accepted:3

Description

If you are the lucky one to advance to the ACM-ICPC World Finals, one of the situations you will face is the world finals competition itself. Wait, isn’t that the main reason to go there? In the beginning of each ACM-ICPC competition, there are two separate goals each team tries to accomplish:
1. among the given set of problems, find the easiest one,
2. solve that problem as fast as possible.
To evaluate the performance of all teams in detail, we want to test your abilities for each of these two goals separately. This problem deals with the former goal (finding the easiest problem), the latter one (solving it) is analyzed in another problem (easy).
The main trouble with comparing problem difficulty is that the opinions of different people may vary. To satisfy everyone, we need to find some consensus. Let’s start with determining all problems on which the opinions agree.
Your team is given a set of ICPC problems. Each team member sorts all of the problems in the order of their expected difficulty. Then we want to find all pairs of problems such that their relative order is the same according to all given orderings.

Input

The input contains several tasks. Each task starts by one line containing single integer N, 2 ≤ N ≤ 150 000, the number of problems to consider.
After that, there are three blocks, each of them describing opinion of one team member. (ICPC teams have three members, right?) Every block specifies an arbitrary permutation of N numbers 1 . . .N representing the problems. You should know from the school that the word “permutation” means each of the numbers will appear exactly once in each block.
Each block starts on a new line. For presentation reasons, the numbers inside a block may be split among any number of lines. If there are more than one number per line, they will be separated by at least one space. Empty lines may occur before and after blocks.
The last task is followed by a line containing zero.

Output

For each task, print one line containing a single integer number: the number of all pairs of problems, whose mutual order is the same in all three permutations.
Please note that the result may be as high as N·(N−1)/2 and may therefore exceed 2^32.

Sample Input


4
1 2 3 4
2 3 4 1
4 1 2 3

6
3 6 1 2 4 5
3 6 1 4 2 5
3 6 1 2 4 5

0
Sample Output


1
14

你们都很厉害，题目全是英文的，四六级都过啦？

原文提供了一个故事背景，我就不翻译了。直接描述问题。
输入包含多组测试数据，每组数据的第一个数值N表示接下来的三行每行中的数值数量。每行是一个包含1－N的数值序列。当N为0时标志着数据输入的结束。
问题要的结束是在1－N中仍意两个数值在三行中相对位置（即谁前谁后）相同的这样的数值对有多少。
以第一组示例数据为例，其中只有2、3这个数值对在三行中出现的相对位置相同。所以结果为1。
第二组示例数据中（1，2）（1，3）（1，4）（1，5）（1，6）（2，3）（2，5）（2，6）（3，4）（3，5）（3，6）（4，5）（4，6）（5，6）这14个数值对出现的相对位置相同。所以结果为14。
需要指出一点，我上面为了描述方便说每行包含一个序列，而实际题中指出每组数据可以被放在任意行内，或者说可以被分割成任意多行。所以在数据读入时不要按行读取。
下面是我写的关于这一问题的代码，你可以参考一下。不过这个算法的时间复杂度是N^2，当N=150000时，大概要做90多亿次运算。题目要求的时间是5秒，恐怕要超时的，你可以试着提交一下。如果要提交，请选择GCC或ANSI C。C++可能不支持long long类型。提交后告诉我一下结果。

#include<stdio.h>
#define MAX_N    150000
int s1[MAX_N + 1];
int s2[MAX_N + 1];
int s3[MAX_N + 1];
int sn;
long long cal()
{
    int i, j, a, b, c;
    long long count = 0;
    for(i = 1; i < sn; i++)
    for(j = i + 1; j <= sn; j++)
    {
        a = (s1[i] < s1[j]) ? 1 : 0;
        b = (s2[i] < s2[j]) ? 1 : 0;
        c = (s3[i] < s3[j]) ? 1 : 0;
        if(a == b && b == c) count++;
    }
    return count;
}
int main()
{
    int i, a;
    while(scanf("%d", &sn), sn)
    {
        for(i = 1; i <= sn; scanf("%d", &a), s1[a] = i++);
        for(i = 1; i <= sn; scanf("%d", &a), s2[a] = i++);
        for(i = 1; i <= sn; scanf("%d", &a), s3[a] = i++);
        printf("%lld\n", cal());
    }
    return 0;
}

 

这个是超时的，方法我也是这个，但是。。。我想应该得用其他的方法

英语水平真好

如果对于以下输入，3楼的算法结果是3，可实际上却是0额
1 4 2 3
2 4 1 3
3 4 2 1

你怎么得到3这个结果的？为什么它在我的机器上测试你的数据结果是0呢？
上面的代码算法没有错。
凭直觉我在考虑问题与每行的逆序数的关系，或者构建一个动态规划的模型。

你的循环是：对于每一对（i,j）（i<sn&&j>i）,测试它们在3个数列中是否均为顺序对或者逆序对，如果是则count+1,
输入：
1 4 2 3
2 4 1 3
3 4 2 1
中存在3对i,j=（1,2）(顺序对),(2,3)（逆序对）,(2,4)（逆序对）满足你的a==b&&b==c的判断条件，因此count+3，是么？还是我理解错了？

你们的英语真好！我都看不懂

如果你能找个编译器实际编译执行一下那段代码你就不会那么说了。
看来还是有必要解释一下那段代码。
请注意一下s数组是怎么使用的。楼上仁兄就是想当然的认为数组存的是一行序列，数组的元素是数值，数组的下标是它出现的位置。
而事实上，我是倒过来用的。数组的下标表示的是数值，数组的元素是它出现的位置。
关于这一点请注意看看我是怎么将数据存储到数组里的。这么做的原因在于，之后的处理比原来要方便的多。