小Z的袜子（莫队基础）

小Z的袜子

我的莫队之旅开始啦！

题意：求区间[l,r]中相同数字的数量关系（具体见题）

思路：（莫队思路）

1. 将所有询问按照左端点 $l$l所在块进行排序，若左端点属于同一块，则按照右端点排序（不用按照左端点具体大小排序啦！）
2. 排序的一点优化，为后面求解过程加速：对于左端点属于第奇数块的询问，将它们按照右端点从小到大排序；对于左端点属于第偶数块的询问，将它们按照右端点，从大到小排序。这样相反的排序可以让 $r$r指针不用每次都从最右边跑到最左边。
3. 莫队的四个 $while$while循环，暴力的模拟 $l,r$l,r指针逐渐靠近 $q.l,q.r$q.l,q.r的过程，每次移动考虑插入和删除。

题面描述

#include "bits/stdc++.h"
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}

const int maxn = 5e4+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const double eps = 1e-7;

int n, m, len;
int c[maxn], cnt[maxn];
ll ans1[maxn], ans2[maxn], ans;

struct Q{
    int l, r, id;
    friend bool operator < (const Q &a, const Q &b) {
        if((a.l-1)/len==(b.l-1)/len) {
            if((a.l-1)/len%2) return a.r>b.r;
            else return a.r<b.r;
        }
        return a.l<b.l;
    }
}q[maxn];

inline void update(int p, int f) {
    ans-=1ll*cnt[c[p]]*(cnt[c[p]]-1);
    cnt[c[p]]+=f;
    ans+=1ll*cnt[c[p]]*(cnt[c[p]]-1);
}

ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); }

int main() {
    //ios::sync_with_stdio(false); cin.tie(0);
    n=read(), m=read(); len=sqrt(n);
    for(int i=1; i<=n; ++i) c[i]=read();
    for(int i=1; i<=m; ++i) q[i]=(Q){read(),read(),i};
    sort(q+1,q+1+m);
    int l=1, r=0;
    int cnt=0;
    for(int i=1; i<=m; ++i) {
        while(l<q[i].l) update(l++,-1);
        while(l>q[i].l) update(--l,1);
        while(r<q[i].r) update(++r,1);
        while(r>q[i].r) update(r--,-1);
        int j=q[i].id;
        if(q[i].l==q[i].r) { ans1[j]=0; ans2[j]=1; continue; }
        ans1[j]=ans; ans2[j]=1ll*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
        ll d=gcd(ans1[j],ans2[j]);
        ans1[j]/=d; ans2[j]/=d;
    }
    for(int i=1; i<=m; ++i) printf("%lld/%lld\n", ans1[i], ans2[i]);
}