普通莫队

算法简介

对于序列上的区间询问问题，如果能O(1)O(1)内从[l,r][l,r]扩展得到[l−1,r][l-1,r]，[l+1,r][l+1,r]，[l,r−1][l,r-1]，[l,r+1][l,r+1]的答案，那么可以在O(nn)O(n\sqrt{n})内求出所有询问的答案。

对于区间[l,r][l,r]，以 ll 所在的块的编号为第一关键字，rr 的大小为第二关键字从小到大排序。对于每个块的第一个区间我们在 o(n)o(n) 内暴力求解，然后再暴力转移。

引例

首先看一个例子感受一下

有一个长度为 nn 的序列 。现在给出 mm 个询问，每次给出两个数 ，从编号在 ll 到 &r& 之间的数中随机选出两个不同的数，求两个数相等的概率。

首先按照简介中介绍的方法对这 mm 个区间排序，设选择相同颜色的方案数为 ansans,col[i]col[i] 表示当前区间颜色 ii 出现了多少次，且新加入或新删掉的元素颜色为 kk.

  • 当区间扩大一次时，ans+=Ccol [k]+12−Ccol [k]2,col[k]++ans+=C_{\text {col }[k]+1}^{2}-C_{\text {col }[k]}^{2},col[k]++
  • 当区间缩小一次时，ans+=Ccol [k]2−Ccol [k]−12,col[k]−−ans+=C_{\text {col }[k]}^{2}-C_{\text {col }[k]-1}^{2},col[k]--

注意有 Ccol [k]+12−Ccol [k]2=col[k]C_{\text {col }[k]+1}^{2}-C_{\text {col }[k]}^{2}=col[k] , Ccol [k]2−Ccol [k]−12=col[k]−1C_{\text {col }[k]}^{2}-C_{\text {col }[k]-1}^{2}=col[k]-1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 50005;
int n, m, maxn;
int c[N];
long long sum;
int cnt[N];
long long ans1[N], ans2[N];
struct query {
  int l, r, id;
  bool operator<(const query &x) const {  //这里的排序方式是有一点小优化的，下文会讲
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];
void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}
void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int main() {
  scanf("%d%d", &n, &m);
  maxn = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  for (int i = 0; i < m; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
      continue;
    }
	
    while (l > a[i].l) add(c[--l]);
    while (r < a[i].r) add(c[++r]);
    while (l < a[i].l) del(c[l++]);
    while (r > a[i].r) del(c[r--]);
	//注意应该要先尽量扩大区间然后再缩小，避免出现 l>r 的情况(其实出现了这种情况在大多数情况下也不会影响答案的正确性，但是有时候在某些特殊的题目中是会产生错误的答案的)

    ans1[a[i].id] = sum;
    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      long long g = gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    printf("%lld/%lld\n", ans1[i], ans2[i]);
  }
  return 0;
}

复杂度分析

设总的区间大小为 nn，询问数量为 mm，且 mm和 nn 数量级相同。

对所有询问的区间排序是 O(mlogm)O(mlogm) 的，然后对每个段中的第一个询问在 O(n)O(n) 内求解，所以总共复杂度为 O(nn)O(n\sqrt{n})。

接下来我们对于每个区间单独考虑

对于每个块中的 rr，是从小到大排好序的,所以依次向后更新即可，总共有 n\sqrt{n} 个块，则的复杂度为O(nn)O(n\sqrt{n})。

对于每个块中的 ll，每次的变化范围小于等于n\sqrt{n}，假设当前块有 ii 个元素，则复杂度为 O(in)O(i\sqrt{n})。所有块的元素加起来，复杂度为 O(mn)O(m\sqrt{n})

综上，复杂度为 O(nn)O(n\sqrt{n})

如果 mm和 nn 数量级不相同，可适当调整块的大小。

奇偶化排序优化

奇偶化排序即对于属于奇数块的询问，rr 按从小到大排序，对于属于偶数块的排序，rr 从大到小排序，这样我们的 rr 指针在处理完这个奇数块的问题后，将在返回的途中处理偶数块的问题，再向 nn 移动处理下一个奇数块的问题，优化了 rr 指针的移动次数，一般情况下，这种优化能让程序快 30%30\% 左右。

