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.

Delete this entry (admin only).