# Demo entry 3300742

bzoj2038

Submitted by gaoyb7 on Dec 12, 2015 at 04:02
Language: C++. Code size: 1.6 kB.

```#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define sqr(x) ((x)*(x))
#define LL long long
using namespace std;

const int maxn = 50000 + 10;
int l[maxn], r[maxn], id[maxn];
int c[maxn], tot[maxn];
LL a1[maxn], a2[maxn];
int n, m, sz;
LL tmp;

bool cmp(const int &a, const int &b) {
if (l[a] / sz == l[b] / sz) return r[a] < r[b];
return l[a] / sz < l[b] / sz;
}

void update(int p, int val) {
tmp -= sqr(tot[c[p]]);
tot[c[p]] += val;
tmp += sqr(tot[c[p]]);
}

void set_ans(LL &a, LL &b, LL c, LL d) {
if (c == 0) {
a = 0;
b = 1;
} else {
LL g = __gcd(c, d);
a = c / g;
b = d / g;
}
}

void work() {
for (int i = 1; i <= n; ++i)
scanf("%d", c + i);
for (int i = 0; i < m; ++i)
scanf("%d%d", l + i, r + i), id[i] = i;

sz = sqrt(n + 0.5);
sort(id, id + m, cmp);
memset(tot, 0, sizeof(tot));
int L = 1, R = 0;
tmp = 0;
for (int i = 0; i < m; ++i) {
for ( ;R < r[id[i]]; ++R) update(R + 1, 1);
for ( ;R > r[id[i]]; --R) update(R, -1);
for ( ;L < l[id[i]]; ++L) update(L, -1);
for ( ;L > l[id[i]]; --L) update(L - 1, 1);
if (L == R) {
a1[id[i]] = 0;
a2[id[i]] = 1;
} else {
set_ans(a1[id[i]], a2[id[i]], tmp - (R - L + 1), 1LL * (R - L + 1) * (R - L));
}
}
for (int i = 0; i < m; ++i)
printf("%lld/%lld\n", a1[i], a2[i]);
}

int main() {
while (scanf("%d%d", &n, &m) == 2)
work();
}
```

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.