BZOJ 2038

莫队大法好

能使用莫队算法的条件是:

已知[l,r]的答案,能在O(1)(或O(logn)等较低的时间复杂度)的时间内求得[l+1,r][l,r-1]的答案 ——by hzwer

那么我们观察这道题,假设一个区间[l,r]内有m只相同颜色的袜子 怎么觉得好恶心…,那么满足条件的取法有$C^2_m$种

而$C^2_m=\frac{m(m-1)}{2}$

整理一下,得$2C^2_m=m^2-m$

现在假设这个区间[l,r]里有两种颜色的袜子,分别有ab只,那么取法*2共有$a^2+b^2-a-b$种(把这数放在分子上看起来太小,所以就直接换成取法*2了)

三种颜色的取法*2就是$a^2+b^2+c^2-a-b-c$种,发现这些式子对于某种颜色只有一只时也同样成立

所以得到取法总数*2为$\sum_{i=1}^{colors}=colortot[i]^2-colortot[i]$(colors是区间内颜色的数目,colortot是每种颜色的袜子数),注意到后面那一坨的和就是区间里所有袜子的数

所以得到取法种数*2即为$\sum_{i=1}^{colors}-(r-l+1)=colortot[i]^2-(r-l+1)$

这样就得出了计算区间[l,r]内取法的方法,可以考虑上莫队了

分为$\sqrt{n}$块,对其进行排序,目标是使所有左端点在一个块内的询问的右端点是递增的,举个栗子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
n=6 m=15
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6

分块大小为每块2个,排序后变成了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
1 2
2 3
1 3
2 4
1 4
1 5
2 5
2 6
1 6
1 7
---以上为第一块,右端点为递增的
3 4
4 5
3 5
4 6
3 6
---第二块

这样的话转移时就能省很多时间

初始时区间为[1,0],然后依次向每个询问进行转移,依据上面的公式,只需要维护一个变量表示当前区间内每种颜色数量的平方和,这个变量减掉区间内元素个数就是答案

分母就不用多说了吧,就是$C^2_{r-l+1}=\frac{(r-l+1)(r-l)}{2}$,发现分母分子都有$/2$,直接扔掉,然后用gcd化简一下就是答案

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
97
98
99
program bzoj_2038;
type q=record l,r,id:longint; mom,son:int64; end;
var c,bl,cnt,pos:array[1..50000]of longint;
tot:int64;
n,m,i,block:longint;
ask:array[1..50000]of q;
function gcd(a,b:int64):int64;
begin
if b=0 then exit(a) else exit(gcd(b,a mod b));
end;
function sml(a,b:q):boolean;
begin
if bl[a.l]=bl[b.l] then exit(a.r<b.r);
exit(a.l<b.l);
end;
procedure qsort(l,r:longint);
var i,j:longint;
mid,p:q;
begin
i:=l;
j:=r;
mid:=ask[(l+r)>>1];
repeat
while sml(ask[i],mid) do inc(i);
while sml(mid,ask[j]) do dec(j);
if i<=j then
begin
p:=ask[i];
ask[i]:=ask[j];
ask[j]:=p;
inc(i);
dec(j);
end;
until i>j;
if i<r then qsort(i,r);
if l<j then qsort(l,j);
end;
procedure modify(l,r,delta:longint);
var i:longint;
begin
for i:=l to r do
begin
dec(tot,sqr(cnt[c[i]]));
inc(cnt[c[i]],delta);
inc(tot,sqr(cnt[c[i]]));
end;
end;
procedure solve;
var i,l,r:longint;
g:int64;
begin
l:=1;
r:=0;
tot:=0;
for i:=1 to m do
begin
if l<ask[i].l then modify(l,ask[i].l-1,-1);
if l>ask[i].l then modify(ask[i].l,l-1,1);
if r<ask[i].r then modify(r+1,ask[i].r,1);
if r>ask[i].r then modify(ask[i].r+1,r,-1);
l:=ask[i].l;
r:=ask[i].r;
with ask[i] do
begin
if l=r then
begin
son:=0;
mom:=1;
continue;
end;
son:=tot-(r-l+1);
mom:=int64(r-l+1)*int64(r-l);
g:=gcd(mom,son);
son:=son div g;
mom:=mom div g;
end;
end;
end;
begin
readln(n,m);
block:=trunc(sqrt(n));
for i:=1 to n do bl[i]:=(i-1)div block+1;
for i:=1 to n do read(c[i]);
for i:=1 to m do with ask[i] do
begin
readln(l,r);
id:=i;
end;
qsort(1,m);
for i:=1 to m do pos[ask[i].id]:=i;
solve;
for i:=1 to m do with ask[pos[i]] do writeln(son,'/',mom);
end.

mathjax好难 >_<