题目描述
小 B 有一个长为 \(n\) 的整数序列 \(a\)，值域为 \([1,k]\)。
他一共有 \(m\) 个询问，每个询问给定一个区间 \([l,r]\)，求：
\[\sum\limits_{i=1}^k c_i^2
\]
其中 \(c_i\) 表示数字 \(i\) 在 \([l,r]\) 中的出现次数。
小 B 请你帮助他回答询问。
输入格式
第一行三个整数 \(n,m,k\)。
第二行 \(n\) 个整数，表示小 B 的序列。
接下来的 \(m\) 行，每行两个整数 \(l,r\)。
输出格式
输出 \(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\%\) 的数据，\(1\le n,m,k \le 5\times 10^4\)。
题解
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long ll;
int n,k,m;
struct Node
{int l,r,i;
}q[N];ll sum = 0;
int a[N];
int blen;
int bi[N];
int cnt[N];
int cl=1,cr=0;
int ans[N];bool cmp(Node a,Node b)
{if(bi[a.l]!=bi[b.l])return bi[a.l]<bi[b.l];return a.r<b.r;
}void build()
{blen = (int)sqrt(n);for(int i=1;i<=n;i++){bi[i] = (i-1)/blen +1;}sort(q+1,q+1+m,cmp);}void add(int x)
{sum -= cnt[x]*cnt[x];cnt[x]++;sum += cnt[x]*cnt[x];
}void sub(int x)
{sum -= cnt[x]*cnt[x];cnt[x]--;sum += cnt[x]*cnt[x];
}void solve()
{cin>>n>>m>>k;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].i=i;}build();for(int i=1;i<=m;i++){int l = q[i].l;int r = q[i].r;while(cl>l){add(a[--cl]);}while(cr<r){add(a[++cr]);}while(cl<l){sub(a[cl++]);}while(cr>r){sub(a[cr--]);}ans[q[i].i] = sum;}for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;// cin>>t;while(t--){solve();}return 0;
}