[关闭]
@XLM 2017-09-26T23:52:35.000000Z 字数 2703 阅读 428

离线的另一种生活——莫队算法

莫队 算法思想 分块 离线处理

当处理题目中一个一个繁琐又冗杂的询问时，最好办法当然是在线处理，也就是问一个答一个。然而有时候在线处理会遇到出题人各种各样的陷阱，有些题也没办法使用线段树等适宜的在线算法。这时候就需要我们离线了。

离线干什么？当然，如果你离线后还打算暴搜，那你还是不要看这篇文章较好。
离线是为了什么，简单来说，就是为了一种更好的处理询问的顺序

如果你问：顺序到底有多重要？
我不说话，我们先看这样一道题：
我就没有这种丢袜子还能出出题的经历

简述一下题目大意，处理区间内随机取两个数相同的概率。
不难想出，对于区间l-r，答案为sum(C(2,f[i])/C(2,r-l+1)(其中f[i]为数值，C为组合数)
然后自然，也可以看到，在我们知道区间l-r的答案时，我们可以用O(1)求出区间(l-1)-r和区间l-(r+1)的值，具体方法
代码可以像这样：

  1. void move(int po,ll &ans,int add){
  2.     ans=ans+2*add*f[val[po]]+1;
  3.     f[val[po]]+=add;
  4. }
  5. //解释一下代码，po为我当前要对l-r区间内加入或删除的位置，ans是维护的一个当前操作得到的一个值
  6. //add是一个标记，来标记是加入还是删除，1为加入，-1为删除
  7. //f数组呢，是我维护的当前区间的数的数量

我们当然可以暴力加入减少l和r，但是我们排个序，减少次数不是更好吗。
排序……朴素排序吗？
当然不行，因为如果分别用l和r作为关键字排序的话，很容易被卡到O(n^2)
比如这样，我给出一组数据

  1. 1 5
  2. 2 100
  3. 3 5
  4. 4 100

如果按照l，r排序的话，会先加入到5，再到100，再减少为5再到100.
由于出题人常常是个恶趣味，他很可能会这么卡你卡到死
那么得按照一个别的排序方式，emmmmm

为了保证一个稳定的加入复杂度，我们想到了分块
就以左端点所在的块为第一关键字，右端点为第二关键字好了。
那么这样的复杂度呢，有证明认为在O(n^1.5)上下
粘上证明好了

  1. 右端点移动：
  2. 首先我们考虑一个块里面的转移情况
  3. 由于一个块里面的询问都按右端点排序
  4. 所以我们右端点在一个块里面最多移动n次
  5. 有 O(n√)O(n)个块，那么同一个块内的右端点移动最多就是O(nn√)O(nn)
  6. 然后考虑从一个块到另一个块导致的右端点变化
  7. 最坏情况，右端点由n到1，那么移动n次
  8. 有 O(n√)O(n)个块
  9. 那么从一个块到另一个块的事件只会发生O(n√)O(n)次……
  10. 所以这种右端点移动的次数也是O(nn√)O(nn)次
  11. 没有别的事件导致右端点移动了
  12. 左端点移动：
  13. 同一个块里面，由于左端点都在一个长度为O(n√)O(n)的区间里面
  14. 所以在同一块里面移动一次，左端点最多变化O(n√)O(n)
  15. 总共有n个询问……
  16. 所以同一块里面的移动最多n次
  17. 那么同一个块里面的左端点变化最多是O(nn√)O(nn)的
  18. 考虑跨越块
  19. 每由第i个块到第i+1个块，左端点最坏加上O(n√)O(n)
  20. 总共能加上O(n√)O(n)次
  21. 所以跨越块导致的左端点移动是O(n)O(n)的
  22. 综上，分块做法是O(n∗n√)O(n∗n)。

我们给出AC代码好了

  1. //来一发莫队
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring> 
  5. #include<iostream>
  6. #include<cmath>
  7. using namespace std;
  8. const int maxn=50010;
  9. typedef long long ll;
  11. ll gcd(ll a,ll b){
  12.     return (b==0)?a:gcd(b,a%b);
  13. }
  15. int val[maxn],pos[maxn];
  17. struct node{
  18.     int l,r,id;
  19.     ll a,b;
  20.     void sim(){
  21.         ll temp=gcd(a,b);
  22.         a/=temp,b/=temp;
  23.     }
  24.     bool operator <(const node &rhs)const{
  25.         if (pos[l]==pos[rhs.l]) return pos[r]<pos[rhs.r];
  26.         else return pos[l]<pos[rhs.l];
  27.     }
  28. }Q[maxn];
  30. bool cmp_id(const node &a,const node &b){
  31.     return a.id<b.id;
  32. }
  34. int f[maxn],n,m,limit;
  36. void read(){
  37.     scanf("%d%d",&n,&m);
  38.     for (int i=1;i<=n;i++){
  39.         scanf("%d",&val[i]);
  40.     }
  41.     limit=(int)sqrt(double(n+0.5));
  42.     for (int i=1;i<=n;i++)
  43.         pos[i]=(i-1)/limit+1;
  44.     for (int i=1;i<=m;i++){
  45.         scanf("%d%d",&Q[i].l,&Q[i].r);
  46.         Q[i].id=i;
  47.     }
  48.     sort(Q+1,Q+m+1);
  49. }
  51. void move(int po,ll &ans,int add){
  52.     ans=ans+2*add*f[val[po]]+1;
  53.     f[val[po]]+=add;
  54. }
  56. void deal(){
  57.     ll ans=0;
  58.     int l=1,r=0;
  59.     for (int i=1;i<=m;i++){
  60.         while (r<Q[i].r) r++,move(r,ans,1);    
  61.         while (Q[i].l<l) l--,move(l,ans,1);
  62.         while (Q[i].r<r) move(r,ans,-1),r--;
  63.         while (l<Q[i].l) move(l,ans,-1),l++;
  64.         Q[i].a=ans-(Q[i].r-Q[i].l+1);
  65.         Q[i].b=(ll)(Q[i].r-Q[i].l+1)*(Q[i].r-Q[i].l);
  66.         Q[i].sim();
  67.     }
  68.     sort(Q+1,Q+m+1,cmp_id);
  69.     for (int i=1;i<=m;i++){
  70.         printf("%lld/%lld\n",Q[i].a,Q[i].b);
  71.     }
  72. }
  74. int main(){
  75.     read();
  76.     deal();
  77. }

总结

那么，一篇文章，莫队来莫队去的，莫队是什么啊
emmm……莫队是种思想。
是什么
在考虑一个不满足区间加和性的的问题时，我们没办法使用我们一般使用惯了的数据结构(线段树什么的)，这时候我们就想，这些询问中有没有某种规律可以让我们减少复杂度和操作次数。
如果有的话我们换个方式，或者说，换个顺序，处理这些询问以便更加有复杂度减少方法。
为什么
因为这样可以搞事情啊
怎么用
就是排序分块吧
什么时候呢？
首先，这样一个一个改变区间的操作的复杂度必须在常数级别。
第二，可以离线（有一些强制在线的题）

然后呢，再给出几道题（待补充）
HH的项链（不带修改）
数颜色（带修改）

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注