【bzoj2038-小z的袜子】莫队算法

莫队例题。

莫队学习：https://www.cnblogs.com/Paul-Guderian/p/6933799.html

本题 分子是sigma(c(sum[a[i]],2))，分母是sigma(l-r+1,2); 维护分子和即可。

莫队适用范围：离线，区间，区间转移到下一格O(1)。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 const int N=;

 typedef long long LL;

 int n,m,sq,a[N];

 LL ans,gcd,sum[N];

 struct node{

     int l,r,k,id;

     LL fz,fm;

 };

 node b[N];

 int maxx(int x,int y){return x>y?x:y;}

 bool cmp1(node x,node y)

 {

     if(x.k==y.k) return x.r<y.r;

     return x.l<y.l;

 }

 bool cmp2(node x,node y)

 {

     return x.id<y.id;

 }

 void revise(int x,int d)

 {

     ans-=sum[a[x]]*(sum[a[x]]-)/;

     sum[a[x]]+=d;

     ans+=sum[a[x]]*(sum[a[x]]-)/;

 }

 LL getgcd(LL a,LL b)

 {

     return b?getgcd(b,a%b):a;

 }

 int main()

 {

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

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

     scanf("%d%d",&n,&m);sq=sqrt(n);

     for(int i=;i<=n;i++) scanf("%d",&a[i]);

     for(int i=;i<=m;i++)

     {

         scanf("%d%d",&b[i].l,&b[i].r);

         b[i].k=b[i].l/sq;

         b[i].id=i;

     }

     sort(b+,b+m+,cmp1);

     memset(sum,,sizeof(sum));

     int l=,r=;sum[a[]]=;ans=;

     for(int i=;i<=m;i++)

     {

         while(l<b[i].l) {revise(l,-);l++;}

         while(l>b[i].l) {revise(l-,);l--;}

         while(r<b[i].r) {revise(r+,);r++;}

         while(r>b[i].r) {revise(r,-);r--;}

         b[i].fz=ans;b[i].fm=((LL)(b[i].r-b[i].l+))*((LL)(b[i].r-b[i].l))/;

         gcd=getgcd(b[i].fz,b[i].fm);

         b[i].fz/=gcd;b[i].fm/=gcd;

         if(b[i].fz==) b[i].fm=;

     }

     sort(b+,b+m+,cmp2);

     for(int i=;i<=m;i++)

     {

         printf("%lld/%lld\n",b[i].fz,b[i].fm);

     }

     return ;

 }