沉迷于文化的我N年没更blog了。。。（\(N \in (0,1)\)）

然后回到机房就沉迷于 \(generals.io\) 无法自拔。。。QAQ

然后想打一遍splay（然后是LCT），然后放弃了。。。QAQ

只好学一学\(Brother Zi Duck\)巨佬早学过的莫队辣

%%%GZY

hzwer说的很清楚了qwq以下复述一遍

先蒯一点：

如果我们已知[l,r]的答案，能在O(1)时间得到[l+1,r]的答案以及[l,r-1]的答案，即可使用莫队算法。时间复杂度为O(n^{1.5)。如果只能在logn的时间移动区间，则时间复杂度是O(n}1.5*log n)。

将这\(n\)个数分成\(s(s=\lfloor \sqrt{n} \rfloor)\)块，第i个在pos[i]块。

然后把询问区间按照pos[l]第一关键字，r第二关键字排序。均递增

然后每次暴力转移

为啥复杂度是对的呢？？？

首先n，m同阶，n=m。

有这样几种转移

块内转移：每块r是递增的，一块的所有转移r是O(n)，l的转移是O(n^0.5)。有n0.5块，所以所有r的转移复杂度是O(n^{1.5)，l最多转移m次，复杂度也是O(n}1.5)。

一块到下一块的转移：O(n)，这样的转移只有O(n^{0.5)次，复杂度还是O(n}1.5)。

所以复杂度就是O(n^1.5)

orz gzy

orz hzwer

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cctype>

using namespace std;

#define il inline

#define vd void

#define rg register

#define int long long

il int gi(){

    rg int x=0;rg bool flg=0;rg char ch=getchar();

    while(!isdigit(ch)){if(ch=='-')flg=1;ch=getchar();}

    while(isdigit(ch))x=x*10-'0'+ch,ch=getchar();

    return flg?-x:x;

}

const int maxn=50001,maxm=maxn;

int c[maxn];

struct qq{int l,r,id,ans;}s[maxm];

int n,m,qt,pos[maxn],ans,tot[maxn];

il bool cmp(const qq&a,const qq&b){return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:a.r<b.r;}

il bool cmp_(const qq&a,const qq&b){return a.id<b.id;}

il int sqr(const int&a){return a*(a-1);}

il int gcd(const int&a,int b){return b?gcd(b,a%b):a;}

main(){

	freopen("hose.in","r",stdin);

	freopen("hose.out","w",stdout);

	n=gi(),m=gi(),qt=sqrt(n);

	for(rg int i=1;i<=n;++i)pos[i]=(i-1)/qt+1;

	for(rg int i=1;i<=n;++i)c[i]=gi();

	for(rg int i=1;i<=m;++i)s[i].l=gi(),s[i].r=gi(),s[i].id=i;

	sort(s+1,s+m+1,cmp);

	s[0].l=s[0].r=1;tot[c[1]]=1;

	for(rg int i=1,j;i<=m;++i){

		for(j=s[i-1].l-1;j>=s[i].l;--j)ans-=sqr(tot[c[j]]),++tot[c[j]],ans+=sqr(tot[c[j]]);

		for(j=s[i-1].r+1;j<=s[i].r;++j)ans-=sqr(tot[c[j]]),++tot[c[j]],ans+=sqr(tot[c[j]]);

		for(j=s[i-1].l;j<s[i].l;++j)ans-=sqr(tot[c[j]]),--tot[c[j]],ans+=sqr(tot[c[j]]);

		for(j=s[i-1].r;j>s[i].r;--j)ans-=sqr(tot[c[j]]),--tot[c[j]],ans+=sqr(tot[c[j]]);

		s[i].ans=ans;

	}

	sort(s+1,s+m+1,cmp_);

	int a,b,_gcd;

	for(rg int i=1;i<=m;++i){

		a=s[i].ans,b=(s[i].r-s[i].l+1)*(s[i].r-s[i].l);

		_gcd=gcd(a,b);

		printf("%lld/%lld\n",a/_gcd,b/_gcd);

	}

	return 0;

}