BZOJ3781 小B的询问 【莫队算法】
题目大意:给定一个序列,多次询问某个区间内所有数字出现个数的平方和。
莫队算法的题目。
所谓莫队算法,指的是以下一类问题:
已知$[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隐藏)
|
上面那行是>>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; }