首页 > 代码库 > BZOJ 3524 [Poi2014]Couriers（二分+蒙特卡罗）
BZOJ 3524 [Poi2014]Couriers（二分+蒙特卡罗）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=3524
【题目大意】
给一个长度为n的序列a。1≤a[i]≤n。
m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。
如果存在，输出这个数，否则输出0。
【题解】
我们可以在[l,r]中随机一个位置检验这个位置上数是不是答案，
检测方法可以在数组中保存每个数在序列中的不同位置，二分即可
选中答案的概率为1/2，我们做k次蒙特卡罗，正确率就为1-(1/2)^k，
复杂度为O(kmlogn)。
主席树做法见 LINK
【代码】
#include <cstdio>#include <algorithm>#include <vector>using namespace std;const int N=500010;vector<int> pos[N];int a[N],l,r,n,m;int main(){ while(~scanf("%d%d",&n,&m)){ for(int i=1;i<=n;i++)pos[i].clear(); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); pos[a[i]].push_back(i); } while(m--){ scanf("%d%d",&l,&r); int len=r-l+1,find=0; for(int k=1;k<=20;k++){ int u=a[l+rand()%len]; int st=lower_bound(pos[u].begin(),pos[u].end(),l)-pos[u].begin(); int en=upper_bound(pos[u].begin(),pos[u].end(),r)-pos[u].begin(); if((en-st)*2>len){find=u;break;} }if(find)printf("%d\n",find); else puts("0"); } }return 0;}BZOJ 3524 [Poi2014]Couriers（二分+蒙特卡罗）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。