[国家集训队] 小 Z 的袜子
我们来看这种问题。
它们一般会有这样的特征，每次询问区间，支持询问，得到 $[l,r]$ 的答案后，再得到 $[l+1,r]$，$[l,r+1]$，$[l-1,r]$，$[l,r-1]$ 的代价很小，比如说这题就是 $O(1)$ 的。
然后每次我们从一个区间算到另一个区间的代价就是 $\left|l_i-l_{i-1}\right|+\left|r_i-r_{i-1}\right|$ 的。
于是我们很容易有一个想法，就是把每个区间询问转化成二维平面上的点 $(l_i,r_i)$，从一个区间算到另一个区间的代价就是两点间的曼哈顿距离。
那么我们现在的计算最小代价就是这张图上的最短哈密顿路（当然，按某种想法来说不一定需要哈密顿路，最小生成树也是可以的）。
真的去找这个哈密顿路比较困难，所以我们一般就用莫队，或者说分块方法解决这类问题。
可以证明的是，莫队的复杂度和平面最短哈密顿路的数量级下限是相同的（但我并不知道怎么证。。。）。
然后我们来看莫队的想法。
我最开始看到莫队的时候，大概了解到它是一个对询问的顺序进行分块式调整的算法，一下子就有了一种复杂度较劣的方法：
先按左端点排序，块内按右端点排序。然后对于每个块，单独计算第一个询问的答案，然后再从这个答案扩展出块内的其他答案。很容易知道，这个复杂度是 $O((n+m)\sqrt{n})$。
这个复杂度固然相当不错，但并不是真的莫队，因为我们还有更加优秀的方法。
为了方便，我们直接用最短哈密顿路的方法（只计算一个询问的答案，剩下全靠扩展）。
将询问按左端点排序，在序列上分块，左端点在一个块内的再按右端点排序。
设块的大小为 $T$，则块内每次左端点扩展的复杂度都是 $O(T)$ 的，左端点跨过块的扩展复杂度仍然是 $O(T)$ 的，容易想到总的左端点扩展复杂度是 $O(mT)$ 的。
一个块内的询问的右端点是递增的，也就是一个块内的右端点扩展复杂度是 $O(n)$ 的，跨过块扩展的复杂度仍然是 $O(n)$ 的。仍然容易想到，这个右端点扩展的总复杂度是 $O\left(n^2/T\right)$ 的。
于是我们的总复杂度是 $O\left(mT+\dfrac{n^2}{T}\right)$ 的。
根据根号平衡（设上面两项相等列个方程），$T=n/\sqrt{m}$ 的时候最优。
此时我们的复杂度就是 $O(n\sqrt{m})$。
这题具体实现的过程中，我们知道最后的答案是：
$$Ans=\dfrac{\sum_{i=1}^kcnt(i)(cnt(i)-1)}{len(len-1)}$$
其中是假设有 $k$ 种颜色，区间 $[l,r]$ 中颜色为 $i$ 的数量为 $cnt(i)$，$len$ 即为区间 $[l,r]$ 的长度。
意义就是小学组合，我们挑选的方案共有 $len(len-1)$ 种，其中对于颜色 $i$，挑中颜色相同的两个的方案有 $cnt(i)(cnt(i)-1)$。并且我们容易证明每种方案是等概率的。
然后 $O(1)$ 扩展实际上很 Trivial 啊。。。
对于增加一个颜色 $x$：$\Delta=(cnt(x)+1)^2-(cnt(x)+1)-(cnt(x)^2-cnt(x))=2cnt(x)$。
对于减少一个颜色 $x$：$\Delta=(cnt(x)-1)^2-(cnt(x)-1)-(cnt(x)^2-cnt(x))=-2cnt(x)+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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
| #include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
inline void writeln(ll x) {write(x);putchar(10);}
const ll N=5e4,M=1e3;
inline ll gcd(ll a,ll b) {return (b==0)?a:gcd(b,a%b);}
ll n,m,nn,cnt,sum;
ll a[N+5],pos[N+5],col[N+5];
struct Block{ll l,r;}blo[M+5];
struct Qry{
ll l,r,ansmole,ansdeno,id;
}q[N+5];
inline bool Cmp1(Qry x,Qry y) {return x.l<y.l;}
inline bool Cmp2(Qry x,Qry y) {return x.r<y.r;}
inline bool Cmp3(Qry x,Qry y) {return x.r>y.r;}
inline bool Cmp4(Qry x,Qry y) {return x.id<y.id;}
inline void Modify(ll from,ll to,bool op) {
if(from==to) return;
ll type=((from<to)^op);
if(type) {
if(from<to) {
for(ll i=from+1;i<=to;i++) {sum=sum+2*col[a[i]];col[a[i]]++;}
}
else {
for(ll i=from-1;i>=to;i--) {sum=sum+2*col[a[i]];col[a[i]]++;}
}
}
else {
if(from<to) {
for(ll i=from;i<to;i++) {sum=sum-2*col[a[i]]+2;col[a[i]]--;}
}
else {
for(ll i=from;i>to;i--) {sum=sum-2*col[a[i]]+2;col[a[i]]--;}
}
}
}
inline void Println(ll mole,ll deno) {
if(mole==0||deno==0) {printf("0/1\n");return;}
ll k=gcd(mole,deno);
mole/=k;deno/=k;
write(mole);putchar('/');writeln(deno);
}
int main() {
n=read();m=read();
nn=max(1ll,(ll)n/(ll)sqrt(m));
for(ll i=1;i<=n;i++) {a[i]=read();}
cnt=1;
for(ll i=1;i<=n;i+=nn,cnt++) {
blo[cnt].l=i;blo[cnt].r=i+nn-1;if(blo[cnt].r>n) blo[cnt].r=n;
for(ll j=blo[cnt].l;j<=blo[cnt].r;j++) {pos[j]=cnt;}
}
cnt--;
for(ll i=1;i<=m;i++) {q[i].l=read();q[i].r=read();q[i].id=i;}
sort(q+1,q+m+1,Cmp1);
ll lst=1;
for(ll i=1,j=1;j<=cnt;j++) {
while(pos[q[i].l]==j) {
i++;
}
if(j&1) {sort(q+lst,q+i,Cmp2);}
else {sort(q+lst,q+i,Cmp3);}
lst=i;
}
ll lit=1,rit=1;col[a[1]]++;
for(ll i=1;i<=m;i++) {
Modify(rit,q[i].r,0);rit=q[i].r;
Modify(lit,q[i].l,1);lit=q[i].l;
ll len=q[i].r-q[i].l+1;
q[i].ansmole=sum;q[i].ansdeno=len*(len-1);
}
sort(q+1,q+m+1,Cmp4);
for(ll i=1;i<=m;i++) {Println(q[i].ansmole,q[i].ansdeno);}
return 0;
}
|