type
status
date
slug
summary
tags
category
icon
password
今日复习一下前缀和的知识，前缀和就是一个数组记录着原数组这个位置及以前的所有值的和，先来一个板子题说明一下：
例题一：
众所周知，狮均国内吼叫总值（Real GDS per lion）是衡量一个狮子国狮子健康程度的重要指标。
其计算方法为：选取若干个狮子，将每个狮子吼叫的次数相加即为总值。
叶子是狮子国健康委员会的会长，有人举报小林汇报的狮均国内吼叫总值的数据有误，所以他想请你帮忙计算。
具体来说，你会知道编号为 11 到 nn 的 nn 只狮子吼叫的次数 aiai。
叶子会提出 qq 个问题。对于每个问题他会给出 ll 和 rr。
他想知道编号在 ll 和 rr 之间的狮子的狮均国内吼叫总值。
输入格式
第一行一个整数 nn，代表狮子的数量。
第二行 nn 个整数 aiai，代表编号为 ii 的狮子的吼叫次数。
第三行一个整数 qq，代表叶子的问题数。
第四到第 3+q3+q 行，每行两个整数 l,rl,r。
输出格式
qq 行整数，代表计算出来的狮均国内吼叫总值。
数据范围
50%50% 的数据 q=1q=1;
100%100% 的数据: 1≤n≤106,1≤ai≤103,1≤q≤105,1≤l≤r≤n1≤n≤106,1≤ai≤103,1≤q≤105,1≤l≤r≤n。
输入样例：
输出样例：
题解：
重点：
关键是前缀和的算法以及情况的区分
例题二：
- ‣
一个环形高速公路上有 NN 个出口，共有 MM 次询问，每次询问你需要回答其中两个出口之间的最短距离是多少。
输入格式
第一行首先包含一个整数 NN，接下来包含 NN 个整数 D1,D2,…,DND1,D2,…,DN，其中 DiDi 是第 ii 个出口与第 i+1i+1 个出口之间的距离，DNDN 是第 NN 个出口与第 11 个出口之间的距离。
第二行包含一个整数 MM，表示询问次数。
接下来 MM 行，每行包含两个整数，表示询问两个出口之间的最短距离。
输出格式
共 MM 行，每行输出一个查询的答案。
数据范围
3≤N≤1053≤N≤105,
1≤M≤1041≤M≤104,
高速公路总长度不超过 107107。
输入样例：
输出样例：
题解：
重点：
重点是发现倒序的求法是怎么计算的，用周长减去正序的就是答案
还有一个就是对于l>r的情况，进行反转
- Author:xiaowaaa
- URL:https://www.xiaowaaa.asia//article/11c5df8d-8884-8080-a6c8-c6a5ebbbee1c
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!