1
2
3
4
5
6
7
8
9
10
struct node {
  int l, r, id;
  bool operator<(const node &x) const {
    if (l / unit != x.l / unit) return l < x.l;
    if ((l / unit) & 1)
      return r <
             x.r;  // 注意这里和下面一行不能写小于（大于）等于，否则会RE,因为sort时遇到元素相等就必须返回false
    return r > x.r;
  }
};

带修改的莫队

莫队本是离线的，但是可以强行加上一维时间维，表示这步操作的时间，即第几次修改，这样把 [l,r][l,r] 变成[l,r,time][l,r,time]。于是我们也可以在时间维上移动，即

  • [l−1,r,time][l-1,r,time]
  • [l+1,r,time][l+1,r,time]
  • [l,r−1,time][l,r-1,time]
  • [l,r+1,time][l,r+1,time]
  • [l,r,time−1][l,r,time-1]
  • [l,r,time+1][l,r,time+1]

复杂度分析

假设询问次数为 mm，区间大小为 nn，为方便考虑，设若 mm 与 nn 同阶

这一次我们排序以 n23n^\frac{2}{3} 为一块，分为 n13n^\frac{1}{3} 块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。

  • 左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是 O(n)O(n)；
  • 若左右端点所在块改变，时间一次最多会移动 nn 个格子，时间复杂度 O(n)O(n) 为；
  • 左端点所在块一共有 n13n^\frac{1}{3} 种，右端点也是 n13n^\frac{1}{3} 种，一共 n23n^\frac{2}{3} 种，再乘上单独处理每个块的复杂度（包括初始化的移动以及块不变时时间的移动） O(n)O(n) ，总复杂度 n53n^\frac{5}{3}。

为什么要以 n23n^\frac{2}{3} 为一块的原因
设对第一关键字的块长度为 s1s_1，第二关键字的块长度为 s2s_2，则复杂度为

(ns1)(ns2)(m+n)+m(s1+s2)\left(\frac{n}{s_{1}}\right)\left(\frac{n}{s_{2}}\right)(m+n)+m\left(s_{1}+s{2}\right)

若 mm 与 nn 同阶，则 s1=s2=23s_1=s_2=\frac{2}{3} 时有最小值，即 n53n^\frac{5}{3}。

例题

给你一个序列，M 个操作，有两种操作：
1. 修改序列上某一位的数字
2. 询问区间 [l,r][l,r] 中数字的种类数（多个相同的数字只算一个）

参见复杂度分析中的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <bits/stdc++.h>
#define SZ (10005)
using namespace std;
template <typename _Tp>
inline void IN(_Tp& dig) {
  char c;
  dig = 0;
  while (c = getchar(), !isdigit(c))
    ;
  while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}
int n, m, sqn, c[SZ], ct[SZ], c1, c2, mem[SZ][3], ans, tot[1000005], nal[SZ];
struct query {
  int l, r, i, c;
  bool operator<(const query another) const {
    if (l / sqn == another.l / sqn) {
      if (r / sqn == another.r / sqn) return i < another.i;
      return r < another.r;
    }
    return l < another.l;
  }
} Q[SZ];
void add(int a) {
  if (!tot[a]) ans++;
  tot[a]++;
}
void del(int a) {
  tot[a]--;
  if (!tot[a]) ans--;
}
char opt[10];
int main() {
  IN(n), IN(m), sqn = pow(n, (double)2 / (double)3);
  for (int i = 1; i <= n; i++) IN(c[i]), ct[i] = c[i];
  for (int i = 1, a, b; i <= m; i++)
    if (scanf("%s", opt), IN(a), IN(b), opt[0] == 'Q')
      Q[c1].l = a, Q[c1].r = b, Q[c1].i = c1, Q[c1].c = c2, c1++;
    else
      mem[c2][0] = a, mem[c2][1] = ct[a], mem[c2][2] = ct[a] = b, c2++;
  sort(Q, Q + c1), add(c[1]);
  int l = 1, r = 1, lst = 0;
  for (int i = 0; i < c1; i++) {
    for (; lst < Q[i].c; lst++) {
      if (l <= mem[lst][0] && mem[lst][0] <= r)
        del(mem[lst][1]), add(mem[lst][2]);
      c[mem[lst][0]] = mem[lst][2];
    }
    for (; lst > Q[i].c; lst--) {
      if (l <= mem[lst - 1][0] && mem[lst - 1][0] <= r)
        del(mem[lst - 1][2]), add(mem[lst - 1][1]);
      c[mem[lst - 1][0]] = mem[lst - 1][1];
    }
    for (++r; r <= Q[i].r; r++) add(c[r]);
    for (--r; r > Q[i].r; r--) del(c[r]);
    for (--l; l >= Q[i].l; l--) add(c[l]);
    for (++l; l < Q[i].l; l++) del(c[l]);
    nal[Q[i].i] = ans;
  }
  for (int i = 0; i < c1; i++) printf("%d\n", nal[i]);
  return 0;
}

