Code
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
int n, m, k, maxb, b[50007];
ll sum, cnt[50007], ans1[50007];
struct Query
{
int l, r, id, pos;
bool operator <(const Query &x) const
{
if (pos == x.pos) return r < x.r;
else return pos < x.pos;
}
} a[50007];
void add(int i)
{
sum += 2 * cnt[i] - 1;
cnt[i]++;
}
void del(int i)
{
cnt[i]--;
sum -= 2 * cnt[i] + 1;
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &b[i]);
maxb = (int) n / sqrt(m);
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &a[i].l, &a[i].r);
a[i].id = i, a[i].pos = (a[i].l - 1) / maxb + 1;
}
sort(a + 1, a + 1 + m);
for (int i = 1, l = 1, r = 0; i <= m; ++i)
{
while (l < a[i].l) del(b[l++]);
while (l > a[i].l) add(b[--l]);
while (r < a[i].r) add(b[r++]);
while (r > a[i].r) del(b[--r]);
ans1[a[i].id] = sum;
}
for (int i = 1; i <= m; ++i) printf("%lld\n", ans1[i]);
return 0;
}
本Code样例输出
-4
-7
-7
-12