BZOJ - 2038 小Z的袜子

Posted on | In ,

思路

莫队算法

莫队算法是一种解决一系列无修改的区间查询问题的算法。对于区间查询问题，我们通常使用线段树。但是考虑这样一个问题：对[l,r]区间内的计算至少重复三次数的个数。这样的问题如果使用线段树需要在节点上维护区间内数字的个数，而这样维护显然并不能在O(1)完成，因而我们常常使用莫队算法。莫队算法的使用条件是我们可以O(1)时间内通过已知的[l,r]答案得到[l-1,r],[l+1,r],[l,r+1],[l,r-1]的答案，并且我们能够离线询问。通过对询问排序，我们利用O(1)的转移能够以一个较为满意的复杂度解决这个问题(避免重复扫描数列）。这个问题可以使用曼哈顿距离最小生成树来写，但这样写代码似乎太麻烦了些，所以我们使用分块。我们以询问左端点所在的分块的序号为第一关键字，右端点的大小为第二关键字。

莫队算法时间复杂度

分块相同时，右端点递增是O(N)的，分块共有O(sqrt(N)) )个，复杂度为O(N^(1.5))
分块转移时，右端点最多变化N，分块共有O(sqrt(N) )个，复杂度为O(N^(1.5)
分块相同时，左端点最多变化sqrt(N) ，分块转移时，左端点最多变化2sqrt(N) ，共有N个询问，复杂度为O(N^(1.5) )
所有总时间复杂度就是O(N^1.5)

参考

莫队算法 (Mo’s Algorithm)
莫队算法

本题思路

莫队模板题。令当前可选的袜子为ans
ans=(color[i]*(color[i]-1)/2);
化简得到ans=(Σ(sum(color[i])2)−(R−L+1))/((R−L+1)∗(R−L))
所以更新为ans=ans-ci^2+(ci+1)^2

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#include <complex>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)
#define sqr(x) ((x)*(x))
#pragma warning(disable:4996)

using namespace std;
const int N = 50005;
ll n, m,color[N],a[N],pos[N],ans;
ll gcd(ll a, ll b) {
	return a%b == 0 ? b : gcd(b, a%b);
}
struct query {
	ll left, right, id, ans1,ans2;
}Q[N];
bool cmp(query q1, query q2) {
	if (pos[q1.left] == pos[q2.left])return q1.right < q2.right;
	else return q1.left < q2.left;
}
bool cmp_id(query q1, query q2) {
	return q1.id < q2.id;
}
void update(ll pos,ll add) {
	ans -= sqr(color[a[pos]]);
	color[a[pos]] += add;
	ans += sqr(color[a[pos]]);
}
void solve() {
	ll left = 1, right = 0;
	for (ll i = 0;i < m;i++) {
		while (left < Q[i].left) {
			update(left, -1);
			left++;
		}
		while (left > Q[i].left) {
			update(left-1, 1);
			left--;
		}
		while (right < Q[i].right) {
			update(right+1, 1);	
			right++;
		}
		while (right > Q[i].right) {
			update(right, -1);
			right--;
		}
		if (Q[i].left==Q[i].right)Q[i].ans1 = 0, Q[i].ans2 = 1;
		else {
			Q[i].ans1 = ans - (right - left + 1);
			Q[i].ans2 = (right - left + 1)*(right - left);
			ll g = gcd(Q[i].ans1, Q[i].ans2);
			Q[i].ans1 = Q[i].ans1 / g, Q[i].ans2 = Q[i].ans2 / g;
		}
	}
}
int main() {
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while (scanf("%lld%lld",&n,&m)!=EOF) {
		ans = 0;
		for (ll i = 1;i <= n;i++)scanf("%lld", &a[i]);
		for (ll i = 0;i < m;i++) {
			scanf("%lld%lld", &Q[i].left, &Q[i].right);
			Q[i].id = i;
		}
		ll block = (ll)sqrt(n);//分块
		for (ll i = 1;i <= n;i++) pos[i] = (i-1) / block+1;
		sort(Q, Q + m, cmp);
		solve();
		sort(Q, Q + m, cmp_id);
		for (ll i = 0;i < m;i++) {
			printf("%lld/%lld\n", Q[i].ans1, Q[i].ans2);
		}
	}
	return 0;
}