[Luogu] p2709 little B's inquiry

Title address ：

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

Title Description ：
Small B There's a long one for $n$ Integer sequence of $a$, The value range is $[1,k]$. He has $m$ A asked , Each query is given an interval $[l,r]$, seek ：$$\sum _{i=1}^k{c}_i^2$$ among $c_i$ Representation number $i$ stay $[l,r]$ The number of occurrences in . Small B Please help him answer the question .

Input format ：
The first row has three integers $n,m,k$.
The second line $n$ It's an integer , It means small B Sequence .
Next $m$ That's ok , Two integers per line $l,r$.

Output format ：
Output $m$ That's ok , One integer per row , The answer to a question .

Data range ：
about $100\%$ The data of ,$1\le n,m,k\le 5\times 10^4$.

Can use Mo team , Inquiries can be averaged $O(\sqrt{n})$ Transfer . Reference resources https://blog.csdn.net/qq_46105170/article/details/125827776. The code is as follows ：

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 5e4 + 10;
int n, m, k, len;
int a[N], bel[N], cnt[N];
long res[N], ans;
struct Query {
    
  int id, l, r;
} q[N];

void add(int x) {
    
  ans -= cnt[x] * cnt[x];
  cnt[x]++;
  ans += cnt[x] * cnt[x];
}

void del(int x) {
    
  ans -= cnt[x] * cnt[x];
  cnt[x]--;
  ans += cnt[x] * cnt[x];
}

int main() {
    
  scanf("%d%d%d", &n, &m, &k);
  len = sqrt(n);
  for (int i = 1; i <= n; i++) {
    
    bel[i] = i / len;
    scanf("%d", &a[i]);
  }

  for (int i = 0; i < m; i++) {
    
    scanf("%d%d", &q[i].l, &q[i].r);
    q[i].id = i;
  }

  sort(q, q + m, [&](Query& q1, Query& q2) {
    
    int l1 = q1.l, l2 = q2.l;
    if (bel[l1] != bel[l2]) return bel[l1] < bel[l2];
    int r1 = q1.r, r2 = q2.r;
    if (bel[l1] & 1) return r1 < r2;
    else return r1 > r2;
  });

  for (int k = 0, i = 0, j = 1; k < m; k++) {
    
    int id = q[k].id, l = q[k].l, r = q[k].r;
    while (i < r) add(a[++i]);
    while (i > r) del(a[i--]);
    while (j < l) del(a[j++]);
    while (j > l) add(a[--j]);
    res[id] = ans;
  }

  for (int i = 0; i < m; i++) printf("%ld\n", res[i]);
}

Preprocessing time complexity $O(m\log m)$, Time of each inquiry $O(\sqrt{n})$, Space $O(n+k)$.