首页 > 代码库 > [Poi2014]Couriers
[Poi2014]Couriers
bzoj3524: [Poi2014]Couriers
Description
给一个长度为n的序列a。1≤a[i]≤n。
m组询问,每次询问一个区间[l,r],是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在,输出这个数,否则输出0。
Input
第一行两个数n,m。
第二行n个数,a[i]。
接下来m行,每行两个数l,r,表示询问[l,r]这个区间。
Output
m行,每行对应一个答案。
Sample Input
1 1 3 2 3 4 3
1 3
1 4
3 7
1 7
6 6
Sample Output
0
3
0
4
HINT
【数据范围】
n,m≤500000
解法一、
还记得区间第k小数怎么查询吗?http://www.cnblogs.com/TheRoadToTheGold/p/6259781.html
如果左子节点新增的数的个数<=k,递归左子节点,反之递归右子节点,k变为k-左子节点新增的数的个数
这里是查询区间出现次数>k的数
与区间第k小一样,都应用了数出现的次数
所以只需要在查询时,如果左子节点新增数的个数>k,递归左子节点;如果右子节点新增数的个数>k,递归右子节点;再否则,那就没有满足条件的数
答案就是递归到的叶子节点
#include<cstdio> #include<algorithm> #define N 500001 using namespace std; int n,m,tot,a[N],hash[N]; int root[N],sum[N*20],lc[N*20],rc[N*20],cnt; int ans; void discrete() { sort(a+1,a+n+1); tot=unique(a+1,a+n+1)-(a+1); for(int i=1;i<=n;i++) hash[i]=lower_bound(a+1,a+tot+1,hash[i])-a; } inline void insert(int pre,int & now,int l,int r,int k) { sum[now=++cnt]=sum[pre]+1; if(l==r) return; int mid=l+r>>1; if(k<=mid) { rc[now]=rc[pre]; insert(lc[pre],lc[now],l,mid,k); } else { lc[now]=lc[pre]; insert(rc[pre],rc[now],mid+1,r,k); } } inline void query(int x,int y,int l,int r,int k) { if(l==r) {ans=a[l];return;} int mid=l+r>>1; if(sum[lc[y]]-sum[lc[x]]>k) query(lc[x],lc[y],l,mid,k); else if(sum[rc[y]]-sum[rc[x]]>k) query(rc[x],rc[y],mid+1,r,k); else {ans=0;return ;} } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),hash[i]=a[i]; discrete(); for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,tot,hash[i]); int s,t,k; for(int i=1;i<=m;i++) { scanf("%d%d",&s,&t); k=t-s+1>>1; query(root[s-1],root[t],1,tot,k); printf("%d\n",ans); } }
解法二、
记得中庸之道那道题吗?http://www.cnblogs.com/TheRoadToTheGold/p/6291149.html
一个区间的中位数是第(r-l)/2+1小,所以如果查找是否有数出现了(r-l)/2+1次,如果存在这个数,那么排序后中位数的位置一定是这个数,所以直接查中位数的出现次数就好了
这里是查找是否有数出现了大于(r-l+1)/2次,即至少出现了(r-l+1)/2+1次
由于整除,所以
如果区间有奇数个点,(r-l+1)/2+1=(r-l)/2+1=区间中位数的位置
如果区间有偶数个点,(r-l+1)/2是把区间从中间劈开,左边一部分的最后一个位置,那么+1后就成为了右边一部分的第一个位置,所以如果有数出现了(r-l+1)/2+1次,右边一部分的第一个位置一定是它
综上所述,直接查区间询第(r-l+1)/2+1小,如果它的出现次数>=(r-l+1)/2+1,那它就符合条件,否则不符合条件
#include<cstdio> #include<algorithm> #define N 500001 using namespace std; int n,m,tot,a[N],hash[N]; int root[N],sum[N*20],lc[N*20],rc[N*20],cnt; int ans; void discrete() { sort(a+1,a+n+1); tot=unique(a+1,a+n+1)-(a+1); for(int i=1;i<=n;i++) hash[i]=lower_bound(a+1,a+tot+1,hash[i])-a; } inline void insert(int pre,int & now,int l,int r,int k) { sum[now=++cnt]=sum[pre]+1; if(l==r) return; int mid=l+r>>1; if(k<=mid) { rc[now]=rc[pre]; insert(lc[pre],lc[now],l,mid,k); } else { lc[now]=lc[pre]; insert(rc[pre],rc[now],mid+1,r,k); } } inline void query(int x,int y,int l,int r,int k,int p) { if(l==r) { if(sum[y]-sum[x]>=p) ans=a[l]; else ans=0; return; } int mid=l+r>>1,tmp=sum[lc[y]]-sum[lc[x]]; if(k<=tmp) query(lc[x],lc[y],l,mid,k,p); else query(rc[x],rc[y],mid+1,r,k-tmp,p); } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]),hash[i]=a[i]; discrete(); for(int i=1;i<=n;i++) insert(root[i-1],root[i],1,tot,hash[i]); int s,t,k; for(int i=1;i<=m;i++) { scanf("%d%d",&s,&t); k=(t-s+1>>1)+1; query(root[s-1],root[t],1,tot,k,k); printf("%d\n",ans); } }
[Poi2014]Couriers