【luogu P1494 [国家集训队]小Z的袜子】 题解

题目链接：https://www.luogu.org/problemnew/show/P1494

#include <cstdio>

#include <algorithm>

#include <iostream>

#include <cmath>

using namespace std;

const int maxn =  50000+10;

inline long long read()

{

    long long k=0;

    char c;

    c=getchar();

    while(!isdigit(c))c=getchar();

    while(isdigit(c)){k=(k<<3)+(k<<1)+c-'0';c=getchar();}

    return k;

}

long long n, m, bl, answer, curL = 1, curR = 0, cnt[maxn], a[maxn], gg;

struct query{

	long long p, l, r;

}e[maxn];

struct answers{

	long long x, y;

}ans[maxn], now;

long long gcd(long long x, long long y)

{

	if(x%y == 0) return y;

	else return gcd(y,x%y);

}

bool cmp(query a, query b)

{

	return (a.l/bl) == (b.l/bl) ? a.r < b.r : a.l < b.l;

}

void add(long long pos)

{

	cnt[a[pos]]++;

	if(cnt[a[pos]] > 1)

	now.x = now.x + cnt[a[pos]]*(cnt[a[pos]]-1)-(cnt[a[pos]]-1)*(cnt[a[pos]]-2);

}

void remove(long long pos)

{

	cnt[a[pos]]--;

	if(cnt[a[pos]] > 0)

	now.x = now.x + cnt[a[pos]]*(cnt[a[pos]]-1)-(cnt[a[pos]]+1)*cnt[a[pos]];

}

int main()

{

	n = read(); m = read();

	bl = sqrt(n);

	for(long long i = 1; i <= n; i++)

	a[i] = read();

	for(long long i = 1; i <= m; i++)

	{

		e[i].l = read(); e[i].r = read(); e[i].p = i;

	}

	sort(e+1,e+1+m,cmp);

	for(long long i = 1; i <= m; i++)

	{

		long long L = e[i].l, R = e[i].r;

		while(curL < L)

			remove(curL++);

		while(curL > L)

			add(--curL);

		while(curR < R)

			add(++curR);

		while(curR > R)

			remove(curR--);

		now.y = (e[i].r-e[i].l+1)*(e[i].r-e[i].l);

		if (!now.x)

		{

			now.x=0;

			now.y=1;

		}

		gg = gcd(now.x, now.y);

		ans[e[i].p].x = now.x/gg;

		ans[e[i].p].y = now.y/gg;

	}

	for(long long i = 1; i <= m; i++)

	printf("%lld/%lld\n",ans[i].x,ans[i].y);

	return 0;

}