UVALive 5881 Unique Encryption Keys【线段树】

题目：UVALive 5881 Unique Encryption Keys

分类：线段树，想法题

题意：给出n个数，然后有q次查询，每次查询 l---r 区间内有没有重复的数，有的话输出任意的，没有的话输出ok

分析：上去一看觉得这个题目可以不用线段树做，因为它是静态的，想了一个方法后来发现时不对的，后来规规矩矩用线段树了。

这个题目不能直接用线段树，否则的话无法维护他们的值，区间内出现超过两次的值没有办法维护，你可以维护出来线段树中出现过的区间，但是当询问的是两个区间的时候又没有办法处理了，这个题在这儿花了不少时间。

其实可以这样处理一下，对于每一个值处理出后面离他最近的点的位置，如果没有的话设为无穷大，那么只要用线段树维护一个区间最小值。

然后查询出区间的最小值和右区间比较，如果不大于右区间的话说明一定出现过。

其实还有更简单的方法，不用线段树维护最小值，上面处理出后面离他最近的点的位置，如果没有的话在线段树中设置为无穷大，我们设置成后面理他最近的点的值就好，这样就是一个单调不减的序列，查询的时候左值相当于区间最小值，那么就很水了。

线段树代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <utility>
#define Del(a,b) memset(a,b,sizeof(a))
const int N = 10010000;
using namespace std;
struct Node
{
    int l,r;
    int num;
};
Node tree[N];
int a[N],b[N];
map<int,int> v;
void build(int l,int r,int o)
{
    tree[o].l=l,tree[o].r=r;
    if(l==r)
    {
        tree[o].num=b[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(l,mid,o+o);
    build(mid+1,r,o+o+1);
    tree[o].num=min(tree[o+o].num,tree[o+o+1].num);
}
int query(int l,int r,int o)
{
    if(tree[o].l==l && tree[o].r==r)
    {
        return tree[o].num;
    }
    int mid=(tree[o].l+tree[o].r)>>1;
    if(r<=mid)
        return query(l,r,o+o);
    else if(l>mid)
        return query(l,r,o+o+1);
    else
    {
        return min(query(l,mid,o*2),query(mid+1,r,o*2+1));
    }
}
int main()
{
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        if(n==0 && q==0)
            break;
        memset(b,0x3f3f3f3f,sizeof(b));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=n;i>=1;i--)
        {
            if(v[a[i]])
                b[i]=v[a[i]];
            v[a[i]]=i;
        }
        build(1,n,1);
        while(q--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int ans=query(x,y,1);
            //printf("%d\n",ans);
            if(ans>y)
                printf("OK\n");
            else
                printf("%d\n",a[ans]);
        }
        printf("\n");
        v.clear();
    }
    return 0;
}
           

直接处理代码：

#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <utility>
#define Del(a,b) memset(a,b,sizeof(a))
const int N = 10010000;
using namespace std;
int a[N],b[N];
map<int,int> v;
int main()
{
    int n,q;
    while(~scanf("%d%d",&n,&q))
    {
        if(n==0 && q==0)
            break;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        b[n+1]=n+1;
        for(int i=n;i>=1;i--)
        {
            b[i]=b[i+1];
            if(v[a[i]])
                b[i]=min(v[a[i]],b[i]);
            v[a[i]]=i;
        }
        while(q--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(b[x]>y)
                printf("OK\n");
            else
                printf("%d\n",a[b[x]]);
        }
        printf("\n");
        v.clear();
    }
    return 0;
}