5652. Snow White and the N dwarfs - #include <Seter> - using namespace Orz;

5652. Snow White and the N dwarfs

Seter posted @ 2011年11月26日 21:45 in SPOJ with tags Dichotomize&Check Classical , 2437 阅读

http://www.spoj.pl/problems/PATULJCI/

ID	DATE	USER	PROBLEM	RESULT	TIME	MEM	LANG
6087529	2011-11-26 13:51:59	Seter	Snow White and the N dwarfs	accepted edit run	3.89	29M	C

SPOJ上PCOUNT的冉克一被别的神犇夺走了……这么多天终于又有个冉克一了……

这道题的题意是求区间众数（出现次数严格大于长度的一半）。一开始想得是划分树（如果有众数，则一定是区间的中位数），但是“众数”这么好的性质（其实也不是很好……）没有利用，太可惜了！

首先，如果知道了可能的众数x，如何判定x的出现次数是否严格大于l/2呢？将n个数排序，以数值为第一关键字，位置为第二关键字。然后记录某个数值的尾在这个数组的哪里。二分查找a的后继和b的前继，相减就能得到a..b中x出现次数。

排序时可以用基数排序，这样不仅快，而且排好后就可以同时记录下某个数值的尾的位置。

下面假设存在众数（求出假设存在的众数后二分判定）。

先考虑O(NC)的算法。预处理出f[i][j]表示前i个数中j出现了几次。然后j在a..b中出现次数就是f[b][j]-f[a-1][j]。

由于假设了众数存在，那么当1..C-1都不是众数时，C一定是众数。如果C是2就好了，如果不是1，那一定是2！

于是试着将区间里的数表示为二进制，某一位如果不是0，那一定是1！

于是f[i][j]表示前i个数第j位为1的数有几个，对于每一位，如果f[b][j]-f[a-1][j]>=l/2，那么这位一定是1，反之一定是0！于是问题得以解决。

一开始#6WAD4……原因居然是计算出现次数时算成原数列中第一个众数和最后一个众数的距离了……我太2了……

PS：BZOJ上这题我Rank2……ymRank1的……

#include <stdio.h>
#include <stdlib.h>
int n,c,cs,a[300001][17],rs[300000],rk[300000][2],m[100002];
char str[4000000],*p=str;
inline getint(){
	int re=0;
	while(*p<'0'||*p>'9')p++;
	while(*p>='0'&&*p<='9')re=re*10+*p++-48;
	return re;
}main(){
	int i=-1,j=-1,A,B,t,ans,l,r,mid,k;fread(str,1,4000000,stdin);
	for(n=getint(),cs=32-__builtin_clz(c=getint()+1);++i!=n;j=-1)for(m[(rs[i]=t=getint())+1]++;++j!=cs;t>>=1)a[i+1][j]=a[i][j]+(t&1);
	for(i=1;i++!=c;m[i]+=m[i-1]);
	for(i=-1;++i!=n;rk[m[rs[i]]++][1]=i)rk[m[rs[i]]][0]=rs[i];
	for(t=getint();t--;){
		A=getint()-1;B=getint();j=B-A>>1;ans=0;
		for(i=-1;++i!=cs;)if(a[B][i]-a[A][i]<<1==B-A){ans=0;break;}else if(a[B][i]-a[A][i]>j)ans+=1<<i;
		if(!ans||ans>=c||m[ans]==m[ans-1]){puts("no");continue;}
		for(l=m[ans-1]-1,r=m[ans]-1;l+1!=r;rk[mid][1]>A?(r=mid):(l=mid))if(rk[mid=1+l+r>>1][1]==A)break;
		k=1+l+r>>1;
		for(l=m[ans-1],r=m[ans];l+1!=r;rk[mid][1]>B-1?(r=mid):(l=mid))if(rk[mid=l+r>>1][1]==B-1)break;
		if((l+r>>1)-k>=j)printf("yes %d\n",ans);else puts("no");
	}return 0;
}

By Seter