[莫隊][學習筆記]

基礎

暴力！！

啥叫莫隊

莫隊是前國家隊隊長莫濤想出的演算法。用於處理一些可離線的區間問題。可以將本來是\(n^2\)的複雜度優化成n*根號級別。是基於分塊的。

普通莫隊

這類莫隊用來處理一類可離線，無修改的區間問題，也是最基礎的莫隊。

先來看這樣一道題:

給出一個長度為n的序列，然後有m次詢問，每次詢問從l到r這個區間內不同的數字的個數。\(1 \leq n ,m \leq 10^5\)

先考慮普通的暴力怎麼打，那就是每次詢問都掃一遍唄。

然後考慮有一些點，在很多次詢問的時候都被掃到過。是不是可以把這裡給優化一下。

是的。莫隊的做法是給每個位置的點分塊。然後把詢問離線下來，排個序。排序的標準是這樣的

bool cmp(node x,node y) {
    if(belong[x.l] != belong[y.l]) return x.l < y.l;
    else return x.r < y.r;
}

belong[i]表示i這個位置的點屬於哪個塊。也就是說，如果兩次查詢的左端點不在同一個塊里，那就按照左端點排序，否則按照右端點排序。這樣就可以達到每次詢問根號的複雜度了。

然後需要兩個指針L,R來表示當前統計的區間。然後每次不斷的往想要的區間跳。

一道板子題

題解

帶修莫隊

帶修莫隊其實就是在莫隊的基礎上加了個時間戳，排序的時候作為第三關鍵字，按從小到大排序。然後記錄下每次修改修改前的樣子和修改後的樣子。給每次詢問記錄下一個時間戳，也就是之前有幾次詢問。排完序之後，每次都把當前的時間暴力修改成查詢時的時間(沒錯，就是這麼暴力)，然後按照普通莫隊的查詢方式查詢就行了。

帶修莫隊當分的塊的大小為\(n^{\frac{2}{3}}\)時，複雜度最優秀，為\(n^{\frac{5}{3}}\)

一道模板題

代碼

/*
* @Author: wxyww
* @Date:   2018-12-17 14:32:03
* @Last Modified time: 2018-12-17 20:07:07
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<bitset>
using namespace std;
typedef long long ll;
const int N = 60010;
ll read() {
   ll x=0,f=1;char c=getchar();
   while(c<'0'||c>'9') {
      if(c=='-') f=-1;
      c=getchar();
   }
   while(c>='0'&&c<='9') {
      x=x*10+c-'0';
      c=getchar();
   }
   return x*f;
}
struct node {
   int pre,nex,x;//pre表示修改前的顏色，nex表示修改後的顏色，x表示修改的位置
}C[N];
struct Node {
   int tim,l,r,id;//l,r表示詢問的區間，tim表示詢問前進行過多少次修改。
}Q[N];
int col[N],cl[N];
int belong[N];
bool cmp(Node x,Node y) {
   if(belong[x.l] != belong[y.l]) return x.l < y.l;
   if(belong[x.r] != belong[y.r]) return x.r < y.r;
   return x.tim < y.tim;
}
int ch[N * 100],now,ans,L,R;
void LST() {//時光倒流
   col[C[now].x] = C[now].pre;
   if(C[now].x <= R && C[now].x >= L) {
      ch[C[now].nex]--;
      if(ch[C[now].nex] == 0) ans--;
      ch[C[now].pre]++;
      if(ch[C[now].pre] == 1) ans++;
   }
   now--;
}
void NET() {
   now++;
   col[C[now].x] = C[now].nex;
   if(C[now].x <= R && C[now].x >= L) {
      ch[C[now].pre]--;
      if(ch[C[now].pre] == 0) ans--;
      ch[C[now].nex]++;
      if(ch[C[now].nex] == 1) ans++;
   }
}
void update(int color,int c) {
   ch[color] += c;
   if(c > 0 && ch[color] == 1) ans++;
   if(c < 0 && ch[color] == 0) ans--;
}
int anss[N];
int main() {
   int n = read(),m = read();
   int unit = pow(n,0.666666);
   for(int i = 1;i <= n;++i) cl[i] = col[i] = read(),belong[i] = (i-1) / unit + 1;
   char c;
   int time = 0,qjs = 0;
   for(int i = 1;i <= m;++i) {
      c = getchar();
      while(c != 'Q' && c != 'R') c = getchar();
      if(c == 'Q') {
         Q[++qjs].tim = time;
         Q[qjs].l = read();
         Q[qjs].r = read();
         Q[qjs].id = qjs;
      }
      else {
         ++time;
         int x = read(),col = read();
         C[time].pre = cl[x];
         C[time].nex = col;
         C[time].x = x;
         cl[x] = col;
      }
   }
   sort(Q + 1,Q + qjs + 1,cmp);
   for(int i = 1;i <= qjs;++i) {
      while(now < Q[i].tim) NET();
      while(now > Q[i].tim) LST();
      while(L > Q[i].l) update(col[--L],1);
      while(R < Q[i].r) update(col[++R],1);
      while(L < Q[i].l) update(col[L++],-1);
      while(R > Q[i].r) update(col[R--],-1);
      anss[Q[i].id] = ans;
   }
   for(int i = 1;i <= qjs;++i) printf("%d\n",anss[i]);
   return 0;
}
/*
6 5
1 2 3 4 5 5
Q 1 4
Q 2 6
R 1 2
Q 1 4
Q 2 6
*/

樹上莫隊

留坑待填....