[国家集训队] 小z的袜子/【模板】运动队
学习算法首先是学习模板问题。 这就是我加入莫团队的启蒙老师
题解：
先了解莫队的思想，超越顺序后的莫队，时间的复杂度大大降低了。 那么，我们现在可以离线处理区间问题。 这个问题只要询问区间中出现对数的数量，我们只要在已知的区间中进行加减操作就可以得到当前区间的答案。 该统计概率可以在区间内将增加的对数和减少的对数相加，在区间内减去
AC代码：
# include bits/stdc.husingnamespacestd； # definelllonglongconstllmaxn=1e 55； ll pos[maxn]、ans[maxn]、a[maxn]； ll cnt[maxn]，mu[maxn]； ll res； LGCD(LLa，ll b ) if ) b==0)返回a； 返回gcd (b，a%b )； }结构节点{ ll l，r，k； 6q[maxn]； BOOLCMP(nodea，node b ) if ) pos[a.l]==pos[b.l] ) return a.rb.r； 返回pos [ a.l ] pos [ b.l ]； }llcal(llx ) returnx * (x-1 )/2； }voidadd(LLI ) { cnt[a[i]]； RES=cal(CNT[a[I] )-cal ) CNT[a[I]-1 )； }voidsub(LLI ) CNT(a(I )--； RES-=cal(CNT[a[I] )1)-cal (CNT [ a [ I ] )； (}int main ) ) lln，m； 扫描(' % lld % lld )、n、m )； ldis=sqrt(n； for(LLI=1； i=n； I ) Scanf('%lld '，a[i]； pos[i]=i/dis； }for(LLI=0； im； I ) scanf('%lld%lld )、q[i].l、q[i].r )； q[i].k=i； }sort(q、q m、cmp )； ll l=1，r=0； for(LLI=0； im； I ) ) while(LQ[I].L ) ) sub ) l； }while(rq[I].r ) ) sub(r-- )； (while ) LQ[I].L ) add(-L )； }while(rq[I].r ) add ) r； }if(l==r ) { ans[q[i].k]=0； mu[q[i].k]=1； } else { ll len=q[i].r-q[i].l 1； Len=(Len-1 ) ) *len/2； ans[q[I].k]=res/gcd(Len，RES )； mu[q[I].k]=Len/gcd(Len，res )； }for(llI=0； im； I ) printf('%lld/%lld(n )，ans[i]，mu[i] )； }