题目链接
题目概况
小B的询问
题目描述
小B 有一个长为 n n n 的整数序列 a a a,值域为 [ 1 , k ] [1,k] [1,k]。
他一共有 m m m 个询问,每个询问给定一个区间 [ l , r ] [l,r] [l,r],求:
∑ i = 1 k c i 2 \sum\limits_{i=1}^k c_i^2 i=1∑kci2
其中 c i c_i ci 表示数字 i i i 在 [ l , r ] [l,r] [l,r] 中的出现次数。
小B请你帮助他回答询问。
输入格式
第一行三个整数 n , m , k n,m,k n,m,k。
第二行 n n n 个整数,表示 小B 的序列。
接下来的 m m m 行,每行两个整数 l , r l,r l,r。
输出格式
输出 m m m 行,每行一个整数,对应一个询问的答案。
样例 #1
样例输入 #1
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
样例输出 #1
6
9
5
2
提示
【数据范围】
对于 100 % 100\% 100% 的数据, 1 ≤ n , m , k ≤ 5 × 1 0 4 1\le n,m,k \le 5\times 10^4 1≤n,m,k≤5×104。
个人思路
普通的莫队做法:首先将所有询问按照询问边界进行排序(详见Query
类里的比较方法)。每次询问,如果边界向外扩张,则重新计算当前的 c i c_i ci 累加和——即代码中变量 sumn
。
参考代码
C++
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4 + 3;
int n, m, k, arr[N], maxn;
// cnt[i]记录i在当前区间出现的次数
int cnt[N];
ll ans[N], sumn = 0;
class Query
{
public:
int id, l, r;
int operator<(const Query &x) const {
// 重载<运算符
if (l / maxn != x.l / maxn) return l < x.l;
return (l / maxn) & 1 ? r < x.r : r > x.r;
}
};
Query q[N];
void add(int i)
{
sumn = sumn - cnt[arr[i]] * cnt[arr[i]];
cnt[arr[i]]++;
sumn += cnt[arr[i]] * cnt[arr[i]];
}
void del(int i)
{
sumn = sumn - cnt[arr[i]] * cnt[arr[i]];
cnt[arr[i]]--;
sumn += cnt[arr[i]] * cnt[arr[i]];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m >> k;
maxn = sqrt(n);
for(int i = 1; i <= n; ++i)
{
cin >> arr[i];
}
for(int i = 0; i < m; ++i)
{
q[i].id = i;
cin >> q[i].l >> q[i].r;
}
sort(q, q + m);
int l = 1, r = 0;
for(int i = 0; i < m; ++i)
{
while(l > q[i].l)
{
add(--l);
}
while(r < q[i].r)
{
add(++r);
}
while(l < q[i].l)
{
del(l++);
}
while(r > q[i].r)
{
del(r--);
}
ans[q[i].id] = sumn;
}
for(int i = 0; i < m; ++i)
{
cout << ans[i] << "\n";
}
return 0;
}