codeforces227B--Effective Approach--想法题

B. Effective Approach

time limit per test 2 seconds  memory limit per test 256 megabytes input standard input output standard output

Once at a team training Vasya, Petya and Sasha got a problem on implementing linear search in an array.

According to the boys, linear search works as follows. The array elements in a pre-selected order are in turn compared with the number that you need to find. Once you find the array element that is equal to the required one, the search ends. The efficiency of the algorithm is the number of performed comparisons. The fewer comparisons the linear search has made, the more effective it is.

Vasya believes that a linear search would work better if it sequentially iterates through the elements, starting with the 1-st one (in this problem we consider the elements of the array indexed from 1 to n) and ending with the n-th one. And Petya says that Vasya is wrong: the search will need less comparisons if it sequentially iterates the elements starting from the n-th and ending with the 1-st one. Sasha argues that the two approaches are equivalent.

To finally begin the task, the teammates decided to settle the debate and compare the two approaches on an example. For this, they took an array that is a permutation of integers from 1 to n, and generated m queries of the form: find element with value bi in the array. They want to calculate for both approaches how many comparisons in total the linear search will need to respond to all queries. If the first search needs fewer comparisons, then the winner of the dispute is Vasya. If the second one does, then the winner is Petya. If both approaches make the same number of comparisons, then Sasha's got the upper hand.

But the problem is, linear search is too slow. That's why the boys aren't going to find out who is right before the end of the training, unless you come in here. Help them to determine who will win the dispute.

Input

The first line contains integer n (1 ≤ n ≤ 105) — the number of elements in the array. The second line contains n distinct space-separated integers a1, a2, ..., an (1 ≤ ai ≤ n) — the elements of array.

The third line contains integer m (1 ≤ m ≤ 105) — the number of queries. The last line contains m space-separated integers b1, b2, ..., bm (1 ≤ bi ≤ n) — the search queries. Note that the queries can repeat.

Output

Print two integers, showing how many comparisons Vasya's approach needs and how many comparisons Petya's approach needs. Separate the numbers by spaces.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specifier.

Sample test(s) Input

2
1 2
1
1
      

Output

1 2
      

Input

2
2 1
1
1
      

Output

2 1
      

Input

3
3 1 2
3
1 2 3
      

Output

6 6
      

Note

In the first sample Vasya's approach will make one comparison (it starts with the 1-st element and immediately finds the required number), and Petya's approach makes two comparisons (first he compares with the 2-nd array element, doesn't find the search item and compares with the 1-st element).

In the second sample, on the contrary, Vasya's approach will need two comparisons (first with 1-st element, and then with the 2-nd), and Petya's approach will find the required value in one comparison (the first comparison with the 2-nd element).

题意很好理解，

就是小明和小红两个人分别从前往后，或者从后往前找元素。

记录小明找到元素的次数，小红找到元素的次数。

直接暴力O（n^2）肯定T了，

所以先通过sort排序，再通过upper_bound和lower_bound函数找到元素所在的下标。

以下是代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxnum=1e5+100;
int n;
struct hehe
{
    int value;
    int id;
}a[maxnum];

bool mycompare(hehe a,hehe b)
{
    if(a.id!=b.id)
        return a.value<b.value;
    else
        return a.id<b.id;
}

//写二分永远想清楚，谁是主体！当然是被查找的那个数列啊！！！！！！！！
int my_lowerbound(int l,int r,int x)//寻找第一个大于等于x的元素的下标
{
    while(l<r)
    {
        int mid=l+((r-l)>>1);//因为(r+l)>>1可能会爆int
        if(a[mid].value<x) l=mid+1; //如果mid对应的值比x小，那么为了查找第一个大于或等于x的元素的下标，肯定从mid+1开始查询
        else r=mid; //如果mid对应的值大于或等于x，那么为了查找第一个大于或等于x的元素的下标，肯定从mid开始往前找
    }
    if(a[l].value>=x)
        return l;
    else
        return -1;
}

int my_upperbound(int l,int r,int x) //寻找第一个大于x的元素的下标
{
    while(l<r)
    {
        int mid=l+((r-l)>>1);//因为(r+l)>>1可能会爆int
        if(a[mid].value<=x) l=mid+1; //如果mid对应的值小于等于x，那么为了查找第一个大于x的元素的下标，肯定从mid+1开始查询
        else r=mid; //如果mid对应的值大于x，那么为了查找第一个大于x的元素的下标，肯定从mid+开始往前找
    }
    if(a[l].value>x)
        return l;
    else
        return -1;
}

int main()
{
    long long ans1=0,ans2=0;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i].value);
        a[i].id=i;
    }
    sort(a+1,a+1+n,mycompare);
    int m;
    cin>>m;
    int temp;
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&temp);
        int index=my_lowerbound(1,n,temp);
        int t1=a[index].id;
        index=my_upperbound(1,n,temp);
        if(index!=-1)
        {
            int t2=a[index-1].id;
            ans1+=t1;
            ans2+=n-t2+1;
        }
        else
        {
            int t2=a[n].id;
            ans1+=t1;
            ans2+=n-t2+1;
        }
    }
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}
           

后来发现想复杂了，

因为数的范围小，

可以直接用一个数组存下从前往后找到的第一个position，

从后往前找到的第一个position。

最后输出结果。

#include <iostream>
#include <cstdio>
using namespace std;
const int maxnum=1e5+100;
int a[maxnum];
int first[maxnum];
int last[maxnum];

int main()
{
    long long ans1=0,ans2=0;
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=n;++i)
    {
        if(first[a[i]]==0)
        {
            first[a[i]]=i;
        }
    }
    for(int i=n;i>=1;--i)
    {
        if(last[a[i]]==0)
        {
            last[a[i]]=i;
        }
    }
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int temp;
        scanf("%d",&temp);
        ans1+=first[temp];
        ans2+=n-last[temp]+1;
    }
    cout<<ans1<<" "<<ans2<<endl;
    return 0;
}