数据结构——分块扩展\莫队算法
莫队算法（mo’s algorithm）一般分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。当然也有树上莫队，带修改莫队、二维莫队等等。
可参考：莫队算法初探：https://www.luogu.com.cn/blog/codesonic/Mosalgorithm
普通莫队
分析
相信大家已经学过了分块这一数据结构（没学过），其中251.小Z的袜子一题会使用分块算法的一种重要形式——对“询问”进行分块。这是一种用于处理一类不带修改的区间查询问题的离线做法，又被称为“莫队算法”，其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。
如果可以通过区间
[
l
,
r
]
[l,r]
[l,r]快速转移到
[
l
−
1
,
r
]
[
l
+
1
,
r
]
[
l
,
r
−
1
]
[
l
,
r
+
1
]
[l-1,r][l+1,r][l,r-1][l,r+1]
[l−1,r][l+1,r][l,r−1][l,r+1]，那么可以用
O
(
x
×
∣
l
1
−
l
2
∣
+
∣
r
1
−
r
2
∣
)
O(x\times |l1-l2|+|r1-r2|)
O(x×∣l1−l2∣+∣r1−r2∣)的时间完成转移，
[
l
2
,
r
2
]
[l2,r2]
[l2,r2]是
[
l
1
,
r
1
]
[l1,r1]
[l1,r1]的后一次询问，
x
x
x是
[
l
,
r
]
[l,r]
[l,r]转到相邻区间的复杂度
我们让这个值最小，就是求曼哈顿距离最小生成树
我们先假设一个问题，给定一个序列， m m m次询问，每次询问区间 [ l , r ] [l,r] [l,r]有多少种不同的颜色 ( n , m ≤ 100000 ) (n,m\leq 100000) (n,m≤100000)
这一题可以用其他更优算法，但是我们假装没有
先考虑暴力，对每次询问遍历一遍，时间复杂度 O ( n m ) O(nm) O(nm)
换种方式，定义 q l ql ql， q r qr qr表示区间 [ q l , q r ] [ql,qr] [ql,qr]内有多少种颜色，再定义 c n t cnt cnt数组， c n t i cnt_i cnti表示第 i i i种颜色在区间 [ q l , q r ] [ql,qr] [ql,qr]内出现了多少次。
我们一个个询问处理，对于询问 [ l , r ] [l,r] [l,r]，挪动 q l ql ql到 l l l， q r qr qr到 r r r
代码如下：
inline void add(int x)
{
cnt[x]++;
if (cnt[x] == 1) ans++;
}
inline void del(int x)
{
cnt[x]--;
if (cnt[x] == 0) ans--;
}
//获取答案
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--]);
我们发现时间复杂度依然是 O ( n m ) O(nm) O(nm)，现在要想个办法进行加速，因为耗时耗在挪动上，所以我们要想办法减少其挪动次数。
我们将询问先储存下来，再按照某种方法排序，让他减少挪动次数，就是强行离线，然后排序，所以不支持修改。
接下来我们讨论如何排序
我们可以运用分块，将序列分成 n \sqrt n n个长度为 n \sqrt n n的块，优先按照左端点排序，若左端点在同一个块内，则按右端点排序（以左端点所在块的编号为第一关键字排序，右端点的值作为第二关键字排序）
bool cmp(query a, query b)
{
return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r;
}
P2709 小B的询问
传送门
题目分析
裸莫队
如果
c
n
t
i
cnt_i
cnti多一个，
a
n
s
+
=
2
×
c
n
t
[
x
]
−
1
ans+=2\times cnt[x]-1
ans+=2×cnt[x]−1
反之，
a
n
s
−
=
2
×
c
n
t
[
x
]
+
1
ans-=2\times cnt[x]+1
ans−=2×cnt[x]+1
Code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
inline ll read()
{
ll x = 0, f = 1; char c = getchar();
while (c > '9' || c < '0') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
const int maxn = 50050;
int n,m,k;
ll ans,bk;
ll c[maxn],cnt[maxn],answ[maxn];
struct node
{
ll l, r, num;
}mo[maxn];
bool cmp(node a, node b)
{
return (a.r/bk)==(b.r/bk)?a.l<b.l:a.r<b.r;
}
inline void del(int x)
{
cnt[c[x]]--;
ans -= 2 * cnt[c[x]] + 1;
}
inline void add(int x)
{
cnt[c[x]]++;
ans += 2 * cnt[c[x]] - 1;
}
int main()
{
n = read(), m = read(), k = read();
bk = sqrt(n);
for (int i = 1; i <= n; ++i)
c[i] = read();
for (int i = 1; i <= m; ++i)
{
mo[i].l = read(), mo[i].r = read();
mo[i].num = i;
}
sort(mo+1, mo+m+1, cmp);
int l = 1, r = 0;
for (int i = 1; i <= m; ++i)
{
ll ql = mo[i].l, qr = mo[i].r;
while (l < ql) {del(l); l++;}
while (l > ql) {l--; add(l);}
while (r < qr) {r++; add(r);}
while (r > qr) {del(r); r--;}
answ[mo[i].num] = ans;
}
for (int i = 1; i <= m; ++i)
printf("%lld\n",answ[i]);
return 0;
}
251. 小Z的袜子
传送门
题目分析
\quad 以小Z的袜子为例，先把所有询问 [ l , r ] [l,r] [l,r]读入，把这些询问按照左端点递增排序，然后分成 N \sqrt N N块。每块内部再按照右端点排序。
\quad 这样一来，在每一块内部，相邻两个询问的左端点变化在 N \sqrt N N以内，右端点变化是单调的。如果我们以上一次询问的回答为基础，那么每次只需要花费 O ( N ) O(\sqrt N) O(N)的时间处理左端多出或减少的部分。而整块中右端点增长的范围之和为 O ( N ) O(N) O(N)，所以在 O ( N N ) O(N\sqrt N) O(NN)的时间内即可求解本题。
\quad
对于每一块询问，我们先朴素处理该块的第一个询问，得到一个数组
n
u
m
num
num，表示在该块的第一个询问
[
l
,
r
]
[l,r]
[l,r]中，颜色为
c
c
c的袜子有
n
u
m
[
c
]
num[c]
num[c]只。另外，我们在维护一个变量
a
n
s
ans
ans，存储
∑
c
n
u
m
[
c
]
∗
(
n
u
m
[
c
]
−
1
)
2
\frac{\sum_{c}num[c]*(num[c]-1)}{2}
2∑cnum[c]∗(num[c]−1)
然后，我们依次考虑该块的其余询问。当左、右端点发生变化时，朴素地在
n
u
m
num
num中进行增减，同时更新
a
n
s
ans
ans的值。抽到同色袜子的概率就是
a
n
s
C
r
−
l
+
1
2
\frac{ans}{C_{r-l+1}^{2}}
Cr−l+12ans。（源自：算法进阶指南）
Code
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
inline ll read()
{
ll x = 0, f = 1; char c = getchar();
while (c > '9' || c < '0') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
return f * x;
}
const int maxn = 50050;
int n,m;
ll ans,bk;
ll c[maxn],cnt[maxn];
struct node
{
ll l, r, num;
ll a, b;
}mo[maxn];
bool cmp(node a, node b)
{
return (a.r/bk)==(b.r/bk)?a.l<b.l:a.r<b.r;
}
bool CMP(node a, node b)
{
return a.num<b.num;
}
inline void del(ll x)
{
cnt[c[x]]--;//先返回上一状态，再进行ans的相减
ans -= cnt[c[x]];
}
inline void add(ll x)
{
ans += cnt[c[x]];
cnt[c[x]]++;
}
ll gcd(ll a, ll b)
{
return b?gcd(b,a%b):a;
}
int main()
{
n = read(), m = read();
bk = sqrt(n);
for (int i = 1; i <= n; ++i)
c[i] = read();
for (int i = 1; i <= m; ++i)
{
mo[i].l = read(), mo[i].r = read();
mo[i].num = i;
}
sort (mo+1, mo+m+1, cmp);
ll l = 1, r = 0;
for (int i = 1; i <= m; ++i)
{
ll ql = mo[i].l, qr = mo[i].r;
while (l < ql) {del(l); l++;}
while (l > ql) {l--; add(l);}
while (r < qr) {r++; add(r);}
while (r > qr) {del(r); r--;}
mo[i].a = ans;
mo[i].b = (mo[i].r - mo[i].l + 1) * (mo[i].r - mo[i].l) / 2;
if (!ans)//分子为零
{
mo[i].b = 1;
continue;
}
ll gcd1 = gcd(mo[i].a, mo[i].b);//约分
mo[i].a /= gcd1;
mo[i].b /= gcd1;
}
sort (mo+1, mo+m+1, CMP);//按序输出
for (int i = 1; i <= m; ++i)
printf("%lld/%lld\n",mo[i].a,mo[i].b);
return 0;
}