莫队

参考文章：

莫队细讲——从零开始学莫队

莫队算法——从入门到黑题

oiwiki--普通莫队

莫队简介

莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。

莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。

普通莫队算法

形式

假设 \(n = m\)，那么对于序列上的区间询问问题，如果从 \([l, r]\) 的答案能够 \(O(1)\) 扩展到 \([l-1, r]\), \([l+1, r]\), \([l, r+1]\), \([l, r-1]\)（即与 \([l, r]\) 相邻的区间）的答案，那么可以在 \(O(n\sqrt{n})\) 的复杂度内求出所有询问的答案。

解释

离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步一步移动即可）。

排序方法

对于区间 \([l, r]\), 以 \(l\) 所在块的编号为第一关键字，\(r\) 为第二关键字从小到大排序。

略.......

直接上题目

P1494 [国家集训队] 小 Z 的袜子

[国家集训队] 小 Z 的袜子

题目描述

upd on 2020.6.10 ：更新了时限。

作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小 Z 把这 \(N\) 只袜子从 \(1\) 到 \(N\) 编号，然后从编号 \(L\) 到 \(R\) 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 \((L,R)\) 以方便自己选择。

然而数据中有 \(L=R\) 的情况，请特判这种情况，输出<code>0/1。

输入格式

输入文件第一行包含两个正整数 \(N\) 和 \(M\)。\(N\) 为袜子的数量，\(M\) 为小 Z 所提的询问的数量。接下来一行包含 \(N\) 个正整数 \(C_i\)，其中 \(C_i\) 表示第 \(i\) 只袜子的颜色，相同的颜色用相同的数字表示。再接下来 \(M\) 行，每行两个正整数 \(L, R\) 表示一个询问。

输出格式

包含 \(M\) 行，对于每个询问在一行中输出分数 \(A/B\) 表示从该询问的区间 \([L,R]\) 中随机抽出两只袜子颜色相同的概率。若该概率为 \(0\) 则输出 0/1，否则输出的 \(A/B\) 必须为最简分数。（详见样例）

样例 #1

样例输入 #1

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

样例输出 #1

2/5

0/1

1/1

4/15

提示

\(30\%\) 的数据中，\(N,M\leq 5000\)；

\(60\%\) 的数据中，\(N,M \leq 25000\)；

\(100\%\) 的数据中，\(N,M \leq 50000\)，\(1 \leq L \leq R \leq N\)，\(C_i \leq N\)。

AC代码：

#include<bits/stdc++.h>

#define int long long

#define debug() cout<<"----------debug-------------"

using namespace std;

const int N = 500010; // 定义数组最大大小

int n, q; // n 是数组大小，q 是查询数量

int c[N]; // 存储输入数组

array<int, 3> que[N]; // 存储查询的数组，每个查询是一个三元组 {l, r, i}

int B = 750; // 分块的大小

int ans[N]; // 存储每个查询的结果

int tmp = 0; // 临时变量，用于计算当前区间内不同元素对的个数

int ans2[N]; // 记录每个查询的分母

int cnt[N]; // 记录每个数出现的次数

signed main() {

ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 加速输入输出

cin >> n >> q; // 读取数组大小和查询数量

for (int i = 1; i <= n; i++)

cin >> c[i]; // 读取数组元素

for (int i = 0; i < q; i++) {

int l, r;

cin >> l >> r; // 读取每个查询的区间 [l, r]

que[i] = {l, r, i}; // 存储查询

ans2[i] = (r - l) * (r - l + 1) / 2; // 计算分母

}

// 按照莫队算法的分块策略对查询进行排序

sort(que, que + q, [&](array<int, 3> a, array<int, 3> b) {

int d = a[0] / B;

if (a[0] / B != b[0] / B) return a[0] / B < b[0] / B;

//if (d % 2 == 1) return a[1] < b[1];

//else return a[1] > b[1];

return a[1]<b[1];

});

int l = 1, r = 0; // 初始化指针 l 和 r

// 添加元素时更新 tmp 和 cnt

auto add = [&](int x) {

tmp += cnt[c[x]];

cnt[c[x]]++;

};

// 删除元素时更新 tmp 和 cnt

auto del = [&](int x) {

cnt[c[x]]--;

tmp -= cnt[c[x]];

};

// 遍历每个查询，通过移动指针 l 和 r 来处理区间

for (int i = 0; i < q; i++) {

if (que[i][1] == que[i][0]) { // 如果查询区间长度为 0

ans[que[i][2]] = 0;

continue;

}

while (r < que[i][1]) r++, add(r); // 扩展右边界

while (l > que[i][0]) l--, add(l); // 扩展左边界

while (r > que[i][1]) del(r), r--; // 收缩右边界

while (l < que[i][0]) del(l), l++; // 收缩左边界

ans[que[i][2]] = tmp; // 记录当前查询的结果

}

// 输出每个查询的结果

for (int i = 0; i < q; i++) {

if (ans2[i] == 0 && ans[i] == 0) { // 如果分子和分母都为 0

cout << "0/1" << endl;

continue;

}

int d = __gcd(ans[i], ans2[i]); // 计算最大公约数

cout << ans[i] / d << "/" << ans2[i] / d << endl; // 输出结果

}

return 0;

}

