https://www.luogu.com.cn/problem/P2709

先ql < l_____r < qr

再 l < ql____qr < r

const int N = 200010;
ll res;
ll a[N], pos[N], ans[N], cnt[N];
struct Q
{
    int l, r, k;
}q[N];
ll cmp(Q a, Q b)
{
    if (pos[a.l] == pos[b.l]) return a.r < b.r;
    else return pos[a.l] < pos[b.l];
}
void add(int x)
{
    res += (cnt[x] * cnt[x]) - ((cnt[x] - 1) * (cnt[x] - 1));
}
void det(int x)
{
    res -= ((cnt[x] + 1) * (cnt[x] + 1)) - (cnt[x] * cnt[x]);
}
void solve()
{
    int n, m, len;
    cin >> n >> m >> len;
    int size = sqrt(n);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        pos[i] = i / size;
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> q[i].l >> q[i].r;
        q[i].k = i;
    }
    sort(q + 1, q + 1 + m, cmp);
    int l = 1, r = 0;
    for (int i = 1; i <= m; i++)
    {
        while (q[i].l < l)
        {
            l--;
            cnt[a[l]]++;
            add(a[l]);
        }
        while (q[i].r > r)
        {
            r++;
            cnt[a[r]]++;
            add(a[r]);
        }
        while (q[i].l > l)
        {
            cnt[a[l]]--;
            det(a[l]);
            l++;
        }
        while (q[i].r < r)
        {
            cnt[a[r]]--;
            det(a[r]);
            r--;
        }
        ans[q[i].k] = res;
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}