同一份代码提交可以因为在不同的点TLE获得$[60,80]$的成绩（

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50005;
int n, m, pos[MAXN], c[MAXN];
long long s[MAXN], ans;
struct data {
    int l, r, id;
    long long a, b;
} a[MAXN];
bool cmp( const data& a, const data& b ) {
    if ( pos[a.l] == pos[b.l] ) {
        return a.r < b.r;
    }
    return a.l < b.l;
}
bool cmp_id( const data& a, const data& b ) {
    return a.id < b.id;
}
void update( int p, int add ) {
    ans -= s[c[p]] * s[c[p]];
    s[c[p]] += add;
    ans += s[c[p]] * s[c[p]];
}
int main() {
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cin >> n >> m;
    for ( int i = 1; i <= n; i++ ) {
        cin >> c[i];
    }
    int block = sqrt( n );
    for ( int i = 1; i <= n; i++ ) {
        pos[i] = ( i - 1 ) / block + 1;
    }
    for ( int i = 1; i <= m; i++ ) {
        cin >> a[i].l >> a[i].r;
        a[i].id = i;
    }
    sort( a + 1, a + m + 1, cmp );
    for ( int i = 1, l = 1, r = 0; i <= m; i++ ) {
        for ( ; r < a[i].r; r++ ) {
            update( r + 1, 1 );
        }
        for ( ; r > a[i].r; r-- ) {
            update( r, -1 );
        }
        for ( ; l < a[i].l; l++ ) {
            update( l, -1 );
        }
        for ( ; l > a[i].l; l-- ) {
            update( l - 1, 1 );
        }
        if ( a[i].l == a[i].r ) {
            a[i].a = 0;
            a[i].b = 1;
            continue;
        }
        a[i].a = ans - ( a[i].r - a[i].l + 1 );
        a[i].b = ( a[i].r - a[i].l + 1 ) * 1LL * ( a[i].r - a[i].l );
        long long g = __gcd( a[i].a, a[i].b );
        a[i].a /= g;
        a[i].b /= g;
    }
    sort( a + 1, a + m + 1, cmp_id );
    for ( int i = 1; i <= m; i++ ) {
        cout << a[i].a << "/" << a[i].b << endl;
    }
    return 0;
}

下面是评测记录。

• 第一发80pts
• 第二发70pts
• 第三发CE
• 第四发60pts