关于 CF86D Powerful array，为什么每块的大小为 sqrt(n) 就 TLE，而 sqrt(1000010) 就可以啊？谢谢！

AC 的：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
#define LL __int128
using namespace std;
ll n, m, T, a[1000010], c[1000010], ans[1000010], sum;
struct Range {
    int l, r, id;
    bool operator <(const Range &W)const {
        if (l / T != W.l / T) return l < W.l;
        return r < W.r;
    }
}b[1000010];
inline void add(ll x) {
    sum -= c[x] * c[x] * x;
    c[x] ++ ;
    sum += c[x] * c[x] * x;
}
inline void del(ll x) {
    sum -= c[x] * c[x] * x;
    c[x] -- ;
    sum += c[x] * c[x] * x;
}
int main() {
    scanf("%lld%lld", &n, &m);
    T = sqrt(1000010); // This line.
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    for (int i = 1; i <= m; i ++ ) {
        scanf("%d%d", &b[i].l, &b[i].r);
        b[i].id = i;
    }
    sort(b + 1, b + m + 1);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i ++ ) {
        while (L > b[i].l) add(a[ -- L]);
        while (R < b[i].r) add(a[ ++ R]);
        while (L < b[i].l) del(a[L ++ ]);
        while (R > b[i].r) del(a[R -- ]);
        ans[b[i].id] = sum;
    }
    for (int i = 1; i <= m; i ++ ) printf("%lld\n", ans[i]);
    return 0;
}

TLE 的：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
#define LL __int128
using namespace std;
ll n, m, T, a[1000010], c[1000010], ans[1000010], sum;
struct Range {
    int l, r, id;
    bool operator <(const Range &W)const {
        if (l / T != W.l / T) return l < W.l;
        return r < W.r;
    }
}b[1000010];
inline void add(ll x) {
    sum -= c[x] * c[x] * x;
    c[x] ++ ;
    sum += c[x] * c[x] * x;
}
inline void del(ll x) {
    sum -= c[x] * c[x] * x;
    c[x] -- ;
    sum += c[x] * c[x] * x;
}
int main() {
    scanf("%lld%lld", &n, &m);
    T = sqrt(n); // This line.
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &a[i]);
    for (int i = 1; i <= m; i ++ ) {
        scanf("%d%d", &b[i].l, &b[i].r);
        b[i].id = i;
    }
    sort(b + 1, b + m + 1);
    int L = 1, R = 0;
    for (int i = 1; i <= m; i ++ ) {
        while (L > b[i].l) add(a[ -- L]);
        while (R < b[i].r) add(a[ ++ R]);
        while (L < b[i].l) del(a[L ++ ]);
        while (R > b[i].r) del(a[R -- ]);
        ans[b[i].id] = sum;
    }
    for (int i = 1; i <= m; i ++ ) printf("%lld\n", ans[i]);
    return 0;
}