大视野2038 小z的袜子 莫队算法

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
#define LL long long 
int n,m;
int a[];

struct node{
    int l,r;
    int id;
}Q[];
LL gcd(LL a,LL b){
    return b==?a:gcd(b,a%b);
}
struct q{
    LL  a,b;
    void huajian(){
        LL d = gcd(a,b);
        a /= d;
        b /= d; 
    }
}ans[];
int num[];
int Un;
bool cmp(node a,node b){
    if(a.l/Un != b.l/Un) return a.l/Un < b.l/Un;
    else return a.r < b.r;
}
void work(){
    LL temp = ;
    memset(num,,sizeof(num));
    int l = ;
    int r = ;
    for(int i = ;i < m;i++){
        while(r < Q[i].r){
            r ++;
            temp -= (LL) num[a[r]] * num[a[r]];
            num[a[r]] ++;
            temp += (LL) num[a[r]] * num[a[r]];
        }
        while(r > Q[i].r){
            temp -= (LL) num[a[r]] * num[a[r]];
            num[a[r]] --;
            temp += (LL) num[a[r]] * num[a[r]];
            r--; 
        }
        while(l < Q[i].l){
            temp -= (LL) num[a[l]] * num[a[l]];
            num[a[l]] --;
            temp += (LL) num[a[l]] * num[a[l]];
            l++;
        }
        while(l > Q[i].l){
            l --;
            temp -= (LL) num[a[l]] * num[a[l]];
            num[a[l]] ++;
            temp += (LL) num[a[l]] * num[a[l]];
        }
        ans[Q[i].id].a = temp - (r-l+);
        ans[Q[i].id].b = (LL)(r-l+)*(r-l);
        ans[Q[i].id].huajian();
    }
}


int main(){

    while(cin >> n >> m){
        for(int i = ;i <= n;i++){
            scanf("%d",&a[i]);
        }       
        for(int i = ;i < m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            Q[i].l = x;
            Q[i].r = y;
            Q[i].id = i;
        }
        Un = (int)sqrt(n);
        sort(Q,Q+m,cmp);
        work();
        for(int i = ;i < m;i++){
            printf("%lld/%lld\n",ans[i].a,ans[i].b);
        }
    }
    return ;
}
           

我对莫队算法的理解就是对查询进行排序然后合理的暴力，也就是合理的组织一下查询的顺利让前面的暴力对后面的暴力有一定的贡献，这样就能节省一点时间