BZOJ3781 小B的询问 【莫队算法】

tonyfang posted @ 2015年8月28日 19:31 in BZOJ with tags c++ OI , 644 阅读

题目大意:给定一个序列,多次询问某个区间内所有数字出现个数的平方和。

莫队算法的题目。

所谓莫队算法,指的是以下一类问题:

已知$[L,R]$的解,能算出$[L,R+1],[L,R-1],[L+1,R],[L-1,R]$的解的,就可以使用莫队算法。莫队算法就是离线询问,排序后处理,其实就是大暴力~优化了顺序。

然后就打了遍莫队,发现TLE了。。。

然后去看了$PoPoQQQ$大神的代码,发现了这样一个奇怪的东西:

 

bool operator < (const quest &Y) const {
	if((Y.l>>8)!=(l>>8)) return l<Y.l;
	else return r<Y.r;
}

为什么要除以256...?不理解。。

发现我自己死活过不去,于是改成了一样的写法,竟然,过了。。。900ms。

我想知道这到底是个什么优化。。于是就把>>8改成了>>3,发现,也过了,但是,明显慢。

(RunID,User,Languege隐藏)

 

RunID User Problem Result Memory Time Language Code_Length Submit_Time
    3781 Accepted 1976 kb 6756 ms   904 B 2015-08-28 19:44:06
    3781 Accepted 1976 kb 904 ms   904 B 2015-08-28 19:41:31
   

上面那行是>>3的,下面那行是>>8的,这时间的差别。。。

upd: 2015/08/28 19:51

问了聚聚之后终于知道了。。。我的过。。

莫队算法的排序是左端点在一定区间内,按照右端点排序。。。

不是双关键字快排。。

一定区间这里取256为一个区间,一般取$sqrt(n)$。

我果然是弱= =$tooyoungtoosimple$

============================================

代码时间:

 

#include<stdio.h>
#include<algorithm>
using namespace std;
struct quest{
	int l,r,id;
	bool operator < (const quest &Y) const {
		if((Y.l>>8)!=(l>>8)) return l<Y.l;
		else return r<Y.r;
	}
}q[50010];
int n,m,k,a[50010];
int cnt[50010],left=1,right=0;
unsigned int ans[50010],ansx=0;
inline void g(int x,int t) {
	ansx-=cnt[x]*cnt[x];
	cnt[x]+=t;
	ansx+=cnt[x]*cnt[x];
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for (int i=1;i<=n;++i) scanf("%d",&a[i]);
	for (int i=1;i<=m;++i) q[i].id=i,scanf("%d%d",&q[i].l,&q[i].r);
	sort(q+1,q+m+1);
	for (int i=1;i<=m;++i) {
		while(right<q[i].r) g(a[++right],1);
		while(left>q[i].l) g(a[--left],1);
		while(right>q[i].r) g(a[right--],-1);
		while(left<q[i].l) g(a[left++],-1);
		ans[q[i].id]=ansx;
	}
	for (int i=1;i<=m;++i) printf("%u\n",ans[i]);
	return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter