某山寨

z4zr的待调教小窝

hrbustoj 1830第一个重复出现的数 (区间最值)

hrbustoj 1830第一个重复出现的数 (区间最值)

http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1830

额 学弟发问 然后骚扰五姑娘 然后诞生此物。。。

思路
首先生成一个数组 用来存储每个数的前面距离它最近的相同数字的下标
然后利用线段数 查询区间最大值
最大值就是 答案的下标 然后输出
然后需要注意 下标如果在查询的范围外 就返回-1 (第一次我错在这里)

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<map>
using namespace std;

struct node{
    int max,l,r;
}tree[500010*3];
int n,q,num[500010],ans[500010],a,b;

int creat(int root,int left,int right){
    tree[root].l=left;
    tree[root].r=right;
    if(left==right)return tree[root].max=ans[left];
    int a,b,middle=(left+right)/2;
    a=creat(2*root,left,middle);
    b=creat(2*root+1,middle+1,right);
    return tree[root].max=max(a,b);
}

int query(int root,int left,int right){
    if(tree[root].l>right||tree[root].r<left)return -1;
    if(left<=tree[root].l&&tree[root].r<=right){
        if(tree[root].max>=a)return tree[root].max;
        else return -1;
    }
    int aa,bb;
    aa=query(2*root,left,right);
    bb=query(2*root+1,left,right);
//printf("query root:%3d  left:%3d  right:%3d  a:%3d  b:%3d\n",root,left,right,a,b);
    return max(aa,bb);
}
int main(){
    int i,j,k;
    map<int,int> mp;
    map<int,int>::iterator it;
    while(scanf("%d",&n)!=EOF){
        mp.clear();
        memset(ans,-1,sizeof(ans));
        for(i=1;i<=n;i++){
            scanf("%d",&num[i]);
            it=mp.find(num[i]);
            if(it==mp.end()){
                mp[num[i]]=i;
            }else {
                ans[i]=(*it).second;
                (*it).second=i;
            }
        }
        creat(1,1,n);
        scanf("%d",&q);
        while(q--){
            scanf("%d%d",&a,&b);
            int qq=query(1,a,b);
            if(qq<=0)puts("jiong");
            else printf("%d\n",num[qq]);
        }
        puts("");
    }
    return 0;
}

Warning: file_get_contents(http://api.hitokoto.us/rand): failed to open stream: Connection timed out in /data/htdocs/z4zr.host.smartgslb.com/usr/themes/Wcat/functions.php on line 87

文章二维码