莫队算法是谁发明的_班队工作计划与总结

莫队算法是谁发明的_班队工作计划与总结跟风学莫队,发现竟不会。博客一大堆,不知该看谁。刚开始要学习莫队的时候发现那么多的博客,真有乱花渐欲迷人眼的感觉,后来觉得不妨看看集训队的论文,才发现根本找不到,说是10-13年是作业的形式,根本没发表论文,那就只好一篇篇的去浏览,找到适合自己的。研究良久,觉得是时候对莫队做一波总结了。首先明白莫队可以解决的问题:区间问题类似这种:有n个数的整数数列,给出区间[l,r],求[l,r]中的...

跟风学莫队,发现竟不会。博客一大堆,不知该看谁。

刚开始要学习莫队的时候发现那么多的博客,真有乱花渐欲迷人眼的感觉,后来觉得不妨看看集训队的论文,才发现根本找不到,说是10-13年是作业的形式,根本没发表论文,那就只好一篇篇的去浏览,找到适合自己的。研究良久,觉得是时候对莫队做一波总结了。

首先明白莫队可以解决的问题:区间问题
类似这种:有n个数的整数数列,给出区间[l,r],求[l,r]中的计数问题,特点就是数组是静态的,但是动态查询。其他数据结构可以维护,但是有的时间复杂度太大,有的代码冗杂,莫队应运而生。

莫队的实现:可以在O(1)的时间内把[l,r]的询问转移到[l-1,r],[l+1,r],[l,r-1],[l,r+1]的询问,而且不需要修改操作,此时可以使用莫队算法来解决此问题。

