注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

小Z的袜子(莫队算法)  

2013-05-04 13:28:46|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
实在是觉得莫队算法太神奇了。
有修改的我暂时还不会
但是那种只有区间进行询问的题目,莫队算法基本上接近无敌了(我用词还是很注意的……)

讲下这道题吧
经过一些化简之后,我们知道这题要求的实质其实是sigma{S[i]^2},S[i]表示在[l,r]里面第i种袜子的出现次数
如何做呢?

能使用莫队算法的前提是这样的
如果我们已知[l,r]的答案,能在O(1)时间得到[l+1,r]的答案以及[l,r-1]的答案,即可使用莫队算法。时间复杂度为O(n^1.5)。如果那个只能在logn的时间求,则时间复杂度是O(n^1.5*log n)。
说白了,就是用一个“神奇的数据结构”维护插入、删除操作

这道题的话我们很容易用“数组”来实现那个“神奇的数据结构”,做到O(1)的从[l,r]转移到[l,r+1]与[l+1,r]

那么莫队算法怎么做呢?以下都是在转移为O(1)的基础下讨论的时间复杂度。另外由于n与m同阶,为了书写方便,我就全部写成n了……
如果已知[l,r]的答案,要求[l',r']的答案,我们很容易在O( | l - l' + | r - r' | )的时间复杂度内求得

莫涛大神是这么说的:把询问[l,r]抽象成一个点(l,r),题目就转化为求n个点的最小曼哈顿哈密尔顿路;由于这是个NP问题,所以我们希望找到一个稍微劣一点又不是很劣的但是能快速求得方案。莫涛大神在他的论文里使用了二维曼哈顿距离最小生成树
二维曼哈顿距离最小生成树可以用区域划分法+树状数组/线段树维护区间极值在nlogn的时间复杂度内完成构图,并用Kruskal在n log n时间内求得,但是代码比较繁琐。
这里介绍一个优美的替代品——分块
将n个数分成sqrt(n)块
按区间排序,以左端点所在块内为第一关键字,右端点为第二关键字,进行排序
也就是以( pos [l],r )排序
然后搞就可以了

为什么呢?
搞得过程是这样的:
一、i与i+1在同一块内,r单调递增,所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
二、i与i+1跨越一块,r最多变化n,由于有n^0.5块,所以这一部分时间复杂度是n^1.5
三、i与i+1在同一块内时变化不超过n^0.5,跨越一块也不会超过2*n^0.5,不妨看作是n^0.5。由于有n个数,所以时间复杂度是n^1.5
于是就变成了O(n^1.5)了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 50010
using namespace std;
typedef long long LL;
int pos[maxn],color[maxn],n,m;
LL S[maxn];
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
struct Question
{
int l,r,id;
LL a,b;
friend bool operator < (const Question &a,const Question &b)
{
return pos[a.l]<pos[b.l]||(pos[a.l]==pos[b.l]&&a.r<b.r);
}
}ask[maxn];
bool cmp_id(const Question &a,const Question &b)
{
return a.id<b.id;
}
void read()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&color[i]);
int limit=(int)sqrt(n+0.5);
for(int j=1;j<=n;j++)
pos[j]=(j-1)/limit+1;
for(int i=1;i<=m;i++)
{
scanf("%d %d",&ask[i].l,&ask[i].r);
ask[i].id=i;
}
sort(ask+1,ask+m+1);
}
void Modify(int p,LL &ans,int add)
{
ans=ans-S[color[p]]*S[color[p]];
S[color[p]]+=add;
ans=ans+S[color[p]]*S[color[p]];
}
void work()
{
/* l,r -> [l,r] */
LL ans=0;
for(int i=1,l=1,r=0;i<=m;i++)
{
if(r<ask[i].r)
{
for(r=r+1;r<=ask[i].r;r++)
Modify(r,ans,1);
r--;
}
if(r>ask[i].r)
for(;r>ask[i].r;r--)
Modify(r,ans,-1);
if(l<ask[i].l)
for(;l<ask[i].l;l++)
Modify(l,ans,-1);
else if(l>ask[i].l)
{
for(l=l-1;l>=ask[i].l;l--)
Modify(l,ans,1);
l++;
}
if(ask[i].l==ask[i].r)
{
ask[i].a=0,ask[i].b=1;
continue;
}
ask[i].a=ans-(ask[i].r-ask[i].l+1),ask[i].b=(LL)(ask[i].r-ask[i].l+1)*(ask[i].r-ask[i].l);
LL k=gcd(ask[i].a,ask[i].b);
ask[i].a/=k,ask[i].b/=k;
}
/*
sigma(S[i]*(S[i]-1)/2)/[(r-l+1)*(r-l)/2]
=sigma(S[i]*(S[i]-1))/[(r-l+1)*(r-l)]
=[sigma(S[i]*S[i])-(r-l+1)]/[(r-l+1)*(r-l)]
*/
}
void print()
{
sort(ask+1,ask+m+1,cmp_id);
for(int i=1;i<=m;i++)
printf("%lld/%lld\n",ask[i].a,ask[i].b);
}
int main()
{
read();
work();
print();
return 0;
}


  评论这张
 
阅读(4690)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017