第一个重复出现的数 HRBUST - 1830

本文主要是介绍第一个重复出现的数 HRBUST - 1830，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

开个数组记录每个数右边第一个相同数的位置 线段树维护这个数组的区间最小值 这样可以把问题转换为判定性问题 即右树是否存在符合条件的某个位置 有则返回 无则查左树

但是这里的query写起来稍微有点不太一样 因为我们不是从根节点开始查 要查询的区间会被划分成很多不太规则的小区间 但是遍历这些小区间的先后顺序是一定的 比如对于1-8 我要查2-7 区间划分如下

1-8

1-4 5-8

1-2 [3-4] [5-6] 7-8

1 [2] 3 4 5 6 [7] 8

如果query先递归左树 那遍历顺序为[2] [3-4] [5-6] [7] 这里要先递归右树 遍历顺序为[7] [5-6] [3-4] [2]

进入[7]后 如果最小值小于等于查询区间右边界 说明当前区间内有符合条件的数 从当前区间继续递归肯定能找到答案且找到答案后立即返回 若大于查询区间右边界 说明[7]内没有要找的数 返回 等到递归至[5-6]时再做判断 总体复杂度还是logn

当然可以logn*logn无脑二分 做法就不说了

#include <bits/stdc++.h>
using namespace std;
const int N=0x3f3f3f3f;map <int,int> mp;
int ary[500010],rgt[500010],minn[2000010];
int n,q;void pushup(int cur)
{minn[cur]=min(minn[2*cur],minn[2*cur+1]);
}void build(int l,int r,int cur)
{int m;if(l==r){minn[cur]=rgt[l];return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);
}int query(int pl,int pr,int l,int r,int cur)
{int res,m;if(pl<=l&&r<=pr){if(minn[cur]<=pr){if(l==r) return l;else{res=-1,m=(l+r)/2;if(pr>m) res=query(pl,pr,m+1,r,2*cur+1);if(pl<=m&&res==-1) res=query(pl,pr,l,m,2*cur);return res;}}else return -1;}else{res=-1,m=(l+r)/2;if(pr>m) res=query(pl,pr,m+1,r,2*cur+1);if(pl<=m&&res==-1) res=query(pl,pr,l,m,2*cur);}return res;
}int main()
{int i,l,r,res;while(scanf("%d",&n)!=EOF){for(i=1;i<=n;i++) scanf("%d",&ary[i]);mp.clear();for(i=n;i>=1;i--){if(mp[ary[i]]==0) rgt[i]=N;else rgt[i]=mp[ary[i]];mp[ary[i]]=i;}build(1,n,1);scanf("%d",&q);while(q--){scanf("%d%d",&l,&r);res=query(l,r,1,n,1);if(res==-1) printf("jiong\n");else printf("%d\n",ary[res]);}printf("\n");}return 0;
}

 

这篇关于第一个重复出现的数 HRBUST - 1830的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---