https://ac.nowcoder.com/acm/contest/1085/G

description：

n个数m个询问 l,r 问图片说明 num(ai)为ai出现的次数

solution：

这题区间问题可以很好的用莫队维护，设定一个vis[i]数组代表出现的次数，
关于add操作，每出现一个新的次数 使得之前出现的数对答案的贡献得加上vis[a[x] * a[x] 那么当前这个数对答案贡献为(vis[a[x]] + 1)*a[x]

关于del操作，区间去掉一个数，这个数的出现次数先减去1，那么前面所有与这个数相等的都要减上这个数，然后再减去这个数再乘此时的出现次数

code：

#include <bits/stdc++.h>

using namespace std;

#define LL long long

const int N = 1e5 + 50;

int a[N];
LL res[N];

int n, m, block;

int belong(int x) { return x / block; }

struct node {
  int l, r, id;
} q[N];

bool cmp(node a, node b) {
  return (belong(a.l) ^ belong(b.l))
             ? belong(a.l) < belong(b.l)
             : ((belong(a.l) & 1) ? a.r < b.r : a.r > b.r);
}

int vis[N];
LL sum = 0;
void add(int x) {
  sum += 1LL * vis[a[x]] * a[x] + 1LL * (vis[a[x]] + 1) * a[x];
  vis[a[x]]++;
}

void del(int x) {
  vis[a[x]]--;
  sum -= 1LL * vis[a[x]] * a[x] + 1LL * (vis[a[x]] + 1) * a[x];
}

int main() {
  scanf("%d%d", &n, &m);
  block = sqrt(n);

  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }

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

  sort(q + 1, q + 1 + m, cmp);
  int l = 1, r = 0;

  for (int i = 1; i <= m; i++) {
    while (r < q[i].r) {
      add(++r);
    }
    while (r > q[i].r) {
      del(r--);
    }
    while (l < q[i].l) {
      del(l++);
    }
    while (l > q[i].l) {
      add(--l);
    }
    res[q[i].id] = sum;
  }

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

  return 0;
}