莫队算法:?
其核心思维就是对于 区间查询 操作，通过对所有 “被询问的区间进行” 合理的排序 ，然后通过 暴力移动区间的左右端点 并 快速更新答案 得到所有询问的结果。
-----摘自这里?
题目链接：小Z的袜子?
细节问题这里不诉说了，下面来证明一下如何计算时间复杂度以及为何这样最优。
??
对于这一问题的证明如下：
?t取时：
t取时：
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
long long a[N];
long long n,m,t;
int L[N],R[N];
long long c[N];
struct node
{
long long l,r,p,f,id,ans;
}p[N];
bool cmp1(node a,node b){return a.l < b.l;}
bool cmp2(node a,node b){ return a.r < b.r;}
bool cmp3(node a,node b){return a.id < b.id;}
long long ans = 0;
void init()
{
long long w= pow(n,1.0/2.0);
for(long long i=1;i<=m;i+=w)
{
L[++t]=i,R[t]=min(m,i+w-1ll);
//pos[j]=t;
}
// sort(e+1,e+m+1,cmp1);
for(int i=1;i<=t;i++)
sort(p+L[i],p+R[i]+ 1,cmp2);
}
void add(int x)
{
ans -= c[x]* max(c[x] - 1ll,0ll)/2;c[x]++;
ans += c[x]* max(c[x] - 1ll,0ll)/2;
}
void dec(int x)
{
ans -= c[x]* max(c[x] - 1ll,0ll)/2;c[x]--;
ans += c[x]* max(c[x] - 1ll,0ll)/2;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n ; i++) cin >> a[i];
for(int i = 1 ; i <= m ; i++) {cin >> p[i].l >> p[i].r; p[i].id = i; p[i].p = (p[i].r - p[i].l + 1ll)*(p[i].r - p[i].l) >> 1;}
sort(p + 1,p + 1 + m,cmp1);
// for(int i = 1; i <= m ; i++) cout << p[i].l <<" " <<p[i].r <<endl;
init();
// for(int i = 1; i <= m ; i++) cout << p[i].l <<"az" <<p[i].r <<endl;
for(int i = 1,l = 0 , r = 0; i <= m ; i++)
{
while(l<p[i].l)dec(a[++l]);
while(l>=p[i].l)add(a[l--]);
while(r<p[i].r)add(a[++r]);
while(r>p[i].r)dec(a[r--]);
if(ans == 0) p[i].f = 0,p[i].p = 1;
else
{
p[i].f = ans;
long long g = __gcd(ans,p[i].p);
p[i].f /= g;
p[i].p /= g;
}
}
sort(p + 1,p + 1 + m,cmp3);
for(int i = 1 ; i <= m ; i++)
{
if(p[i].f == 0 && p[i].p == 1) cout <<"0/1" << endl;
else cout << p[i].f <<"/" << p[i].p << endl;
}
}如有错误欢迎指正！?