莫隊1 走上騙分之路

新坑介紹莫隊, 第一篇是不帶修的線性莫隊.

什么是莫隊

一種硬往兩邊擴展 (可能是收縮) 的玄學算法, 是老前輩莫濤老師發明的算法, 又因為莫老師進了國家隊, 所以叫莫隊.

Google搜索需要搜索"Mo's Algo".

莫隊能解決什么問題

很多, 只要 \([l, r]\) 這個區間的答案可以 \(O(1)\) 擴展到 \([l - 1, r]\), \([l + 1, r]\), \([l, r - 1]\) 和 \([l, r + 1]\) 這四個相鄰區間的答案就可以用.

舉例區間和

給一個數組和很多區間, 不帶修, 求這些區間的和.

這個題顯然是前綴和板子, 但是我們在討論莫隊, 所以只考慮莫隊.

由于沒這個題, 所以給個樣例, 強度不知道大不大.

9 5
2 3 5 7 11 13 17 19 23
1 5
2 6
3 9
1 9
5 5

28
39
95
100
11

首先, 這個題擴展到相鄰區間只需要加加減減的, 顯然 \(O(1)\), 那么莫隊考慮的就是怎么讓這些加加減減的次數更少.

莫隊的想法是, 給詢問排序, 先看左端點所在的塊, 再看右端點.

qsort 在 stdlib.h 或 cstdlib 里, 用不習慣可以用 sort(q + 1, q + Q + 1, cmp) 然后把 cmp 的比較改掉, 返回 \(x - y\) 就改成 \(x < y\), 返回 \(-x + y\) 就改成 \(x > y\).

typedef struct _node {
  int l, r, i;
} qryy;

int cmp(const void *a, const void *b) {
  qryy *x = (qryy*)(a), *y = (qryy*)(b);
  if (pos[x->l] ^ pos[y->l]) {
    return pos[x->l] - pos[y->l];
  } else {
    return x->r - y->r;
  }
}
 
void get_ans() {
  int l = 1, r = 0;
  qsort(q + 1, Q, sizeof(q[0]), cmp);
  f1 (i, 1, Q, 1) {
    while (q[i].l < l) {
      s += a[--l];
    }
    while (l < q[i].l) {
      s -= a[l++];   
    }
    while (r < q[i].r) {
      s += a[++r];
    }
    while (q[i].r < r) {
      s -= a[r--];
    }
    ans[q[i].i] = s;
  }
}

read(&N, &Q);
M = pow(N, 0.5);
f1 (i, 1, N, 1) {
  read(a + i);
  pos[i] = (i - 1) / M + 1;
}
f1 (i, 1, Q, 1) {
  read(&q[i].l, &q[i].r);
  q[i].i = i;
}
get_ans();
f1 (i, 1, Q, 1) {
  cout << ans[i] << endl;
}

不過既然 \(l\) 和 \(r\) 看上去這么像隊頭和隊尾, 那么也有可能莫隊是莫濤老師の雙端隊列吧.

有的問題需要預處理

VJudge SPOJ LuoGu 雙倍經驗_VJudge 雙倍經驗_LuoGu

求區間 unique 長, 就是區間降重后的數量.

SDOI再次坐實板子巨多.

雙倍經驗的數據范圍較大, 所以數組都看著雙倍經驗開即可.

我們先預處理出每個數上一次在哪出現, 下一次在哪出現, 然后用這個擴展即可.

void init() {
  f1 (i, 1, N, 1) {
    pre[i] = lst[a[i]];
    lst[a[i]] = i;
  }
  f1 (i, 1, N, 1) {
    lst[a[i]] = N + 1;
  }
  f2 (i, N, 1, 1) {
    nxt[i] = lst[a[i]];
    lst[a[i]] = i;
  }
}

int cmp(const void *a, const void *b) {
  qryy *x = (qryy*)(a), *y = (qryy*)(b);
  if (pos[x->l] ^ pos[y->l]) {
    return pos[x->l] - pos[y->l];
  } else {
    return x->r - y->r;
  }
}

void get_ans() {
  int l = 1, r = 0;
  qsort(q + 1, Q, sizeof(q[0]), cmp);
  f1 (i, 1, Q, 1) {
    while (q[i].l < l) {
      s += (nxt[--l] > r);
    }
    while (l < q[i].l) {
      s -= (nxt[l++] > r);
    }
    while (r < q[i].r) {
      s += (pre[++r] < l);
    }
    while (q[i].r < r) {
      s -= (pre[r--] < l);
    }
    ans[q[i].i] = s;
  }
}

read(&N);
M = pow(N, 0.5);
f1 (i, 1, N, 1) {
  read(a + i);
  pos[i] = (i - 1) / M + 1;
}
init();
read(&Q);
f1 (i, 1, Q, 1) {
  read(&q[i].l, &q[i].r);
  q[i].k = i;
}
get_ans();
f1 (i, 1, Q, 1) {
  cout << ans[i] << endl;
}