当前位置: 首页 > news >正文

【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 1xn) 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+1an,a1,a2ax1. 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 1t104) — 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 1n,q2105) — 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 1ai106).

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 1lrn2) — 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 2105 and the sum of q q q does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105.

输出格式

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

​ 别的不说&#xff0c;GPT4用来看代码很是很爽的&#xff0c;可以让他直接恢复出函数中的数学公式&#xff0c;有的时候为了做笔记&#xff0c;GPT4回复的答案&#xff0c;复制出来使markdown、letax等格式&#xff0c;为了更好的记笔记&#xff0c;可以使用下面的工具将复制…...

vscode调试编译找不到gcc,只有cl,但是检查cmd是对的,控制面板的路径也更改了

&#x1f3c6;本文收录于《全栈Bug调优(实战版)》专栏&#xff0c;主要记录项目实战过程中所遇到的Bug或因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&am…...

空间解析几何5-空间圆到平面的距离【附MATLAB代码】

目录 理论公式 matlab代码 理论公式 matlab代码 function [dis,P,Q,L]Circle2PlaneDistance(T,R,n,Pn) % output % dis 为最短距离&#xff0c;P为距离最短时圆上的点 Q为P对应的投影点 L为最小值有几个 % input % T为园心到基坐标系的变换矩阵 R为圆半径 n为平面的单位法向…...

[已解决] pycharm添加本地conda虚拟环境 + 配置解释器 - pycharm找不到conda可执行文件

目录 问题&#xff1a; 方法&#xff1a; 补充&#xff1a;创建conda虚拟环境 参考文档&#xff1a;pycharm找不到conda可执行文件怎么办&#xff1f;-CSDN 问题&#xff1a; 1.显示&#xff1a;未为项目配置 Python 解释器 2.想在pycharm中使用本地创建的虚拟环境 方法&a…...

SENT - Single Edge Nibble Transmission for Automotive

SENT 总线的特征和优势 SENT 总线是一种数字信号传输协议&#xff0c;具有更高的传输精度和速度&#xff1b;SENT 总线是单线传输数据&#xff0c;减少信号线&#xff0c;降低成本。加上电源和地线&#xff0c;总共 3 线&#xff1b;SENT 总线具有更强大的诊断功能&#xff1b;…...

2024年软件设计师中级(软考中级)详细笔记【7】面向对象技术(下)23种设计模式(分值10+)

目录 前言阅读前必看 第七章 面向对象技术&#xff08;下&#xff09;7.3 设计模式&#xff08;固定4分&#xff09;7.3.1 设计模式的要素7.3.2 创建型设计模式7.3.2.1 Abstract Factory&#xff08;抽象工厂&#xff09;7.3.2.2 Builder&#xff08;生成器&#xff09;7.3.2.3…...

未来人工智能的发展对就业市场的影响 人工智能在生活中的相关

人工智能&#xff08;Artificial Intelligence&#xff09;&#xff0c;英文缩写为AI.是新一轮科技革命和产业变革的重要驱动力量&#xff0c; 是研究、开发用于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学. 人工智能的发展对就业市场的影响主要…...

Oracle EBS 中财务模块

Oracle E-Business Suite (EBS) 提供了全面的财务管理解决方案&#xff0c;涵盖了企业财务活动的各个方面。以下是EBS中主要的财务模块及其功能概述&#xff1a; 总账&#xff08;General Ledger, GL&#xff09;&#xff1a;Oracle EBS 中 GL 模块的财务流程概览-CSDN博客 总账…...

基于SSM公廉租房维保系统的设计

管理员账户功能包括&#xff1a;系统首页&#xff0c;个人中心&#xff0c;业主管理&#xff0c;维修单位管理&#xff0c;房屋信息管理&#xff0c;维修申报管理&#xff0c;维修完成&#xff0c;房屋维护管理 业主账号功能包括&#xff1a;系统首页&#xff0c;个人中心&…...

【AI大模型】深入Transformer架构:解码器部分的实现与解析

目录 &#x1f354; 解码器介绍 &#x1f354; 解码器层 2.1 解码器层的作用 2.2 解码器层的代码实现 2.3 解码器层总结 &#x1f354; 解码器 3.1 解码器的作用 3.2 解码器的代码分析 3.3 解码器总结 学习目标 &#x1f340; 了解解码器中各个组成部分的作用. &#…...

前端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包呢

下载地址&#xff1a;https://pkgs.org/和https://rpmfind.net/linux/rpm2html/search.php 根基自己的需要进行下载使用。...

Android TextView实现一串文字特定几个字改变颜色

遇到一个需求&#xff0c;让Android端实现给定一个字符串指定下标的几个字颜色与其他字颜色不一致。 主要是用ForegroundColorSpan这个API来传入颜色值&#xff0c;用SpannableString来设置指定索引下标的字的颜色值。 这里通过给定一个输入文字描述框&#xff0c;要求输入指定…...

桃子叶片病害分类检测数据集(猫脸码客 第221期)

桃子叶片病害分类检测数据集 一、引言 桃子作为世界上广泛种植的果树之一&#xff0c;其叶片的健康状况直接关系到果实的产量和品质。然而&#xff0c;桃子叶片易受多种病害的侵袭&#xff0c;这些病害不仅影响叶片的光合作用&#xff0c;还可能导致果实减产、品质下降&#…...

Vue--》掌握自定义依赖引入的最佳实践

在现代前端开发中&#xff0c;vue凭借其灵活性和高效性&#xff0c;已成为开发者们的宠儿&#xff0c;然而随着项目的复杂度提升&#xff0c;如何高效地管理和引入依赖&#xff0c;尤其是自定义引入依赖&#xff0c;成为了许多开发者面临的一大挑战。无论是为了优化加载速度&am…...

repo 命令大全详解(第十四篇 repo overview)

repo overview 命令用于显示当前项目的概览信息&#xff0c;帮助用户快速了解项目的状态和分支信息。 参数分类及解释 基本参数 [--current-branch]: 可选&#xff0c;仅考虑已检出的分支。 示例: repo overview --current-branch [<project>...]: 可选&#xff0c;指定…...

【设计模式】深入理解Python中的抽象工厂设计模式

深入理解Python中的抽象工厂设计模式 设计模式是软件开发中解决常见问题的经典方案&#xff0c;而**抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09;**是其中非常重要的一种创建型模式。抽象工厂模式的主要作用是提供一个接口&#xff0c;创建一系列相关或依赖…...

网站建设完成后,多久需要升级迭代一次

网站建设完成后&#xff0c;一般每隔几个月就会进行一次迭代升级。以下是关于网站迭代周期和原因的具体分析&#xff1a; 更新频率&#xff1a;网站在建设完成后&#xff0c;一般每隔几个月就会进行一次迭代升级。这种周期性的更新有助于保持网站的现代感和竞争力。更新目的&a…...

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字

这里写目录标题 问题详情分析问题代码展示 问题详情 剑指 Offer 56&#xff1a; 一个整型数组 nums 里除两个数字之外&#xff0c;其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)&#xff0c;空间复杂度是O(1)。 示例&#xff1a; 输入&a…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...