UVALive 5881 Unique Encryption Keys【线段树】

快来打我* 2022-08-10 13:45 16阅读 0赞

题目：[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;
    }

直接处理代码：

[UVALive 5881 Unique Encryption Keys]: https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3892