树上莫队

引例

给你一棵树，每个点有颜色，每次询问 ∑cvalc∑i=1cntcwi\sum_{c} v a l_{c} \sum_{i=1}^{c n t_{c}} w_{i}

其中：valval 表示该颜色的价值，cntcnt 表示颜色出现的次数，ww 表示该颜色出现 ii 次后的价值

括号序+莫队

利用dfs序把树强行压成序列。即把树的括号序跑下来，然后在括号序上面跑莫队。

我们开一个 visvis 数组，每次扫到点 xx，就把 vis[x]vis[x] 异或上 11 。

如果 vis[x]==0vis[x]==0 就不计算这个点的贡献，相当于这个点没有遍历过或者被扫了两次（被扫两次时即该点不位于所求路径上）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;

const int maxn = 200010;

int f[maxn], g[maxn], id[maxn], head[maxn], cnt, last[maxn], dep[maxn],
    fa[maxn][22], v[maxn], w[maxn];
int block, index, n, m, q;
int pos[maxn], col[maxn], app[maxn];
bool vis[maxn];
long long ans[maxn], cur;

struct edge {
  int to, nxt;
} e[maxn];
int cnt1 = 0, cnt2 = 0;  // 时间戳

struct query {
  int l, r, t, id;
  bool operator<(const query &b) const {
    return (pos[l] < pos[b.l]) || (pos[l] == pos[b.l] && pos[r] < pos[b.r]) ||
           (pos[l] == pos[b.l] && pos[r] == pos[b.r] && t < b.t);
  }
} a[maxn], b[maxn];

inline void addedge(int x, int y) {
  e[++cnt] = (edge){y, head[x]};
  head[x] = cnt;
}

void dfs(int x) {
  id[f[x] = ++index] = x;
  for (int i = head[x]; i; i = e[i].nxt) {
    if (e[i].to != fa[x][0]) {
      fa[e[i].to][0] = x;
      dep[e[i].to] = dep[x] + 1;
      dfs(e[i].to);
    }
  }
  id[g[x] = ++index] = x;  // 括号序
}

inline int lca(int x, int y) {
  if (dep[x] < dep[y]) swap(x, y);
  if (dep[x] != dep[y]) {
    int dis = dep[x] - dep[y];
    for (int i = 20; i >= 0; i--)
      if (dis >= (1 << i)) dis -= 1 << i, x = fa[x][i];
  }  // 爬到同一高度
  if (x == y) return x;
  for (int i = 20; i >= 0; i--) {
    if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
  }
  return fa[x][0];
}

inline void add(int x) {
  if (vis[x])
    cur -= (long long)v[col[x]] * w[app[col[x]]--];
  else
    cur += (long long)v[col[x]] * w[++app[col[x]]];
  vis[x] ^= 1;
}

inline void modify(int x, int t) {
  if (vis[x]) {
    add(x);
    col[x] = t;
    add(x);
  } else
    col[x] = t;
}  // 在时间维上移动

