team2012-F3-sol-0007

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
题意：给定一个整数序列，有一些区间询问，对于每一个询问要回答在这个区间里从右到左第一个重复出现的数字。
解法：从左至右处理这个序列，用map或hash维护每一个不同数字的上一次出现位置
并且用F[i]表示i之前最右的重复位置，则F[i] = max{ a[i]的上一次出现位置, F[i-1] }
对于每一个询问(l,r)，比较F[r]和l即可
}}}
{{{
#include <iostream>
#include <map>

using namespace std;

int n, m, f[500004], a[500004];
map<int, int> near;

int main()
{
    while(cin>>n)
    {
        f[0] = 0;
        near.clear();
        for(int i=1;i<=n;i++)
        {
            int& x = a[i];
            cin>>x;
            f[i] = f[i-1];
            if(near.count(x) == 0)
                near[x] = i;
            else
            {
                if(near[x] > f[i])
                    f[i] = near[x];
                near[x] = i;
            }
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            int l, r;
            cin>>l>>r;
            if(f[r] >= l)
                cout<<a[f[r]]<<endl;
            else
                cout<<"OK"<<endl;
        }
        cout<<endl;
    }
    return 0;
}
}}}

题意：给定一个整数序列，有一些区间询问，对于每一个询问要回答在这个区间里从右到左第一个重复出现的数字。
解法：从左至右处理这个序列，用map或hash维护每一个不同数字的上一次出现位置
并且用F[i]表示i之前最右的重复位置，则F[i] = max{ a[i]的上一次出现位置, F[i-1] }
对于每一个询问(l,r)，比较F[r]和l即可

#include <iostream>
#include <map>
using namespace std;
int n, m, f[500004], a[500004];
map<int, int> near;
int main()
{
    while(cin>>n)
    {
        f[0] = 0;
        near.clear();
        for(int i=1;i<=n;i++)
        {
            int& x = a[i];
            cin>>x;
            f[i] = f[i-1];
            if(near.count(x) == 0)
                near[x] = i;
            else
            {
                if(near[x] > f[i])
                    f[i] = near[x];
                near[x] = i;
            }
        }
        cin>>m;
        for(int i=1;i<=m;i++)
        {
            int l, r;
            cin>>l>>r;
            if(f[r] >= l)
                cout<<a[f[r]]<<endl;
            else
                cout<<"OK"<<endl;
        }
        cout<<endl;
    }
    return 0;
}