題意
有一個序列,包含N個1~K之間的整數。一共有M個詢問,每個詢問給定一個區間[L..R],求Sigma(c(i)^2)的值,其中i的值從1到K,其中c(i)表示數字i在[L..R]中的重複次數。
n,m,k<=50000
分析
莫隊算法好勁啊!!!
按所在塊為第一關鍵字,右端點為第二關鍵字對詢問排序,然後就可以直接上莫隊啦。
代碼
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ll long long
#define N 50005
using namespace std;
int n,m,cnt,cnt1,t[N],a[N],pos[N],k,block;
struct data{int id,x,y;ll ans;}q[N];
ll ans;
bool cmp(data a,data b)
{
return pos[a.x]<pos[b.x]||pos[a.x]==pos[b.x]&&a.y<b.y;
}
bool cmpid(data a,data b)
{
return a.id<b.id;
}
void updata(int x,int y)
{
ans-=(ll)t[a[x]]*t[a[x]];
t[a[x]]+=y;
ans+=(ll)t[a[x]]*t[a[x]];
}
void query()
{
updata(,);
for (int i=,l=,r=;i<=m;i++)
{
for (;r<q[i].y;r++)
updata(r+,);
for (;l>q[i].x;l--)
updata(l-,);
for (;r>q[i].y;r--)
updata(r,-);
for (;l<q[i].x;l++)
updata(l,-);
q[i].ans=ans;
}
}
int main()
{
scanf("%d%d%d",&n,&m,&k);
block=sqrt(n);
for (int i=;i<=n;i++)
{
scanf("%d",&a[i]);
pos[i]=(i+block-)/block;
}
for (int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
q[i].x=x;q[i].y=y;q[i].id=i;
}
sort(q+,q+m+,cmp);
query();
sort(q+,q+m+,cmpid);
for (int i=;i<=m;i++)
printf("%lld\n",q[i].ans);
return ;
}