CF433B Kuriyama Mirai's Stones 题解
2024-10-10 09:02:50
Content
有一个长度为 \(n\) 的数组 \(a_1,a_2,a_3,...,a_n\)。有 \(m\) 次询问,询问有以下两种:
- \(1~l~r\),求 \(\sum\limits_{i=l}^ra_i\)。
- \(2~l~r\),将数组非降序排列后再依次标号,然后再求 \(\sum\limits_{i=l}^ra_i\)。
数据范围:\(1\leqslant l\leqslant r\leqslant n\leqslant 10^5,1\leqslant m\leqslant 10^5,1\leqslant a_i\leqslant 10^9\)。
Solution
这道题旨在考察对前缀和的操作,比如说这道题目我们就可以用前缀和很好地求解。具体如下:
我们先将没有排序的数组求出他们的前缀和 \(s_i=\sum\limits_{j=1}^ia_j\),然后再按照题目要求排序得到 \(a'\) 数组,再求出 \(s'_i=\sum\limits_{j=1}^ia_j\)。再接着,我们根据两种不同的操作分类讨论:
- 对于第一种操作,我们知道:\(s_{l-1}=\sum\limits_{i=1}^{l-1} a_i,s_r=\sum\limits_{i=1}^n a_i\)。由此我们得到 \(s_r-s_{l-1}=a_r+a_{r-1}+...+a_l+a_{l-1}+...+a_1-(a_l+a_{l-1}+...+a_l)=a_l+a_{l+1}+...+a_r\)。正好就是我们所要求的 \([l,r]\) 这个区间内所有数的总和。由此我们就知道了,第一种操作的答案就是 \(s_r-s_{l-1}\)。
- 对于第二种操作,和第一种操作类似,只不过变成了排序后的数组的前缀和罢了,除了排序以外几乎没什么差别,答案就是 \(s'_r-s'_{l-1}\)。
Code
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, a1[100007], a2[100007];
long long sum[3][100007];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%d", &a1[i]);
a2[i] = a1[i];
}
sort(a2 + 1, a2 + n + 1);
for(int i = 1; i <= n; ++i)
sum[1][i] = sum[1][i - 1] + a1[i], sum[2][i] = sum[2][i - 1] + a2[i];
scanf("%d", &m);
while(m--) {
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
printf("%lld\n", sum[opt][r] - sum[opt][l - 1]);
}
return 0;
}
最新文章
- Core Java 总结(异常类问题)
- Util应用程序框架公共操作类(二):数据类型转换公共操作类(源码篇)
- [NOIP2010初赛]烽火传递+单调队列详细整理
- 数据结构作业——N!的位数(斯特灵公式)
- CentOS 编译安装 mysql
- PAT乙级真题1016.部分A+B(15)(2016-4-28)
- 关于上次我写的那个ATM程序 ,程序没有什么错,但是有些麻烦,两个类中有好多成员函数重复,因此我把ATM重新写了一边。
- windows下RabbitMQ 监控
- 【PostgreSQL】PostgreSQL语法
- 轻量级的移动框架--zepto.js
- Azure Messaging-ServiceBus Messaging消息队列技术系列-索引篇
- golang使用http client发起get和post请求示例
- nginx rewrite 指令
- Python入门 序列章
- P4822 [BJWC2012]冻结
- adb server is out of date ADB server didn&#39;t ACK * failed to start daemon *一种解决方式
- 使用Navicat导入excel表
- linux内核分析 第五周读书笔记
- Python入门1(简介、安装)
- 在系统中使用read函数读取文件内容
热门文章
- Vue3学习与实战 &#183; 全局挂载使用Axios
- html+css第三篇
- SSM(Spring-MyBatis-SpringMVC)框架整合【完整版】
- Sentry 监控 - Snuba 数据中台本地开发环境配置实战
- MYSQL5.8-----4
- python爬虫之正则表达式(用在其他地方也可)
- php操作mongodb手册地址
- 零基础学习java------day5------do....while循环、嵌套、方法(函数)
- JavaScript的数据结构快速学-链表的实现
- class.getName()和class.getSimpleName()的区别