首页 > 代码库 > 莫队算法
莫队算法
特意学了一下莫队算法，做了几个题，总结一下。
目前还只是学了线性序列的莫队的分块，没有学什么曼哈顿最小生成树。分开的写法也挺简单粗暴明了(据说曼哈顿距离的最小生成树并不好写)
时间复杂度是O(n*sqrt(n))。
做了几个题感觉莫队最主要的还是三个内容
1、离线
2、分块计算
3、由[l,r]到[l+1,r] or [l,r+1] or [l-1,r] or [l,r-1]可以在O(1)(ps:O(logn)应该也可以)内求出，且必须能在O(1)内求出
序列型 莫队算法 分块过程基本上都是一样的，把整个序列按照index从小到大分成sqrt(n)块，记录下序列中每个元素所在的块，把离线后的询问按照 左端点 l 所在块 为第一关键字，右端点 r 为第二关键字排序。这样排序比直接以左端点l 和右端点r排序对于等一下的计算优化了太多，可以尝试一下这两种方法的感觉。
接下来就是对于每一块询问里的每一个进行计算了，上面的的过程基本上都是通用的，每个题和每个题不同的地方就在于怎么用O(1)的复杂度求出下一个状态。
CSU 1515 Sequence
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1515
求给定区间里满足|a[i]-a[j]|=1 有多少pair
中南校赛时的一个题，那时不会莫队，然后纵看水题飞走
因为a[i]最大会有2^31所以不能用数组标记，可以用map，事实证明虽然AC 但是很慢
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #include <map> 6 using namespace std; 7 const int maxn = 100005; 8 typedef long long LL; 9 struct node10 {11 int l,r;12 int id;13 int ans;14 }a[maxn];15 map<int,int>vis;16 int c[maxn];17 int pos[maxn];18 int ans;19 bool cmp(node a,node b)20 {21 if(pos[a.l]==pos[b.l])return a.r<b.r;22 return a.l<b.l;23 }24 bool cmp_id(node a,node b)25 {26 return a.id<b.id;27 }28 void update(int x,int add)29 {30 x = c[x];31 vis[x]+=add;32 ans+=add*vis[x+1];33 if(x>0)ans+=add*vis[x-1];34 35 }36 int main()37 {38 // freopen("in.txt","r",stdin);39 int n,m;40 while(~scanf("%d%d",&n,&m))41 {42 int block = int(sqrt(n));43 vis.clear();44 for(int i = 1;i<=n;++i){scanf("%d",&c[i]);pos[i] = (i-1)/block+1;}45 for(int i = 1;i<=m;++i)46 {47 scanf("%d%d",&a[i].l,&a[i].r);48 a[i].id = i;49 }50 sort(a+1,a+1+m,cmp);51 ans = 0;52 int l = 1,r = 0;53 for(int i = 1;i<=m;++i)54 {55 while(r<a[i].r)update(r+1,1),r++;;56 while(r>a[i].r)update(r,-1),r--;57 while(l<a[i].l)update(l,-1),l++;58 while(l>a[i].l)update(l-1,1),l--;59 a[i].ans = ans;60 }61 sort(a+1,a+1+m,cmp_id);62 for(int i = 1;i<=m;++i)printf("%d\n",a[i].ans);63 }64 return 0;65 }66 67 /**************************************************************68 Problem: 151569 User: round_070 Language: C++71 Result: Accepted72 Time:6328 ms73 Memory:4224 kb74 ****************************************************************/
BZOJ 2038小Z的袜子(hose)
http://www.lydsy.com/JudgeOnline/problem.php?id=2038
这题是经典
1 /************************************************************** 2 Problem: 2038 3 User: round_0 4 Language: C++ 5 Result: Accepted 6 Time:1748 ms 7 Memory:3168 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 using namespace std;14 const int maxn = 50005;15 typedef long long LL;16 LL sqr(LL x)17 {18 return x*x;19 }20 struct node21 {22 int l;23 int r;24 int id;25 LL a,b;26 }a[maxn];27 int pos[maxn];28 bool cmp(node a,node b)29 {30 if(pos[a.l]==pos[b.l])return a.r<b.r;31 return a.l<b.l;32 }33 bool cmp_id(node a,node b)34 {35 return a.id<b.id;36 }37 LL ans;38 LL cnt[maxn],c[maxn];39 void update(int pos,int add)40 {41 ans-=sqr(cnt[c[pos]]);42 cnt[c[pos]]+=add;43 ans+=sqr(cnt[c[pos]]);44 }45 LL gcd(LL a,LL b)46 {47 return b?gcd(b,a%b):a;48 }49 50 int main()51 {52 // freopen("in.txt","r",stdin);53 int n,m;54 while(~scanf("%d%d",&n,&m))55 {56 int block = (int)sqrt(n);57 for(int i = 1;i<=n;++i)58 {59 scanf("%lld",&c[i]);60 cnt[i] = 0;61 pos[i] = (i-1)/block+1;62 }63 for(int i = 1;i<=m;++i)64 {65 scanf("%d%d",&a[i].l,&a[i].r);66 a[i].id = i;67 }68 ans = 0;69 sort(a+1,a+1+m,cmp);70 int l = 1,r = 0;71 LL x = 0;72 for(int i = 1;i<=m;++i)73 {74 while(r<a[i].r){update(r+1,1);r++;x++;}75 while(r>a[i].r){update(r,-1);r--;x++;}76 while(l<a[i].l){update(l,-1);x++;l++;}77 while(l>a[i].l){update(l-1,1);l--;x++;}78 a[i].a = ans-(r-l+1);79 a[i].b = (LL)(r-l+1)*(r-l);80 LL k = gcd(a[i].a,a[i].b);81 a[i].a/=k;82 a[i].b/=k;83 }84 sort(a+1,a+1+m,cmp_id);85 for(int i = 1;i<=m;++i)printf("%lld/%lld\n",a[i].a,a[i].b);86 }87 return 0;88 }
BZOJ 1878 HH的项链
http://www.lydsy.com/JudgeOnline/problem.php?id=1878
水题
1 /************************************************************** 2 Problem: 1878 3 User: round_0 4 Language: C++ 5 Result: Accepted 6 Time:2908 ms 7 Memory:9416 kb 8 ****************************************************************/ 9 10 #include <cmath>11 #include <cstdio>12 #include <cstring>13 #include <algorithm>14 using namespace std;15 const int maxn = 200005;16 struct node17 {18 int l,r;19 int id;20 int ans;21 }a[maxn];22 int cnt[maxn*5];23 int val[maxn];24 int pos[maxn];25 int ans;26 bool cmp(node a,node b)27 {28 if(pos[a.l]==pos[b.l])return a.r<b.r;29 return a.l<b.l;30 }31 bool cmp_id(node a,node b)32 {33 return a.id<b.id;34 }35 void update(int x,int status)36 {37 x = val[x];38 if(status==1)39 {40 if(!cnt[x])ans++;41 cnt[x]++;42 }43 else44 {45 if(cnt[x]==1)ans--;46 cnt[x]--;47 }48 }49 int main()50 {51 // freopen("in.txt","r",stdin);52 int n,m;53 while(~scanf("%d",&n))54 {55 int block = (int)sqrt(n);56 memset(cnt,0,sizeof(cnt));57 for(int i = 1;i<=n;++i){scanf("%d",&val[i]);pos[i]=(i-1)/block+1;}58 scanf("%d",&m);59 for(int i = 1;i<=m;++i)60 {61 scanf("%d%d",&a[i].l,&a[i].r);62 a[i].id = i;63 }64 sort(a+1,a+1+m,cmp);65 int l = 1,r = 0;66 ans = 0;67 for(int i = 1;i<=m;++i)68 {69 while(r<a[i].r)update(r+1,1),r++;70 while(r>a[i].r)update(r,-1),r--;71 while(l<a[i].l)update(l,-1),l++;72 while(l>a[i].l)update(l-1,1),l--;73 a[i].ans = ans;74 }75 sort(a+1,a+1+m,cmp_id);76 for(int i = 1;i<=m;++i)printf("%d\n",a[i].ans);77 78 }79 return 0;80 }
HDU 4638 Group
http://acm.hdu.edu.cn/showproblem.php?pid=4638
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 100005; 7 int c[maxn],pos[maxn]; 8 bool vis[maxn]; 9 struct node10 {11 int l;12 int r;13 int id;14 int ans;15 }a[maxn];16 int ans;17 bool cmp(node a,node b)18 {19 if(pos[a.l]==pos[b.l])return a.r<b.r;20 return a.l<b.l;21 }22 bool cmp_id(node a,node b)23 {24 return a.id<b.id;25 }26 void update(int x,int status)27 {28 int m = c[x],l = m-1,r = m+1;29 if(status==1)30 {31 if(vis[l]==0&&vis[r]==0)ans++;32 else if(vis[l]&&vis[r])ans--;33 vis[m] = 1;34 }35 else36 {37 if(vis[l]==0&&vis[r]==0)ans--;38 else if(vis[l]==1&&vis[r]==1)ans++;39 vis[m] = 0;40 }41 }42 int main()43 {44 // freopen("in.txt","r",stdin);45 int T;scanf("%d",&T);46 while(T--)47 {48 int n,m;scanf("%d%d",&n,&m);49 int block = (int)sqrt(n);50 for(int i = 1;i<=n;++i){scanf("%d",&c[i]);pos[i] = (i-1)/block+1;}51 memset(vis,0,sizeof(vis));52 for(int i = 1;i<=m;++i)53 {54 scanf("%d%d",&a[i].l,&a[i].r);55 a[i].id = i;56 }57 sort(a+1,a+m+1,cmp);58 int l = 1,r = 0;59 ans = 0;60 for(int i = 1;i<=m;++i)61 {62 while(r<a[i].r)update(r+1,1),r++;63 while(r>a[i].r)update(r,-1),r--;64 while(l<a[i].l)update(l,-1),l++;65 while(l>a[i].l)update(l-1,1),l--;66 67 a[i].ans = ans;68 }69 sort(a+1,a+1+m,cmp_id);70 for(int i = 1;i<=m;++i)printf("%d\n",a[i].ans);71 72 }73 return 0;74 }
WHU 1551 Pairs
http://acm.whu.edu.cn/land/problem/detail?problem_id=1551
和CSU1515 本页第一题一样
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 using namespace std; 6 const int maxn = 100005; 7 typedef long long LL; 8 struct node 9 {10 int l,r;11 int id;12 int ans;13 }a[maxn];14 int vis[maxn];15 int c[maxn];16 int pos[maxn];17 int ans;18 bool cmp(node a,node b)19 {20 if(pos[a.l]==pos[b.l])return a.r<b.r;21 return a.l<b.l;22 }23 bool cmp_id(node a,node b)24 {25 return a.id<b.id;26 }27 void update(int x,int add)28 {29 x = c[x];30 for(int i = max(x-2,0);i<=x+2;++i) if(i!=x)31 ans+=add*vis[i];32 if(add==1)ans+=vis[x];33 else ans-=(vis[x]-1);34 vis[x]+=add;35 }36 int main()37 {38 // freopen("in.txt","r",stdin);39 int n,m,kase = 1;40 while(~scanf("%d%d",&n,&m))41 {42 int block = int(sqrt(n));43 memset(vis,0,sizeof(vis));44 for(int i = 1;i<=n;++i){scanf("%d",&c[i]);pos[i] = i/block;}45 for(int i = 1;i<=m;++i)46 {47 scanf("%d%d",&a[i].l,&a[i].r);48 a[i].id = i;49 }50 sort(a+1,a+1+m,cmp);51 ans = 0;52 int l = 1,r = 0;53 for(int i = 1;i<=m;++i)54 {55 while(r<a[i].r)update(r+1,1),r++;;56 while(r>a[i].r)update(r,-1),r--;57 while(l<a[i].l)update(l,-1),l++;58 while(l>a[i].l)update(l-1,1),l--;59 a[i].ans = ans;60 }61 sort(a+1,a+1+m,cmp_id);62 printf("Case %d:\n",kase++);63 for(int i = 1;i<=m;++i)printf("%d\n",a[i].ans);64 }65 return 0;66 }
莫队就先告一段落了，去找点别的好玩的学一下
莫队算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。