team2012-E1-mysol-0007

从 Trac 迁移的文章

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

原文章内容如下：

{{{
/* 解题报告 //

给出一行上的 n 个数，再给出 m 个查询
每次询问 [Li, Ri] 区间内最靠右的第二次出现的数字是谁

做法就是对查询的区间，按照右端点排序，从小到大
依次处理每个区间，同时有一个指针 x 表示当前处理了前多少个数字
当一个区间包含了未处理的数字（即 x 小于区间右端点）
则对第 x + 1 个数字进行处理，方法如下：

记第 x + 1 个数字为 val，在 map 中查找它上次出现的位置
如果没有出现，则上次出现的位置记为 0，我的代码利用了 map 的一个特性，
如果用下标的方式读取一个不存在的元素，则 map 会将它初始化成 0

总之，得到了 val 上次出现的位置后，去更新 far = max(far, map[val])
表示前 x + 1 个数字中，最靠右的第二次出现的数字在哪里
然后更新 val 上次出现的位置，即 map[val] = ++x

解决完那些未处理的数字后，再处理当前区间
如果 far >= 区间的左端点，则说明当前区间包含了重复的数字
并且 far 是最靠右的第二次出现的数字的位置

最后，输出的时候要注意一下，输出的是第二次出现的数字的值，不是位置

// By 猛犸也钻地 @ 2012.07.19 */
}}}

{{{
#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;

int a[500000];
int o[500000];
pair<pair<int,int>,int> u[50000];

int main(){
    int n,m;
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++) scanf("%d",a+i);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d%d",&u[i].first.second,&u[i].first.first);
            u[i].second=i;
        }
        sort(u,u+m);
        map<int,int> s;
        int far=0;
        for(int i=0,x=0;i<m;i++){
            while(u[i].first.first>x){
                int& pos=s[a[x]];
                far=max(far,pos);
                pos=++x;
            }
            if(far>=u[i].first.second) o[u[i].second]=far;
        }
        for(int i=0;i<m;i++)
            if(o[i]) printf("%d\n",a[o[i]-1]); else puts("OK");
        puts("");
    }
}
}}}

/* 解题报告 //
给出一行上的 n 个数，再给出 m 个查询
每次询问 [Li, Ri] 区间内最靠右的第二次出现的数字是谁
做法就是对查询的区间，按照右端点排序，从小到大
依次处理每个区间，同时有一个指针 x 表示当前处理了前多少个数字
当一个区间包含了未处理的数字（即 x 小于区间右端点）
则对第 x + 1 个数字进行处理，方法如下：
记第 x + 1 个数字为 val，在 map 中查找它上次出现的位置
如果没有出现，则上次出现的位置记为 0，我的代码利用了 map 的一个特性，
如果用下标的方式读取一个不存在的元素，则 map 会将它初始化成 0
总之，得到了 val 上次出现的位置后，去更新 far = max(far, map[val])
表示前 x + 1 个数字中，最靠右的第二次出现的数字在哪里
然后更新 val 上次出现的位置，即 map[val] = ++x
解决完那些未处理的数字后，再处理当前区间
如果 far >= 区间的左端点，则说明当前区间包含了重复的数字
并且 far 是最靠右的第二次出现的数字的位置
最后，输出的时候要注意一下，输出的是第二次出现的数字的值，不是位置
// By 猛犸也钻地 @ 2012.07.19 */

#include <cstdio>
#include <map>
#include <algorithm>
using namespace std;
int a[500000];
int o[500000];
pair<pair<int,int>,int> u[50000];
int main(){
    int n,m;
    while(scanf("%d",&n)==1){
        for(int i=0;i<n;i++) scanf("%d",a+i);
        scanf("%d",&m);
        for(int i=0;i<m;i++){
            scanf("%d%d",&u[i].first.second,&u[i].first.first);
            u[i].second=i;
        }
        sort(u,u+m);
        map<int,int> s;
        int far=0;
        for(int i=0,x=0;i<m;i++){
            while(u[i].first.first>x){
                int& pos=s[a[x]];
                far=max(far,pos);
                pos=++x;
            }
            if(far>=u[i].first.second) o[u[i].second]=far;
        }
        for(int i=0;i<m;i++)
            if(o[i]) printf("%d\n",a[o[i]-1]); else puts("OK");
        puts("");
    }
}