2012-A3-0007

从 Trac 迁移的文章

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

原文章内容如下：

题意：给出一串长度为N的序列，给出M组询问，每组询问一段[l,r]区间内的重复情况，如有输出最后一组重复的数字，否者输出OK.

首先把序列里的元素离散化，对于序列里每个元素找到在它之前的最后一个与之重复的，记录下标。

根据题意，重复位置的取最靠后的，所以上述的下标都只要存个前缀最大值d[i]，

对于区间[l,r],如果 d[y]>=x,就有重复，否者没有。

离散化要O(n log n),查询单次O(1)
{{{
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned num;

num a[1<<19],b[1<<19],c[1<<19],d[1<<19];
int main(){
    for(num n,m,q;scanf("%u",&n)==1;putchar('\n')){
        for(num i=0;i<n;++i)scanf("%u",a+i);
        memcpy(b,a,n<<2);
        sort(b,b+n);m=unique(b,b+n)-b;
        memset(c,0,n<<2);
        for(num i=0,j;i<n;c[j]=++i)
            d[i+1]=max(d[i],c[j=upper_bound(b,b+m,a[i])-b]);
        scanf("%u",&q);
        for(num x,y;q--;){
            scanf("%u%u",&x,&y);
            if(d[y]>=x)printf("%u\n",a[d[y]-1]);
            else puts("OK");
        }
    }
    return 0;
}
}}}

题意：给出一串长度为N的序列，给出M组询问，每组询问一段[l,r]区间内的重复情况，如有输出最后一组重复的数字，否者输出OK.

首先把序列里的元素离散化，对于序列里每个元素找到在它之前的最后一个与之重复的，记录下标。

根据题意，重复位置的取最靠后的，所以上述的下标都只要存个前缀最大值d[i]，

对于区间[l,r],如果 d[y]>=x,就有重复，否者没有。

离散化要O(n log n),查询单次O(1)

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned num;
num a[1<<19],b[1<<19],c[1<<19],d[1<<19];
int main(){
    for(num n,m,q;scanf("%u",&n)==1;putchar('\n')){
        for(num i=0;i<n;++i)scanf("%u",a+i);
        memcpy(b,a,n<<2);
        sort(b,b+n);m=unique(b,b+n)-b;
        memset(c,0,n<<2);
        for(num i=0,j;i<n;c[j]=++i)
            d[i+1]=max(d[i],c[j=upper_bound(b,b+m,a[i])-b]);
        scanf("%u",&q);
        for(num x,y;q--;){
            scanf("%u%u",&x,&y);
            if(d[y]>=x)printf("%u\n",a[d[y]-1]);
            else puts("OK");
        }
    }
    return 0;
}