首页 > 代码库 > 洛谷 P2709 BZOJ 3781 小B的询问
洛谷 P2709 BZOJ 3781 小B的询问
题目描述
小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
吐槽
BZOJ居然把这题设成权限题，我们这种穷人做不起啊，放个题号吧。
我的代码在洛谷上跑的挺快，刚开始没开O2，跑了1900+ms，然后去大牛分站交了一波，瞬间540毫秒，rank3了啊！估计我的程序最大的耗时处在两个sort上，algorithm里的东西和STL里的东西缺氧，吸了氧就跑得飞快，几乎是缺氧时的四倍速度了。
后来加快读、乘法换成位运算、另开一个数组$O(m)$记录答案而不是第二次排序，尤其是最后一项，整整少了60ms，终于卡到了473ms，目前的洛谷rank1.
解题思路
一道裸的莫队。莫队的原理可以看我这篇博文，每个莫队题目最重要的步骤都是推导出区间中减少一个元素或加入一个元素后答案的变化。
这题推公式不难。设当前区间$[l,r]$的答案为$t$，那么增加(l--或r++)一个元素时，设增加元素的颜色为k (l-1或r+1)，$f(k)$为题目中的$c(k)$，那么$t+=(f(k)+1)^2-f^2(k)=2*f(k)+1$，同理，减少一个颜色为k的元素时$t-=f^2(k)-(f(k)+1)^2=2*f(k)-1$，于是就套上莫队的标志“四个while”吧。
源代码
#include<cmath>#include<cstdio>#include<algorithm>using namespace std;inline int get(){ char c;short f = 1; int res = 0; while (( (c=getchar())<48||c>57) && c!= ‘-‘); if (c==‘-‘) f = -1; else res = c- ‘0‘; while ( (c = getchar()) >= 48 && c <= 57) res = res * 10 + c -‘0‘; return f *res;}int n,m,k;int c[50010]={0};int f[50010]={0};struct query{ int id,pos,l,r,ans;}a[50010];int aa[50010]={0};inline int cmp1(const query & a,const query & b){ return a.pos==b.pos?a.r<b.r:a.pos<b.pos;}int main(){ n=get(),m=get(),k=get(); for(int i=1;i<=n;i++) c[i]=get(); for(int i=1,l,r,kuai=sqrt(n);i<=m;i++) { l=get(); r=get(); a[i]={i,l/kuai,l,r,0}; } sort(a+1,a+1+m,cmp1); for(int i=1,l=0,r=0,t=0;i<=m;i++) { while(r<a[i].r) { r+=1; t+=(f[c[r]]<<1)+1; f[c[r]]+=1; } while(l<a[i].l) { t-=(f[c[l]]<<1)-1; f[c[l]]--; l++; } while(l>a[i].l) { l--; t+=(f[c[l]]<<1)+1; f[c[l]]++; } while(r>a[i].r) { t-=(f[c[r]]<<1)-1; f[c[r]]--; r--; } a[i].ans=t; } for(int i=1;i<=m;i++) aa[a[i].id]=a[i].ans-1; for(int i=1;i<=m;i++) printf("%d\n",aa[i]); return 0;}
洛谷 P2709 BZOJ 3781 小B的询问
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。