优化：

过程

我们看一下下面这组数据

// 设块的大小为 2 (假设)

1 1

2 100

3 1

4 100

手动模拟一下可以发现，r 指针的移动次数大概为 300 次，我们处理完第一个块之后，\(l = 2, r = 100\)，此时只需要移动两次 l 指针就可以得到第四个询问的答案，但是我们却将 r 指针移动到 1 来获取第三个询问的答案，再移动到 100 获取第四个询问的答案，这样多了九十几次的指针移动。我们怎么优化这个地方呢？这里我们就要用到奇偶化排序。

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

// 按照莫队算法的分块策略对查询进行排序

sort(que, que + q, [&](array<int, 3> a, array<int, 3> b) {

int d = a[0] / B;

if (a[0] / B != b[0] / B) return a[0] / B < b[0] / B;

if (d % 2 == 1) return a[1] < b[1];

else return a[1] > b[1];

});

根号分治

根号分治，是暴力美学的集大成体现。与其说是一种算法，我们不如称它为一个常用的trick。

题目引入

首先，我们引入一道入门题目 CF1207F Remainder Problem：

给你一个长度为 \(5×10^5\) 的序列，初值为 \(0\)，你要完成 \(q\) 次操作，操作有如下两种：

1. 1 x y: 将下标为 \(x\) 的位置的值加上 \(y\)。
2. 2 x y: 询问所有下标模 \(x\) 的结果为 \(y\) 的位置的值之和。

暴力解法

暴力1

首先有一种暴力就是按照题目所说的去做，开一个 \(5×10^5\) 大小的数组 \(a\) 去存，\(1\) 操作就对 \(a[x]\) 加上 \(y\)，\(2\) 操作就枚举所有下标模 \(x\) 的结果为 \(y\) 的位置，统计他们的和。

对于这种暴力，\(1\) 操作的时间复杂度为 \(O(1)\)，\(2\) 操作的时间复杂度为 \(O(n)\)，所以在最坏情况下总时间复杂度可达 \(O(nq)\)。

暴力2

经过思考，我们可以发现另外一种暴力：新开一个大小为 \(n×n\) 的二维数组 \(b\)，\(b[i][j]\) 当前所有下标模 \(i\) 的结果为 \(j\) 的数的和是什么。对于每个 \(1\) 操作，动态的去维护这个 \(b\) 数组，在每次询问的时候直接输出答案即可。

对于这种暴力，\(1\) 操作的时间复杂度是枚举模数的 \(O(n)\)，\(2\) 操作的时间复杂度为 \(O(1)\)，总的时间复杂度为 \(O(nq)\)。

根号分治策略

现在我们发现，这两种暴力对应了两种极端：一个是 \(1\) 操作的时间复杂度为 \(O(1)\)，2 操作的时间复杂度为 \(O(n)\)；另一个是 \(1\) 操作的时间复杂度是枚举模数的 \(O(n)\)，2 操作的时间复杂度为 \(O(1)\)。那么，有没有办法让这两种暴力融合一下，均摊时间复杂度，达到一个平衡呢？

其实是有的。我们设定一个阈值 \(b\)。

对于所有 \(≤b\) 的数，我们动态的维护暴力 \(2\) 的 \(b\) 数组。每次 \(1\) 操作只需要枚举 \(b\) 个模数即可，故单次操作 \(1\) 的时间复杂度降为 \(O(b)\)。

对于所有 \(>b\) 的数，我们就不在操作 \(1\) 中维护 \(b\)，直接再询问答案时暴力枚举下标即可。显然，这 \(n\) 个下标中最多有 \(⌈n/b⌉\) 个下标对 \(x\) 取模余 \(y\) 找到第一个 \(y\) 后每次跳 \(x\)，即可做到单次操作 \(2\) 时间复杂度为 \(O(n\sqrt{b})\)。

所以，总时间复杂度就成为了 \(O(q×(b+n\sqrt{b}))\)。由基本不等式可得，\(b+n/b≥2√(b×n/b)=2√n\)，当 \(b=\sqrt{n}\) 时取等。所以我们只需要让 \(b=\sqrt{n}\)，就可以做到时间和空间复杂度均为\(O(q\sqrt{n})\) 的优秀算法了，可以通过此题。

代码：

#include<bits/stdc++.h>

#define endl "\n"

using namespace std;

const int N=5e5+30,mod=998244353;

typedef long long ll;

typedef pair<int,int> PII;

int n,m;

int q;

const int B=750;

int ans[B+10][B+10];

int a[N];

void solve()

{

cin>>q;

while(q--)

{

int id,x,y;

cin>>id>>x>>y;

if(id==1)

{

for(int i=1;i<=B;i++) ans[i][x%i]+=y;

a[x]+=y;

}

else

{

if(x<=B) cout<<ans[x][y]<<endl;

else

{

int temp=0;

for(int i=y;i<=500000;i+=x)

{

temp+=a[i];

}

cout<<temp<<endl;

}

}

}

}

signed main()

{

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int _;

_=1;

//cin>>T;

while(_--)

{

solve();

}

return 0;

}