# 1. 普通莫队算法

##### 模板
int l = 0, r = 0, nowAns = 0;

inline void move(int pos, int sign) {
// update nowAns
}

void solve() {
BLOCK_SIZE = int(ceil(pow(n, 0.5)));
sort(querys, querys + m);
for (int i = 0; i < m; ++i) {
const query &q = querys[i];
while (l > q.l) move(--l, 1);
while (r < q.r) move(r++, 1);
while (l < q.l) move(l++, -1);
while (r > q.r) move(--r, -1);
ans[q.id] = nowAns;
}
}

##### 复杂度分析

\begin{aligned} & O(\sqrt{n}(\max{} _ 1-1)+\sqrt{n}(\max{} _ 2-\max{} _ 1)+\sqrt{n}(\max{} _ 3-\max{} _ 2)+\cdots+\sqrt{n}(\max{} _ {\lceil\sqrt{n}\rceil}-\max{} _ {\lceil\sqrt{n}\rceil-1))} \\ = & O(\sqrt{n}\cdot(\max{} _ 1-1+\max{} _ 2-\max{} _ 1+\max{} _ 3-\max{} _ 2+\cdots+\max{} _ {\lceil\sqrt{n}\rceil-1}-\max{} _ {\lceil\sqrt{n}\rceil-2}+\max{} _ {\lceil\sqrt{n}\rceil}-\max{} _ {\lceil\sqrt{n}\rceil-1)}) \\ = & O(\sqrt{n}\cdot(\max{} _ {\lceil\sqrt{n}\rceil-1}))\\ \end{aligned}

（裂项求和）

# 2. 例题&代码

### 小 Z 的袜子

$C(a,2)$=$a\times (a-1)/2$

#include <bits/stdc++.h>
#define bi(a) ((a - 1) / sqn + 1)
using namespace std;
typedef long long LL;
template <typename tp>
char c = getchar();
dig = 0;
while (!isdigit(c)) c = getchar();
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}
struct node {
LL l, r, i;
};
LL n, m, sqn, arr[50005], l, r, ans, col[50005], sub[50005], mot[50005];
vector<node> tab;
bool cmp(node a, node b) {
if (bi(a.l) == bi(b.l)) return a.r < b.r;
return a.l < b.l;
}
LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
int main() {
for (LL i = 1; i <= n; i++) read(arr[i]);
for (LL i = 1, a, b; i <= m; i++)
sort(tab.begin(), tab.end(), cmp), l = r = tab[0].l, col[arr[l]]++;
for (LL i = 0, gcdnum; i < tab.size(); i++) {
for (; l < tab[i].l; l++) col[arr[l]]--, ans -= col[arr[l]];
for (--l; l >= tab[i].l; l--) ans += col[arr[l]], col[arr[l]]++;
for (; r > tab[i].r; r--) col[arr[r]]--, ans -= col[arr[r]];
for (++r; r <= tab[i].r; r++) ans += col[arr[r]], col[arr[r]]++;
sub[tab[i].i] = ans, l = tab[i].l, r = tab[i].r;
mot[tab[i].i] = ((r - l) * (r - l + 1)) >> 1;
}
for (LL i = 1, gcdn; i <= m; i++)
gcdn = gcd(sub[i], mot[i]),
printf("%lld/%lld\n", sub[i] / gcdn, mot[i] / gcdn);
return 0;
}


[…] 普通莫队算法教程 […]