int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= m; i++) scanf("%d", &v[i]);
  for (int i = 1; i <= n; i++) scanf("%d", &w[i]);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d%d", &x, &y);
    addedge(x, y);
    addedge(y, x);
  }
  for (int i = 1; i <= n; i++) {
    scanf("%d", &last[i]);
    col[i] = last[i];
  }
  dfs(1);
  for (int j = 1; j <= 20; j++)
    for (int i = 1; i <= n; i++)
      fa[i][j] = fa[fa[i][j - 1]][j - 1];  // 预处理祖先
  int block = pow(index, 2.0 / 3);
  for (int i = 1; i <= index; i++) {
    pos[i] = (i - 1) / block;
  }
  while (q--) {
    int opt, x, y;
    scanf("%d%d%d", &opt, &x, &y);
    if (opt == 0) {
      b[++cnt2].l = x;
      b[cnt2].r = last[x];
      last[x] = b[cnt2].t = y;
    } else {
      if (f[x] > f[y]) swap(x, y);
      a[++cnt1] = (query){lca(x, y) == x ? f[x] : g[x], f[y], cnt2, cnt1};
    }
  }
  sort(a + 1, a + cnt1 + 1);
  int L, R, T;  // 指针坐标
  L = R = 0;
  T = 1;
  for (int i = 1; i <= cnt1; i++) {
    while (T <= a[i].t) {
      modify(b[T].l, b[T].t);
      T++;
    }
    while (T > a[i].t) {
      modify(b[T].l, b[T].r);
      T--;
    }
    while (L > a[i].l) {
      L--;
      add(id[L]);
    }
    while (L < a[i].l) {
      add(id[L]);
      L++;
    }
    while (R > a[i].r) {
      add(id[R]);
      R--;
    }
    while (R < a[i].r) {
      R++;
      add(id[R]);
    }
    int x = id[L], y = id[R];
    int llca = lca(x, y);
    if (x != llca && y != llca) {
      add(llca);
      ans[a[i].id] = cur;
      add(llca);
    } else
      ans[a[i].id] = cur;
  }
  for (int i = 1; i <= cnt1; i++) {
    printf("%lld\n", ans[i]);
  }
  return 0;
}

树上分块+莫队

这里分块的方式可以参考[SCOI2005]王室联邦以加深理解。

注意在存现有路径时不存 lcalca，即把 vis[lca]vis[lca] 置为 00 ,只是在计算的考虑它。不然代码写起来会很麻烦。这里的找路径的方法很巧妙，可以学习一下，我就不在这里放我的理解了，多看几遍肯定能看懂的这种东西只是口述的话只会越说越混乱，然而我太懒了，就不画图了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <bits/stdc++.h>
using namespace std;
inline int gi() {
  register int x, c, op = 1;
  while (c = getchar(), c < '0' || c > '9')
    if (c == '-') op = -op;
  x = c ^ 48;
  while (c = getchar(), c >= '0' && c <= '9')
    x = (x << 3) + (x << 1) + (c ^ 48);
  return x * op;
}
int head[100002], nxt[200004], ver[200004], tot = 0;
void add(int x, int y) {
  ver[++tot] = y, nxt[tot] = head[x], head[x] = tot;
  ver[++tot] = x, nxt[tot] = head[y], head[y] = tot;
}
int bl[100002], bls = 0;
unsigned step;
int fa[100002], dp[100002], hs[100002] = {0}, sz[100002] = {0}, top[100002],
                            id[100002];
