【Codeforces】CF 2009 F
Firefly’s Queries
#前缀和 #数据结构 #数学
题目描述
Firefly is given an array a a a of length n n n. Let c i c_i ci denote the i i i’th cyclic shift ∗ ^{\text{∗}} ∗ of a a a. She creates a new array b b b such that b = c 1 + c 2 + ⋯ + c n b = c_1 + c_2 + \dots + c_n b=c1+c2+⋯+cn where + + + represents concatenation † ^{\text{†}} †.
Then, she asks you q q q queries. For each query, output the sum of all elements in the subarray of b b b that starts from the l l l-th element and ends at the r r r-th element, inclusive of both ends.
∗ ^{\text{∗}} ∗The x x x-th ( 1 ≤ x ≤ n 1 \leq x \leq n 1≤x≤n) cyclic shift of the array a a a is a x , a x + 1 … a n , a 1 , a 2 … a x − 1 a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1} ax,ax+1…an,a1,a2…ax−1. Note that the 1 1 1-st shift is the initial a a a.
† ^{\text{†}} †The concatenation of two arrays p p p and q q q of length n n n (in other words, p + q p + q p+q) is p 1 , p 2 , . . . , p n , q 1 , q 2 , . . . , q n p_1, p_2, ..., p_n, q_1, q_2, ..., q_n p1,p2,...,pn,q1,q2,...,qn.
输入格式
The first line contains t t t ( 1 ≤ t ≤ 1 0 4 1 \leq t \leq 10^4 1≤t≤104) — the number of test cases.
The first line of each test case contains two integers n n n and q q q ( 1 ≤ n , q ≤ 2 ⋅ 1 0 5 1 \leq n, q \leq 2 \cdot 10^5 1≤n,q≤2⋅105) — the length of the array and the number of queries.
The following line contains n n n integers a 1 , a 2 , . . . , a n a_1, a_2, ..., a_n a1,a2,...,an ( 1 ≤ a i ≤ 1 0 6 1 \leq a_i \leq 10^6 1≤ai≤106).
The following q q q lines contain two integers l l l and r r r ( 1 ≤ l ≤ r ≤ n 2 1 \leq l \leq r \leq n^2 1≤l≤r≤n2) — the left and right bounds of the query.
Note that the large inputs may require the use of 64-bit integers.
It is guaranteed that the sum of n n n does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105 and the sum of q q q does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.
输出格式
For each query, output the answer on a new line.
样例 #1
样例输入 #1
5
3 3
1 2 3
1 9
3 5
8 8
5 5
4 8 3 2 4
1 14
3 7
7 10
2 11
1 25
1 1
6
1 1
5 7
3 1 6 10 4
3 21
6 17
2 2
1 5
1 14
9 15
12 13
5 3
4 9 10 10 1
20 25
3 11
20 22
样例输出 #1
18
8
1
55
20
13
41
105
6
96
62
1
24
71
31
14
44
65
15
解法
解题思路
可以发现,每次移动会改变相对位置,但是不会改变大小之和,而相对位置其实就是一个环。
我们可以把数组复制一遍变成环,化环为链,计算一遍前缀和。
而每次询问相当于询问固定的几个环,加上一个不完整的环,这个不完整的环就可以使用之前计算的前缀和来完成。
代码
void solve() {int n,q;cin >> n >> q;vector<int>a(n + 1), prefix(2 * n + 1);for (int i = 1; i <= n; ++i) {cin >> a[i];prefix[i] = prefix[i - 1] + a[i];}int s = prefix[n];for (int i = 1; i <= n; ++i) {prefix[n + i] = prefix[n + i - 1] + a[i];}auto cal = [&](int r)->int{int len = r / n, x = r % n;int L = len + 1, R = L + x - 1;int sum = len * s + prefix[R] - prefix[L - 1];return sum;};while (q--) {int l, r;cin >> l >> r;int res = cal(r);res -= cal(l-1);std::cout << res << "\n";}
}signed main() {ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;cin >> t;while (t--) {solve();}
};
相关文章:
【Codeforces】CF 2009 F
Firefly’s Queries #前缀和 #数据结构 #数学 题目描述 Firefly is given an array a a a of length n n n. Let c i c_i ci denote the i i i’th cyclic shift ∗ ^{\text{∗}} ∗ of a a a. She creates a new array b b b such that b c 1 c 2 ⋯ c n b c…...
GTP4聊天记录中letax保存为word
别的不说,GPT4用来看代码很是很爽的,可以让他直接恢复出函数中的数学公式,有的时候为了做笔记,GPT4回复的答案,复制出来使markdown、letax等格式,为了更好的记笔记,可以使用下面的工具将复制…...
vscode调试编译找不到gcc,只有cl,但是检查cmd是对的,控制面板的路径也更改了
🏆本文收录于《全栈Bug调优(实战版)》专栏,主要记录项目实战过程中所遇到的Bug或因后果及提供真实有效的解决方案,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&am…...
空间解析几何5-空间圆到平面的距离【附MATLAB代码】
目录 理论公式 matlab代码 理论公式 matlab代码 function [dis,P,Q,L]Circle2PlaneDistance(T,R,n,Pn) % output % dis 为最短距离,P为距离最短时圆上的点 Q为P对应的投影点 L为最小值有几个 % input % T为园心到基坐标系的变换矩阵 R为圆半径 n为平面的单位法向…...
[已解决] pycharm添加本地conda虚拟环境 + 配置解释器 - pycharm找不到conda可执行文件
目录 问题: 方法: 补充:创建conda虚拟环境 参考文档:pycharm找不到conda可执行文件怎么办?-CSDN 问题: 1.显示:未为项目配置 Python 解释器 2.想在pycharm中使用本地创建的虚拟环境 方法&a…...
SENT - Single Edge Nibble Transmission for Automotive
SENT 总线的特征和优势 SENT 总线是一种数字信号传输协议,具有更高的传输精度和速度;SENT 总线是单线传输数据,减少信号线,降低成本。加上电源和地线,总共 3 线;SENT 总线具有更强大的诊断功能;…...
2024年软件设计师中级(软考中级)详细笔记【7】面向对象技术(下)23种设计模式(分值10+)
目录 前言阅读前必看 第七章 面向对象技术(下)7.3 设计模式(固定4分)7.3.1 设计模式的要素7.3.2 创建型设计模式7.3.2.1 Abstract Factory(抽象工厂)7.3.2.2 Builder(生成器)7.3.2.3…...
未来人工智能的发展对就业市场的影响 人工智能在生活中的相关
人工智能(Artificial Intelligence),英文缩写为AI.是新一轮科技革命和产业变革的重要驱动力量, 是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学. 人工智能的发展对就业市场的影响主要…...
Oracle EBS 中财务模块
Oracle E-Business Suite (EBS) 提供了全面的财务管理解决方案,涵盖了企业财务活动的各个方面。以下是EBS中主要的财务模块及其功能概述: 总账(General Ledger, GL):Oracle EBS 中 GL 模块的财务流程概览-CSDN博客 总账…...
基于SSM公廉租房维保系统的设计
管理员账户功能包括:系统首页,个人中心,业主管理,维修单位管理,房屋信息管理,维修申报管理,维修完成,房屋维护管理 业主账号功能包括:系统首页,个人中心&…...
【AI大模型】深入Transformer架构:解码器部分的实现与解析
目录 🍔 解码器介绍 🍔 解码器层 2.1 解码器层的作用 2.2 解码器层的代码实现 2.3 解码器层总结 🍔 解码器 3.1 解码器的作用 3.2 解码器的代码分析 3.3 解码器总结 学习目标 🍀 了解解码器中各个组成部分的作用. &#…...
前端html js css 基础巩固3
一个这样的首页 滑动显示 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title>&l…...
如在下载自己的需要的rmp包呢
下载地址:https://pkgs.org/和https://rpmfind.net/linux/rpm2html/search.php 根基自己的需要进行下载使用。...
Android TextView实现一串文字特定几个字改变颜色
遇到一个需求,让Android端实现给定一个字符串指定下标的几个字颜色与其他字颜色不一致。 主要是用ForegroundColorSpan这个API来传入颜色值,用SpannableString来设置指定索引下标的字的颜色值。 这里通过给定一个输入文字描述框,要求输入指定…...
桃子叶片病害分类检测数据集(猫脸码客 第221期)
桃子叶片病害分类检测数据集 一、引言 桃子作为世界上广泛种植的果树之一,其叶片的健康状况直接关系到果实的产量和品质。然而,桃子叶片易受多种病害的侵袭,这些病害不仅影响叶片的光合作用,还可能导致果实减产、品质下降&#…...
Vue--》掌握自定义依赖引入的最佳实践
在现代前端开发中,vue凭借其灵活性和高效性,已成为开发者们的宠儿,然而随着项目的复杂度提升,如何高效地管理和引入依赖,尤其是自定义引入依赖,成为了许多开发者面临的一大挑战。无论是为了优化加载速度&am…...
repo 命令大全详解(第十四篇 repo overview)
repo overview 命令用于显示当前项目的概览信息,帮助用户快速了解项目的状态和分支信息。 参数分类及解释 基本参数 [--current-branch]: 可选,仅考虑已检出的分支。 示例: repo overview --current-branch [<project>...]: 可选,指定…...
【设计模式】深入理解Python中的抽象工厂设计模式
深入理解Python中的抽象工厂设计模式 设计模式是软件开发中解决常见问题的经典方案,而**抽象工厂模式(Abstract Factory Pattern)**是其中非常重要的一种创建型模式。抽象工厂模式的主要作用是提供一个接口,创建一系列相关或依赖…...
网站建设完成后,多久需要升级迭代一次
网站建设完成后,一般每隔几个月就会进行一次迭代升级。以下是关于网站迭代周期和原因的具体分析: 更新频率:网站在建设完成后,一般每隔几个月就会进行一次迭代升级。这种周期性的更新有助于保持网站的现代感和竞争力。更新目的&a…...
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字
这里写目录标题 问题详情分析问题代码展示 问题详情 剑指 Offer 56: 一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 示例: 输入&a…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
OpenLayers 可视化之热力图
注:当前使用的是 ol 5.3.0 版本,天地图使用的key请到天地图官网申请,并替换为自己的key 热力图(Heatmap)又叫热点图,是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...
基于大模型的 UI 自动化系统
基于大模型的 UI 自动化系统 下面是一个完整的 Python 系统,利用大模型实现智能 UI 自动化,结合计算机视觉和自然语言处理技术,实现"看屏操作"的能力。 系统架构设计 #mermaid-svg-2gn2GRvh5WCP2ktF {font-family:"trebuchet ms",verdana,arial,sans-…...
树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法
树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源: http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作,无需更改相机配置。但是,一…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Python爬虫(二):爬虫完整流程
爬虫完整流程详解(7大核心步骤实战技巧) 一、爬虫完整工作流程 以下是爬虫开发的完整流程,我将结合具体技术点和实战经验展开说明: 1. 目标分析与前期准备 网站技术分析: 使用浏览器开发者工具(F12&…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制
在数字化浪潮席卷全球的今天,数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具,在大规模数据获取中发挥着关键作用。然而,传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时,常出现数据质…...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
LOOI机器人的技术实现解析:从手势识别到边缘检测
LOOI机器人作为一款创新的AI硬件产品,通过将智能手机转变为具有情感交互能力的桌面机器人,展示了前沿AI技术与传统硬件设计的完美结合。作为AI与玩具领域的专家,我将全面解析LOOI的技术实现架构,特别是其手势识别、物体识别和环境…...
