莫队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, k;
} 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 if (pos[x->l] & 1) {
    return -x->r + y->r;
  } 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 (r < q[i].r) {
      s += a[++r];
    }
    while (l < q[i].l) {
      s -= a[l++];   
    }
    while (q[i].r < r) {
      s -= a[r--];
    }
    ans[q[i].k] = s;
  }
}

不过既然 \(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 if (pos[x->l] & 1) {
    return -x->r + y->r;
  } 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 (r < q[i].r) {
      s += (pre[++r] < l);
    }
    while (l < q[i].l) {
      s -= (nxt[l++] > r);   
    }
    while (q[i].r < r) {
      s -= (pre[r--] < l);
    }
    ans[q[i].k] = 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();
for (int i(1); i <= Q; ++i) {
  cout << ans[i] << endl;
}