莫队算法

把所有询问按左端点分块，块的大小是 $T = \sqrt{n}$
在同一块里的所有询问，按右端点排序
这样的话，假设块内有 $q$ ，处理一块内的所有询问，需要的时间是 $q T + n$
一共会有 $n / T$ 块，总询问数是 $m$
总时间复杂度是 $m T + n \times \frac{n}{T}$
理论最优解 $T = \frac{n}{\sqrt{m}}$
实际最优解，可以试一试 $2T$ 或 $\frac{T}{2}$

参考题目

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

https://www.luogu.com.cn/problem/P1494

题目描述

upd on 2020.6.10 ：更新了时限。

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

具体来说，小 Z 把这 $N$ 只袜子从 $1$ 到 $N$ 编号，然后从编号 $L$ 到 $R$ ( $L$ 尽管小 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 < R \leq N$ ， $C_i \leq N$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int b = 237;
int n, m;
int a[50020];
int c[50020];
int l[50020];
int r[50020];
int o[50020];
int x[50020];
int y[50020];
int z;
void inc(int x)
{
	z += c[x]++;
}
void dec(int x)
{
	z -= --c[x];
}
bool cmp(int x, int y)
{
	if (l[x] / b == l[y] / b)
	{
		return r[x] < r[y];
	}
	else
	{
		return l[x] < l[y];
	}
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &l[i], &r[i]);
		o[i] = i;
	}
	sort(o, o + m, cmp);
	for (int i = 0, L = 2, R = 1; i < m; i++)
	{
		while (L > l[o[i]])
		{
			inc(a[--L]);
		}
		while (R < r[o[i]])
		{
			inc(a[++R]);
		}
		while (L < l[o[i]])
		{
			dec(a[L++]);
		}
		while (R > r[o[i]])
		{
			dec(a[R--]);
		}
		if (l[o[i]] == r[o[i]])
		{
			x[o[i]] = 0;
			y[o[i]] = 1;
		}
		else
		{
			x[o[i]] = z;
			y[o[i]] = (r[o[i]] - l[o[i]] + 1LL) * (r[o[i]] - l[o[i]]) / 2;
			int g = __gcd(x[o[i]], y[o[i]]);
			x[o[i]] /= g;
			y[o[i]] /= g;
		}
	}
	for (int i = 0; i < m; i++)
	{
		printf("%d/%d\n", x[i], y[i]);
	}
	return 0;
}

题解

abc242_g Range Pairing Query

https://atcoder.jp/contests/abc242/tasks/abc242_g

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, q;
int a[1000020];
int c[1000020];
int l[1000020];
int r[1000020];
int o[1000020];
int z[1000020];
bool cmp(int x, int y)
{
	return make_pair(l[x] / 1000, r[x]) < make_pair(l[y] / 1000, r[y]);
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> l[i] >> r[i];
		o[i] = i;
	}
	sort(o, o + m, cmp);
	int L = 0, R = -1, p = 0;
	for (int i = 0; i < m; i++)
	{
		while (L < l[o[i]])
		{
			p -= --c[a[L++]] & 1;
		}
		while (l[o[i]] < L)
		{
			p += c[a[--L]]++ & 1;
		}
		while (R < r[o[i]])
		{
			p += c[a[++R]]++ & 1;
		}
		while (r[o[i]] < R)
		{
			p -= --c[a[R--]] & 1;
		}
		z[o[i]] = p;
	}
	for (int i = 0; i < m; i++)
	{
		cout << z[i] << endl;
	}
	return 0;
}

题解

1 2 3 3 3 2
2 6
1 3

已知 2 到 6 的区间，对数是4，每种数字出现的次数是 c[2]=3 c[3]=2
在这个区间内，加入1，删去2，删去3，问操作之后
对数是什么？
加入1，对数+=0
删去2，对数-=2
删去3，对数-=1
最后对数=1
每种数字出现的次数是？c[1]=1 c[2]=2 c[3]=1

spoj ADANUM

已知
1 出现了5次
2 出现了2次
3 出现了4次
如何计算答案
出现次数多的标的数字比较小
5次的标成1
4次的标成2
2次的标成3
5*1 + 4*2 + 2*3 = 19

再出现了一次3，答案怎么变
5*1 + 5*2 + 2*3 = 21

再出现了一次3，答案怎么变
6*1 + 5*2 + 2*3 = 22

c[x] 表示数字 x 出现了几次
d[x] 表示有多少种数字出现的次数 >= x