莫队
莫队
对于一个维护区间[L,R]，若能在O(1)复杂度内得到 [L-1,R]，[L+1,R]，[L,R-1]，[L+1]中的任意一种，就可以用使用莫队。
比如要维护一个区间内不同元素的个数。
用一个数组cnt[i]来表示区间内i出现的次数,sum,这样当cnt[i]==0时就
sum--,cnt[i] == 1就sum++。
这个是用朴素的双指针，但是如果有$n$个数，$m$个查询，最坏情况下有 $O(nm)$的时间复杂度。
如果能减少左右指针移动的次数就好了qwq。
莫队就是用了分块，先把所有的查询离线，分块，然后排序，排序的第一个关键字是 查询的块的编号，第二个关键字是查询的右区间。
下面讨论算法的时间复杂度：
- 左指针
每次查询最多移动一个块的长度 * 总共查询$m$次 + 所有块最多移动$2*n$次（最糟情况每前进一个块移动两个块的长度）
时间复杂度： O(m*块长)
- 右指针 每个块最多移动$n$(单调) + 每次换块时最多移动$n$
时间复杂度： O(n*块数)
那什么时候时间复杂度最优？ 块长为B, 那么块的数量为 $n/B$
左： $O(mB)$
右： $O(nn/B)$
总共: $O(mB + n\frac{n}{B})$
为双钩函数，当B取$\sqrt{\frac{n^2}{m}}$ 即 $\frac{n}{\sqrt{m}}$时时间复杂度最优
eg.
小 Z 的袜子
作为一个生活散漫的人，小 Z 每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小 Z 再也无法忍受这恼人的找袜子过程，于是他决定听天由命……
具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ 的袜子中随机选出两只来穿。尽管小 Z 并不在意两只袜子是不是完整的一双，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小 Z，他有多大的概率抽到两只颜色相同的袜子。当然，小 Z 希望这个概率尽量高，所以他可能会询问多个 $(L,R)$ 以方便自己选择。
然而数据中有 $L=R$ 的情况，请特判这种情况，输出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$。
用莫队，设当前的区间为len,如果区间增加，len * (len - 1) / 2，变成(len + 1) * len, 增加len。 分子，设在x变化，add : 增减cnt_x
#include <bits/stdc++.h>
#include <cmath>
#include <vector>
using namespace std;
using ll = long long;
// #define int ll
int gcd(int a, int b) {
return (b == 0 ? a : gcd(b, a % b));
}
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int B = n / sqrt(m);
struct Node {
int l, r, id, num;
bool operator<(Node& b) {
return (num == b.num ? r < b.r : num < b.num);
}
};
vector<Node> q(m + 1);
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
q[i].id = i;
q[i].num = q[i].l / B;
}
sort(q.begin() + 1, q.end());
int l = 1, r = 0;
int len = 0;
int fz = 0, fm = 0;
vector<int> cnt(n + 1, 0);
auto add = [&](int loc) {
fm += len;
len++;
fz += cnt[a[loc]];
cnt[a[loc]]++;
};
auto del = [&](int loc) {
len--;
fm -= len;
cnt[a[loc]]--;
fz -= cnt[a[loc]];
};
vector<pair<int, int>> ans(m + 1);
for (int i = 1; i <= m; i++) {
if (q[i].l == q[i].r) {
ans[q[i].id].first = 0;
ans[q[i].id].second = 1;
continue;
}
while (l < q[i].l) {
del(l++);
}
while (l > q[i].l) {
add(--l);
}
while (r < q[i].r) {
add(++r);
}
while (r > q[i].r) {
del(r--);
}
int g = gcd(fz, fm);
ans[q[i].id].first = fz / g;
ans[q[i].id].second = fm / g;
}
for (int i = 1; i <= m; i++) {
cout << ans[i].first << '/' << ans[i].second << '\n';
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
/**
* created: 2025-01-30 03:00
**/