首页 > 其他分享 >AcWing795.前缀和

AcWing795.前缀和

时间:2023-05-14 17:44:06浏览次数:68  
标签:AcWing795 前缀 int 询问 include 输入 1000

输入一个长度为n的整数序列。

接下来再输入m个询问,每个询问输入一对l,r。

对于每个询问,输出原序列中第l个数到第r个数的和。

数据范围

1≤l≤r≤n,

1≤n,m≤100000,

-1000≤数列中元素的值≤1000。

 

#include <iostream>  //C++标准库中的头文件.用于控制台输入和输出。
#include <cstring>   //用于处理字符串的函数和操作
#include <algorithm> //提供了许多常用的算法函数,用于对数据进行排序、查找、变换和操作等操作。
using namespace std; // 这一句也不能少
const int N = 100010;

int n, m;
int q[N];
int sum[N];

int main()
{
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &q[i]);
        sum[i] = sum[i - 1] + q[i];
    }
    while (m--)
    {
        int l, r;
        scanf("%d %d", &l, &r);
        printf("%d\n", sum[r] - sum[l - 1]);
    }
}

 

标签:AcWing795,前缀,int,询问,include,输入,1000
From: https://www.cnblogs.com/gjkt2001/p/17399724.html

相关文章

  • 中二羊专题:栋栋的入门题(前缀和)
    原题标题虽然是栋栋的入门题,但它并不是入门题。原题的题目描述是:给出N个整数,以及M个求和范围,求出每一个范围的数字的和。提示:显然,这并不是一道入门题。这就要用到一种新的思想:前缀思想。进入正题数组\(a\)(此处方便讲解,忽略下标\(0\))有这\(5\)个数字:\(1,3,2,1,5\)......
  • 前缀和
    一、问题描述输入一个长度为 n� 的整数序列。接下来再输入 m� 个询问,每个询问输入一对 l,r�,�。对于每个询问,输出原序列中从第 l� 个数到第 r� 个数的和。输入格式第一行包含两个整数 n� 和 m�。第二行包含 n� 个整数,表示整数数列。接下来 m� 行,每行包含两个整数 l�......
  • 洛谷 P5488 差分与前缀和
    洛谷传送门看起来很毒瘤,但是推出贡献系数后就是一个朴素的卷积了。首先考虑前缀和。考虑\(j\(j\lei)\)的\(a_j\)贡献到\(i\)的过程,是找到\(j=p_0\lep_1\le\cdots\lep_k=i\)的方案数。令\(x_i=p_i-p_{i-1}\),即求\(x_i\ge0,\sum\limits_{i=1}^kx_i......
  • C语言刷leetcode——前缀和
    目录前缀和概述刷题560.和为K的子数组523.连续的子数组和974.和可被K整除的子数组前缀和概述https://zhuanlan.zhihu.com/p/436526162刷题560.和为K的子数组523.连续的子数组和974.和可被K整除的子数组......
  • 根据前缀生成指定范围内的MAC地址
    6进制递增,批处理一键生成指定范围的MAC地址可以经过适当的修改,实现10进制、二进制、8进制的类似效果使用方法:将以下代码复制后,保存为*.bat批处理文件即可执行;或者新建一个记事本文件,将复制的代码粘贴进去,然后将文件名后缀改为*.bat,双击即可执行;批处理内容:@echoofftitleMA......
  • 前缀和及其应用
    1.定义数组a=[1,2,3,4,5],我们维护一个由前缀的和组成的数组sum,sum[i]表示数组中a[0]~a[i]的和。sum[0]=a[0]sum[1]=a[0]+a[1]sum[2]=a[0]+a[1]+a[2]sum[3]=a[0]+a[1]+a[2]+a[3]sum数组就被称为前缀和数组。2.应用前缀和的最主要目的就是求子数组的......
  • 「模板」前缀和
    阿巴阿巴阿巴输入n个数,给出m个询问,询问区间[x,y]的和。输入第一行为n和m,1<=n,m<=100000接下来一行为n个数,范围在0~100000之间接下来m行,每行两个数x,y,输出第x个数到第y个数之间所有数的和。保证x<=y输出m个数tips:1#include<bits/stdc++.h>2usingnamespacestd;3......
  • 前缀和
    前缀和一、介绍前缀,顾名思义就是一个东西前面的点缀...(bushi其实打比方来说就是:假如有一字符串ABCD,那么他的前缀就是A、AB、ABC、ABCD这四个从新从第一个字母一次往后开始拼接的字符串。当然这是字符串。但前缀和一般应用于数组,对于给定的数组a=[1,2,3,4],他的前i项和sum[i]......
  • 判断网卡MAC地址前缀
    我们的电脑上现在可是很多的网卡,因为存在虚拟网卡,Lan口和wifi网卡等等。之前有人给出判断的前缀,但是不够完整。可以从这里下载完整的资料。1)先由GetAdaptersInfo获取所有网卡的基本信息。然后利用网卡名去注册表中查找对应的硬件信息。若是物理网卡,其硬件信息中通常会包含PCI。......
  • D. Remove One Element(前缀最大+简单状态机)
    题目D.RemoveOneElement题意输入n(2≤n≤2e5)和长为n的数组a(1≤a[i]≤1e9)。从a中去掉一个数(也可以不去掉)。输出a的最长严格递增连续子数组的长度。思路一种方法是前缀最长和后缀最长,加起来。这种方法比较简单。用状态机来写,定义f[i][0/1]分别表示前缀......