rt，常数过大，TLE 0 pts

开了O2才AC

#include<bits/stdc++.h>
#define AC return 0;
using namespace std;
const int maxn = 5e5 + 10;
int n, m, k;
char getc()
{
    static char ch[10000000], *s, *t;
    return (s == t) && (t = (s = ch) + fread(ch, 1, 10000000, stdin)), s == t ? EOF : *s++;
}
void read(int &x)
{
    char ch = getc();
    bool f = 0;
    x = 0;
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = 1;
        ch = getc();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - '0';
        ch = getc();
    }
    f ? x = -x : 0;
}
int pos[maxn],a[maxn],cnt[maxn];
long long ans[maxn],res;
struct query
{
    int l, r, id;
    bool operator<(const query x)
    {
        if (pos[l] == pos[x.l])
        {
            if (pos[l] & 1)
                return r < x.r;
            else
                return r > x.r;
        }
        else
        {
            return pos[l] < pos[x.l];
        }
    }
}q[maxn];

inline void add(int x)
{
    res += (cnt[a[x]]++) * 2 + 1;
}
inline void del(int x)
{
    res -= (cnt[a[x]]--) * 2 - 1;
}
void solve()
{
    int l = q[1].l, r = q[1].l - 1, ql, qr;
    for (int i = 1; i <= m; ++i)
    {
        ql = q[i].l, qr = q[i].r;
        while (l < ql)
            del(l++);
        while (l > ql)
            add(--l);
        while (r < qr)
            add(++r);
        while (r > qr)
            del(r--);
        ans[q[i].id] = res;
    }
    for (int i = 1; i <= m; ++i)
        printf("%lld\n", ans[i]);
}
void init()
{
    read(n);
    int sn = sqrt(n);
    read(m);
    read(k);
    for (int i = 1; i <= n; ++i)
        read(a[i]), pos[i] = ((i - 1 / sn) + 1);
    for (int i = 1; i <= m; ++i)
        read(q[i].l), read(q[i].r), q[i].id = i;
    sort(q + 1, q + 1 + m);
}
int main()
{
    init();
    solve();
    AC
}