首先以求[l,r]之间的出现次数为k次的数的个数为例,正常暴力的想法是每次跑一次[l,r],然后不超时算我输。这里做一个假设,假设区间[l,r]的答案已经得到,求[l`,r`]的答案,利用指针偏移的思想,让l去找l`,让r去找r`,这样得到时间复杂度是|l-l`|+|r-r`|  的算法,然后这可以看作点P(l,r)到点P`(l`,r`)的曼哈顿距离,然后对于所有m次询问,求一个最小生成树就是最理想的答案。这种算法叫最优曼哈顿距离生成树,为什么要介绍这个,因为要体现莫队的优越性啊,首先这样时间耗时是O(n^2*logn),m询问次数接近于n,故用n表示,然后代码长度可想而知,在已经区间[l.r]的基础上,引出莫队。

莫队的核心:分块,为什么要分块?假设已知区间[l.r]的解,正常情况的话最优的优化是曼哈顿生成树,但是,如果将序列分块的话,会发现意想不到的惊喜。已知[l,r],易得[l-1,r],[l,r+1],[l,r-1],[l-1,r-1],将所有的块进行排序,按左端点排序,若是左端点相同,就按右端点排序。然后去求解,类似于上面的算法,用两个指针去解决,要是所求区间在当前分块内,只需要移动右指针,此时的时间复杂度最大是O(n),因为是按照左端点和右端点两个关键字排序,所以右指针显然是递增的,即O(n),然后若是不在当前区间内,就移动左指针,左指针也是有序的最多进行分的块数次,通常分块会取\sqrt{n}次,得到总的时间复杂度O(n*\sqrt{n}),也就是通常所说的n的1.5次幂,莫队算法结束。

不难发现此算法的优点就是代码量少,而且时间复杂度可以接受,用通俗的语言再讲一下莫队的实现:将整个区间分块,分块后将所有的查询进行排序,将查询的区间不断移动,无非是左右指针的移动,最后得到每一次查询的答案,按照查询的顺序,输出答案。This is 神奇的莫队,This is 号称解决一切区间问题的莫队

拿个例题说明一下: BZOJ 2038 小Z的袜子(hose)
这是引出莫队算法的题目,也是最基础最能说明莫队的题目。分析此题的答案由两部分组成,分母部分是区间的长度的平方(不考虑组合,只考虑排列),分子是所有满足条件的平方和,考虑枚举区间,维护一个ans值,用一个数组去记录当前每种颜色出现的次数,首先是左指针右移,出现的结果就是某种颜色的值-1,不妨先把所有这种颜色的贡献都减去,然后更新这种颜色的贡献,最后都加上,得到ans值,最后ans值减去区间的长度就是分子,分母就是区间长度的平方。由于此题网上题解众多,此处就不多赘述,建议自己写一下,体会一下莫队的神奇。

代码实现:

/*
Look at the star
Look at the shine for U
*/ 

#include<bits/stdc++.h>
#define sl(x) scanf("%d",&x)
#define PII pair<ll,ll>
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7;
const ll INF = 0x3f3f3f3f;
struct node{
	int l,r,index;
	ll x,y;
}p[N];
ll sum[N],ans;
int s[N],cnt,num[N];
bool cmp(node a,node b) {return num[a.l] == num[b.l] ? a.r < b.r : a.l < b.l;}
bool CMP(node a,node b) {return a.index < b.index;}
void update(int x,int add)
{
	ans -= sum[s[x]]*(sum[s[x]]);
	sum[s[x]] += add;
	ans += sum[s[x]]*(sum[s[x]]);
}
int main()
{
	int n,m,i,j,k;
	sl(n);sl(m);
	cnt = pow(n,0.57);
	for(i = 1;i <= n;i++) sl(s[i]),num[i] = i/cnt+1;
	for(i = 1;i <= m;i++) sl(p[i].l),sl(p[i].r),p[i].index = i;
	sort(p+1,p+1+m,cmp);
	int l = 1,r = 0;
	for(i = 1;i <= m;i++)
	{
		while(l < p[i].l) update(l,-1),l++;
		while(l > p[i].l) update(l-1,1),l--;
		while(r < p[i].r) update(r+1,1),r++;
		while(r > p[i].r) update(r,-1),r--;
		if(p[i].l == p[i].r){p[i].x = 0;p[i].y = 1;continue;}
		p[i].x = ans-(p[i].r-p[i].l+1);
		p[i].y = 1ll*(p[i].r-p[i].l+1)*(p[i].r-p[i].l);
		ll gcd = __gcd(p[i].x,p[i].y);
		p[i].x /= gcd;p[i].y /= gcd; 
	}
	sort(p+1,p+1+m,CMP);
	for(i = 1;i <= m;i++) printf("%lld/%lld\n",p[i].x,p[i].y);
}
只听到从架构师办公室传来架构君的声音:
一自胡尘入汉关,十年伊洛路漫漫。有谁来对上联或下联?

异或序列 思维莫队
题意是给定一堆数,给出m次询问,问[l,r]之间,有多少个子区间的抑或和等于k。

此题要考虑如何在区间移动的过程中保证答案的正确性,根据异或的性质:a^b = c 即有a^c = b, b^c = a。推广到pre的异或,和,pre[i-1]^pre[i] = k, 即有 pre[i-1]^k = pre[i], pre[i-]^k = pre[i-1]。这样就可以在区间移动的过程中维护答案了。

代码实现:

此代码由Java架构师必看网-架构君整理
/* Look at the star Look at the shine for U */ #include<bits/stdc++.h> #define sl(x) scanf("%d",&x) #define PII pair<ll,ll> using namespace std; typedef long long ll; const int N = 1e6+5; const ll mod = 1e9+7; const ll INF = 0x3f3f3f3f; struct node{ int l,r,index; ll ans; }p[N]; ll sum[N],ans; int s[N],cnt,num[N],n,m,k; bool cmp(node a,node b) {return num[a.l] == num[b.l] ? a.r < b.r : a.l < b.l;} bool CMP(node a,node b) {return a.index < b.index;} void update(int x,int add) { if(!add) { sum[s[x]]--; ans -= sum[s[x]^k]; } else { ans += sum[s[x]^k]; sum[s[x]]++; } } int main() { int i,j; sl(n),sl(m);sl(k); cnt = pow(n,0.57); for(i = 1;i <= n;i++) sl(s[i]),num[i] = i/cnt+1,s[i] ^= s[i-1]; for(i = 1;i <= m;i++) sl(p[i].l),sl(p[i].r),p[i].index = i; sort(p+1,p+1+m,cmp); int l = 1,r = 0; sum[0] = 1; for(i = 1;i <=m;i++) { while(l < p[i].l) update(l-1,0),l++; while(l > p[i].l) l--,update(l-1,1); while(r < p[i].r) update(++r,1); while(r > p[i].r) update(r--,0); p[i].ans = ans; } sort(p+1,p+1+m,CMP); for(i = 1;i <= m;i++) printf("%lld\n",p[i].ans); }

通过以上两个题可以发现,莫队的关键是找到区间移动事维护答案的状态,即找到计数数组,并在区间移动的时候维护答案,技巧性比较大,所以还是多做题,熟能生巧。

本文来源Ever_glow,由架构君转载发布,观点不代表Java架构师必看的立场,转载请标明来源出处:https://javajgs.com/archives/153054
已赞1
   

发表评论