stack<int> sta;
void dfs1(int x) {
  sz[x] = 1;
  unsigned ss = sta.size();
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x]) {
      fa[ver[i]] = x, dp[ver[i]] = dp[x] + 1;
      dfs1(ver[i]);
      sz[x] += sz[ver[i]];
      if (sz[ver[i]] > sz[hs[x]]) hs[x] = ver[i];
      if (sta.size() - ss >= step) {
        bls++;
        while (sta.size() != ss) bl[sta.top()] = bls, sta.pop();
      }
    }
  sta.push(x);
}
int cnt = 0;
void dfs2(int x, int hf) {
  top[x] = hf, id[x] = ++cnt;
  if (!hs[x]) return;
  dfs2(hs[x], hf);
  for (int i = head[x]; i; i = nxt[i])
    if (ver[i] != fa[x] && ver[i] != hs[x]) dfs2(ver[i], ver[i]);
}
int lca(int x, int y) {
  while (top[x] != top[y]) {
    if (dp[top[x]] < dp[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return dp[x] < dp[y] ? x : y;
}
struct qu {
  int x, y, t, id;
  bool operator<(const qu a) const {
    return bl[x] == bl[a.x] ? (bl[y] == bl[a.y] ? t < a.t : bl[y] < bl[a.y])
                            : bl[x] < bl[a.x];
  }
} q[100001];
int qs = 0;
struct ch {
  int x, y, b;
} upd[100001];
int ups = 0;
long long ans[100001];
int b[100001] = {0};
int a[100001];
long long w[100001];
long long v[100001];
long long now = 0;
bool vis[100001] = {0};
void back(int t) {
  if (vis[upd[t].x]) {
    now -= w[b[upd[t].y]--] * v[upd[t].y];
    now += w[++b[upd[t].b]] * v[upd[t].b];
  }
  a[upd[t].x] = upd[t].b;
}
void change(int t) {
  if (vis[upd[t].x]) {
    now -= w[b[upd[t].b]--] * v[upd[t].b];
    now += w[++b[upd[t].y]] * v[upd[t].y];
  }
  a[upd[t].x] = upd[t].y;
}
void update(int x) {
  if (vis[x])
    now -= w[b[a[x]]--] * v[a[x]];
  else
    now += w[++b[a[x]]] * v[a[x]];
  vis[x] ^= 1;
}
void move(int x, int y) {
  if (dp[x] < dp[y]) swap(x, y);
  while (dp[x] > dp[y]) update(x), x = fa[x];
  while (x != y) update(x), update(y), x = fa[x], y = fa[y];//注意这里没有考虑两节点的lca的贡献
}
int main() {
  int n = gi(), m = gi(), k = gi();
  step = (int)pow(n, 0.6);
  for (int i = 1; i <= m; i++) v[i] = gi();
  for (int i = 1; i <= n; i++) w[i] = gi();
  for (int i = 1; i < n; i++) add(gi(), gi());
  for (int i = 1; i <= n; i++) a[i] = gi();
  for (int i = 1; i <= k; i++)
    if (gi())
      q[++qs].x = gi(), q[qs].y = gi(), q[qs].t = ups, q[qs].id = qs;
    else
      upd[++ups].x = gi(), upd[ups].y = gi();
  for (int i = 1; i <= ups; i++) upd[i].b = a[upd[i].x], a[upd[i].x] = upd[i].y;
  for (int i = ups; i; i--) back(i);
  fa[1] = 1;
  dfs1(1), dfs2(1, 1);
  if (!sta.empty()) {
    bls++;
    while (!sta.empty()) bl[sta.top()] = bls, sta.pop();
  }
  for (int i = 1; i <= n; i++)
    if (id[q[i].x] > id[q[i].y]) swap(q[i].x, q[i].y);
  sort(q + 1, q + qs + 1);
  int x = 1, y = 1, t = 0;
  for (int i = 1; i <= qs; i++) {
    if (x != q[i].x) move(x, q[i].x), x = q[i].x;
    if (y != q[i].y) move(y, q[i].y), y = q[i].y;
    int f = lca(x, y);
    update(f);
    while (t < q[i].t) change(++t);
    while (t > q[i].t) back(t--);
    ans[q[i].id] = now;
    update(f); //考虑完lca的贡献后就删掉它
  }
  for (int i = 1; i <= qs; i++) printf("%lld\n", ans[i]);
  return 0;
}

回滚莫队

有些题目在区间转移时，可能会出现增加或者删除无法实现的问题。在只有增加不可实现或者只有删除不可实现的时候，就可以使用回滚莫队在 O(nn)O(n\sqrt{n}) 的时间内解决问题。回滚莫队的核心思想就是既然我只能实现一个操作，那么我就只使用一个操作，剩下的交给回滚解决。

引例

给你一个长度为 nn 的数组 AA 和 mm 个询问 ，每次询问一个区间 (1≤n,m≤105)\left(1 \leq n, m \leq 10^{5}\right) 内重要度最大的数字，要求输出其重要度。一个数字 ii 重要度的定义为 ii 乘上 ii 在区间内出现的次数。

对于本题目而言，增加的过程中更新答案是很好实现的，但是在删除的过程中更新答案是不好实现的。因为如果增加会影响答案，那么新答案必定是刚刚增加的数字的重要度，而如果删除过后区间重要度最大的数字改变，我们很难确定新的重要度最大的数字是哪一个。所以，普通的莫队很难解决这个问题。

注意，莫队只是一种思想，重要的是如何灵活应用。其实我们可以发现，就算我们只能增大区间而不能缩小区间，我们依然能用类似莫队算法的方法在 O(nn)O(n\sqrt{n}) 的时间内求解问题，具体做法为：

  1. 如果当前询问的左端点与上一次的左端点所属的块不同，则将莫队的左端点初始化为 BB 的右端点加 11， 将莫队区间的右端点初始化为 BB 的右端点（严格来说这样做的话左端点所在的块就变成当前块的后一个块了，但是我们还是认为左端点是属于当前块的，具体看代码实现）
  2. 如果当前询问的左右端点属于同一块，直接扫描区间得到答案
  3. 如果当前询问的左右端点所属的块不同，则
    • 如果当前询问的右端点大于莫队区间的右端点，不断扩展右端点直到达到当前询问的右端点。
    • 不断扩展莫队区间的左端点直到莫队区间的左端点等于询问的左端点
    • 回答询问后，撤销莫队区间左端点的改动，将其回滚到 BB 的右端点加 11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 5;
int n, q;
int x[N], t[N], m;

struct Query {
  int l, r, id;
} Q[N];
int pos[N], L[N], R[N], sz, tot;
int cnt[N], __cnt[N];
ll ans[N];

inline bool cmp(const Query& A, const Query& B) {
  if (pos[A.l] == pos[B.l]) return A.r < B.r;
  return pos[A.l] < pos[B.l];
}

void build() {
  sz = sqrt(n);
  tot = n / sz;
  for (int i = 1; i <= tot; i++) {
    L[i] = (i - 1) * sz + 1;
    R[i] = i * sz;
  }
  if (R[tot] < n) {
    ++tot;
    L[tot] = R[tot - 1] + 1;
    R[tot] = n;
  }
}

inline void Add(int v, ll& Ans) {
  ++cnt[v];
  Ans = max(Ans, 1LL * cnt[v] * t[v]);
}

inline void Del(int v) { --cnt[v]; }

int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) scanf("%d", &x[i]), t[++m] = x[i];
  for (int i = 1; i <= q; i++) scanf("%d %d", &Q[i].l, &Q[i].r), Q[i].id = i;

  build();

  // 对询问进行排序
  for (int i = 1; i <= tot; i++)
    for (int j = L[i]; j <= R[i]; j++) pos[j] = i;
  sort(Q + 1, Q + 1 + q, cmp);

  // 离散化
  sort(t + 1, t + 1 + m);
  m = unique(t + 1, t + 1 + m) - (t + 1);
  for (int i = 1; i <= n; i++) x[i] = lower_bound(t + 1, t + 1 + m, x[i]) - t;

  int l = 1, r = 0, last_block = 0, __l;
  ll Ans = 0, tmp;
  for (int i = 1; i <= q; i++) {
    // 询问的左右端点同属于一个块则暴力扫描回答
    if (pos[Q[i].l] == pos[Q[i].r]) {
      for (int j = Q[i].l; j <= Q[i].r; j++) ++__cnt[x[j]];
      for (int j = Q[i].l; j <= Q[i].r; j++)
        ans[Q[i].id] = max(ans[Q[i].id], 1LL * t[x[j]] * __cnt[x[j]]);
      for (int j = Q[i].l; j <= Q[i].r; j++) --__cnt[x[j]];
      continue;
    }

    // 访问到了新的块则重新初始化莫队区间
    if (pos[Q[i].l] != last_block) {
      while (r > R[pos[Q[i].l]]) Del(x[r]), --r;
      while (l < R[pos[Q[i].l]] + 1) Del(x[l]), ++l;
      Ans = 0;
      last_block = pos[Q[i].l];
    }

    // 扩展右端点
    while (r < Q[i].r) ++r, Add(x[r], Ans);
    __l = l;
    tmp = Ans;

    // 扩展左端点
    while (__l > Q[i].l) --__l, Add(x[__l], tmp);
    ans[Q[i].id] = tmp;

    // 回滚
    while (__l < l) Del(x[__l]), ++__l;
  }
  for (int i = 1; i <= q; i++) printf("%lld\n", ans[i]);
  return 0;
}

复杂度证明

利用左右端点是否同属于同一个块来把所有询问分为两类分别讨论，然后类似于普通莫队算法的复杂度证明，易征得复杂度仍为 O(nn)O(n\sqrt{n})

bitset + 莫队

「Ynoi2016」掉进兔子洞

先对所有的数字进行离散化处理，然后再对每个数字都用一个bitset来记录出现的情况，所以总共使用了 O(105∗105)O(10^5*10^5) 个比特（bit），由于空间限制为 500MB=500∗1024∗1024Byte=4194304000bit500MB=500*1024*1024Byte=4194304000bit，显然存不下，所以用要先把所有的询问分成足够小的几组再求解。

注意这里代码中 now.set(x+cnt[x])now.set(x+cnt[x]) 意思是把第 x+cnt[x]x+cnt[x] 位置为 11，含义为离散化后值为 xx 的数出现了 cnt[x]+1cnt[x]+1 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 100005, M = N / 3 + 10;
int n, m, maxn;
int a[N], ans[M], cnt[N];
bitset<N> sum[M], now;
struct query {
  int l, r, id;
  bool operator<(const query& x) const {
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} q[M * 3];
void static_set() {
  static int tmp[N];
  memcpy(tmp, a, sizeof(a));
  sort(tmp + 1, tmp + n + 1);
  for (int i = 1; i <= n; i++)
    a[i] = lower_bound(tmp + 1, tmp + n + 1, a[i]) - tmp;
}
void add(int x) {
  now.set(x + cnt[x]);
  cnt[x]++;
}
void del(int x) {
  cnt[x]--;
  now.reset(x + cnt[x]);
}
void solve() {
  int cnt = 0, tot = 0;
  now.reset();
  for (tot = 0; tot < M - 5 && m; tot++) {
    m--;
    ans[tot] = 0;
    sum[tot].set();
    for (int j = 0; j < 3; j++) {
      scanf("%d%d", &q[cnt].l, &q[cnt].r);
      q[cnt].id = tot;
      ans[tot] += q[cnt].r - q[cnt].l + 1;
      cnt++;
    }
  }
  sort(q, q + cnt);
  for (int i = 0, l = 1, r = 0; i < cnt; i++) {
    while (l > q[i].l) add(a[--l]);
    while (r < q[i].r) add(a[++r]);
    while (l < q[i].l) del(a[l++]);
    while (r > q[i].r) del(a[r--]);
    sum[q[i].id] &= now;
  }
  for (int i = 0; i < tot; i++)
    printf("%d\n", ans[i] - (int)sum[i].count() * 3);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  static_set();
  maxn = sqrt(n);
  solve();
  memset(cnt, 0, sizeof(cnt));
  solve();
  memset(cnt, 0, sizeof(cnt));
  solve();
  return 0;
}

「Ynoi2017」由乃的玉米田

这1e51e5 的数据量，对于以前的我来说完完全全就是一道不可做题…

考虑用bitset来优化复杂度。定义 bitset<maxn>s1,s2 ，假如 s1 某项为 11，即代表该下标对应的值在区间中出现过。于是我们可以很容易知道，对于区间中任意一个元素 ii，只要 s1[i+x]==1s1[i+x]==1 或 s1[i−x]==1s1[i-x]==1，则满足有两数的差为 xx。

那么如何判断和为 xx 的情况呢？由于我们的 s2 是倒着存的，对于对于区间中任意一个元素 ii，只要 s1[i]&s2[i]=1s1[i]\& s2[i]=1，即表明存在两元素和为 maxnmaxn。当我们把s2s2 整体右移 maxn−xmaxn-x 时，若s1[i]&s2[i]=1s1[i]\& s2[i]=1,则表明存在两元素和为 xx。

对于乘积为 xx 的情况，如果存在合法解，一定有一个元素小于 x\sqrt{x} ，故只需要暴力枚举即可

对于商为 xx 的情况，我们分情况讨论

  • 假如 x≥nx\geq\sqrt{n}，直接暴力枚举判断
  • 假如 x<nx<\sqrt{n}，则不借助通过莫队处理得到的s1,s2s1,s2，而是使用事先预处理好的一个 visvis 数组 O(1)O(1) 查询得到答案。这里的 vis[i][j]vis[i][j] 意义为，在下标 ii 之前出现过的包含了两个商为 xx 的元素的最近的左端点；pre[i]pre[i] 表示元素 ii 出现的最近的位置。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m,len,maxx;
int a[maxn];
struct query{
	int opt,l,r,val,id;
	const bool operator< (const query &x)const {
		return l/len!=x.l/len?l<x.l:r<x.r;
	}
}qu[maxn];
int cnt[maxn*2],ans[maxn];
bitset<maxn+5>s1,s2;
int vis[maxn][320],pre[maxn];
void del(int p){
	cnt[a[p]]--;
	if(cnt[a[p]]==0)s1[a[p]]=s2[maxn-a[p]]=0;
}
void add(int p){
	cnt[a[p]]++;
	if(cnt[a[p]]==1)s1[a[p]]=s2[maxn-a[p]]=1;
}
void init(){
	for(int i=1;i<=n;i++){
		pre[a[i]]=i;
		for(int j=1;j<=maxx;j++){
			if(a[i]%j==0)
				vis[i][j]=max(pre[a[i]/j],vis[i][j]);
			if(a[i]*j<maxn)
				vis[i][j]=max(pre[a[i]*j],vis[i][j]);
			vis[i][j]=max(vis[i-1][j],vis[i][j]);
		}
		
	}
}
int main(){
	scanf("%d%d",&n,&m);
	len=sqrt(n+0.5);
	maxx=sqrt(maxn);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	init();
	for(int i=1;i<=m;i++){
		int l,r,opt,val,id=i;
		scanf("%d%d%d%d",&opt,&l,&r,&val);
		qu[i]=(query){opt,l,r,val,id};
	}
	sort(qu+1,qu+m+1);
	int xl,xr;
	xl=xr=0;
	for(int i=1;i<=m;i++){
		while(xl<qu[i].l)del(xl),xl++;
		while(xr>qu[i].r)del(xr),xr--;
		while(xl>qu[i].l)xl--,add(xl);
		while(xr<qu[i].r)xr++,add(xr);
		if(qu[i].opt==1)
			ans[qu[i].id]=((s1>>qu[i].val)&s1).any();
		else if(qu[i].opt==2)
			ans[qu[i].id]=((s2>>(maxn-qu[i].val))&s1).any();
		else if(qu[i].opt==3){
			for(int j=1;j*j<=qu[i].val;j++){
				if(qu[i].val%j)continue;
				if(!s1[qu[i].val/j]||!s1[j])continue;
				ans[qu[i].id]=1;break;
			}
		}
		else {
			if(qu[i].val>=maxx){
				for(int j=1;j*qu[i].val<=maxn;j++){
					if(s1[j]&&s1[j*qu[i].val]){
						ans[qu[i].id]=1;break;
					}
				}
			}
			else 
				if(vis[xr][qu[i].val]>=xl)ans[qu[i].id]=1;
		}
	}
	for(int i=1;i<=m;i++){
		if(ans[i])printf("yuno\n");
		else printf("yumi\n");
	}
	return 0;
}