首页 > 代码库 > 洛谷 P2709 小B的询问
洛谷 P2709 小B的询问
https://www.luogu.org/problem/show?pid=2709
题目描述
小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求Sigma(c(i)^2)的值,其中i的值从1到K，其中c(i)表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
输入输出格式
输入格式：
第一行，三个整数N、M、K。
第二行，N个整数，表示小B的序列。
接下来的M行，每行两个整数L、R。
输出格式：
M行，每行一个整数，其中第i行的整数表示第i个询问的答案。
输入输出样例
输入样例#1：
6 4 31 3 2 1 1 31 42 63 55 6
输出样例#1：
6952
说明
对于全部的数据，1<=N、M、K<=50000
莫队
#include<cmath>#include<cstdio>#include<algorithm>using namespace std;#define N 50001int n,m,k,siz;int key[N],sum[N],bl[N];long long ans[N],tmp;struct node{ int l,r,id; bool operator < (node p)const { if(bl[l]!=bl[p.l]) return bl[l]<bl[p.l]; return r<p.r; } }e[N];inline void update(int pos,bool w){ tmp-=1ll*sum[key[pos]]*sum[key[pos]]; if(w) sum[key[pos]]++; else sum[key[pos]]--; tmp+=1ll*sum[key[pos]]*sum[key[pos]];}int main(){ scanf("%d%d%d",&n,&m,&k); siz=sqrt(n); for(int i=1;i<=n;i++) bl[i]=(i-1)/siz+1; for(int i=1;i<=n;i++) scanf("%d",&key[i]); int u,v; for(int i=1;i<=m;i++) { scanf("%d%d",&u,&v); e[i].l=u; e[i].r=v; e[i].id=i; } sort(e+1,e+m+1); int L=1,R=0; for(int i=1;i<=m;i++) { while(L>e[i].l) update(--L,true); while(L<e[i].l) update(L++,false); while(R>e[i].r) update(R--,false); while(R<e[i].r) update(++R,true); ans[e[i].id]=tmp; } for(int i=1;i<=m;i++) printf("%d\n",ans[i]);}
洛谷 P2709 小B的询问
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。