BZOJ

BZOJ 2038

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

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

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

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

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

现在假设这个区间[l,r]里有两种颜色的袜子，分别有a和b只，那么取法*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.