AcWing 251. 小Z的袜子| 分块+莫队

#include using namespace std;
#define ll long long
const int N = 50000 + 10;
int a[N],pre[N];
struct node{
    int id,l,r;
    ll x,y;
    bool operator const node &t)const {
        if (pre[l] == pre[t.l]) return rt.r;
        return pre[l]pre[t.l];
    }
}q[N];
bool cmp(node i,node j) {
    return i.id  j.id;
}
ll num[N];
ll gcd(ll a,ll b) {
    return b?gcd(b,a%b):a;
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    int k = sqrt(n);
    for (int i = 1; i ) {
        scanf("%d",&a[i]);
        pre[i] = i/k;
    }
    for (int i = 0; i ){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int L = 1, R = 0;
    ll fz = 0,fm = 0;
    for (int i = 0; i ) {
        if (q[i].l==q[i].r) {
            q[i].x = 0;
            q[i].y = 1;
            continue;
        }
        while (R  q[i].r) {
            R++;
            fz -= num[a[R]] * (num[a[R]]-1);
            num[a[R]]++;
            fz += num[a[R]] * (num[a[R]]-1);
        }
        while (R > q[i].r) {
            fz -= num[a[R]] * (num[a[R]]-1);
            num[a[R]]--;
            fz += num[a[R]] * (num[a[R]]-1);
            R--;
        }
        while (L  q[i].l) {
            fz -= num[a[L]] * (num[a[L]]-1);
            num[a[L]]--;
            fz += num[a[L]] * (num[a[L]]-1);
            L++;
        }
        while (L > q[i].l) {
            L--;
            fz -= num[a[L]] * (num[a[L]]-1);
            num[a[L]]++;
            fz += num[a[L]] * (num[a[L]]-1);
        }
        fm = (ll)(R-L+1)*(R-L); //忘记类型转换。。WA了几发
        ll tf = gcd(fz,fm);
        q[i].x = fz/tf;
        q[i].y = fm/tf;
    }
    sort(q,q+m,cmp);
    for (int i = 0; i ) 
        printf("%lld/%lld\n",q[i].x,q[i].y);
    return 0;
}