洛谷 P2709 BZOJ 3781 小B的询问
2024-08-31 06:25:22
题目描述
小B有一个序列,包含N个1~K之间的整数。他一共有M个询问,每个询问给定一个区间[L..R],求$\sum_1^Kc_i^2$的值,其中$c_i$表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
输入输出格式
输入格式:
第一行,三个整数N、M、K。
第二行,N个整数,表示小B的序列。
接下来的M行,每行两个整数L、R。
输出格式:
M行,每行一个整数,其中第i行的整数表示第i个询问的答案。
输入输出样例
输入样例#1:
6 4 3
1 3 2 1 1 3
1 4
2 6
3 5
5 6
输出样例#1:
6
9
5
2
说明
对于全部的数据,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 = ; int res = ;
while (( (c=getchar())<||c>) && c!= '-');
if (c=='-') f = -;
else res = c- '';
while ( (c = getchar()) >= && c <= )
res = res * + c -'';
return f *res;
} int n,m,k;
int c[]={};
int f[]={}; struct query{
int id,pos,l,r,ans;
}a[];
int aa[]={};
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=;i<=n;i++)
c[i]=get();
for(int i=,l,r,kuai=sqrt(n);i<=m;i++)
{
l=get();
r=get();
a[i]={i,l/kuai,l,r,};
}
sort(a+,a++m,cmp1);
for(int i=,l=,r=,t=;i<=m;i++)
{
while(r<a[i].r)
{
r+=;
t+=(f[c[r]]<<)+;
f[c[r]]+=;
}
while(l<a[i].l)
{
t-=(f[c[l]]<<)-;
f[c[l]]--;
l++;
}
while(l>a[i].l)
{
l--;
t+=(f[c[l]]<<)+;
f[c[l]]++;
}
while(r>a[i].r)
{
t-=(f[c[r]]<<)-;
f[c[r]]--;
r--;
}
a[i].ans=t;
}
for(int i=;i<=m;i++) aa[a[i].id]=a[i].ans-;
for(int i=;i<=m;i++) printf("%d\n",aa[i]);
return ;
}
最新文章
- php 时间戳与日期的转换(转载)
- jdk8中java.util.concurrent包分析
- Android基于mAppWidget实现手绘地图(四)--如何附加javadoc
- 下载安装resin-3.X服务器并配置到myeclipse
- Titan-红号楼宗谱案例
- C# 文本框 TextChanged 延时触发
- qml自定义标题栏
- 为什么样本方差(sample variance)的分母是 n-1?
- 万维网发布服务(w3svc)已停止,除非万维网发布服务(w3svc)正在运行。
- oc特有语法
- IAsyncResult 接口异步 和匿名委托
- java json转换(二)
- openvas scanner 服务未启动修复
- Linux下使用RedisPool时报错:redis.clients.jedis.HostAndPort getLocalHostQuietly 严重: cant resolve localhost address
- 外部引入的js 判断js脚本加载是否完成,完成后执行 相应的动作(以引入百度地图js为例)
- 甘特图 (Gantt )的优缺点
- IO事件驱动模型
- 位运算&;,逻辑与and
- CentOS7下Docker中构建可以自动发布到项目的Tomcat容器
- 带报表的asp.net项目不要升级