首页 > 其他分享 >中二羊专题:栋栋的入门题(前缀和)

中二羊专题:栋栋的入门题(前缀和)

时间:2023-05-14 11:13:42浏览次数:51  
标签:ch 前缀 中二羊 栋栋 int p1 ull +...+ buf

原题

标题虽然是栋栋的入门题,但它并不是入门题。
原题的题目描述是:

给出N个整数,以及M个求和范围,求出每一个范围的数字的和。

提示:显然,这并不是一道入门题。

这就要用到一种新的思想:前缀思想。

进入正题

数组 \(a\) (此处方便讲解,忽略下标 \(0\) )有这 \(5\) 个数字: \(1,3,2,1,5\) 。你求 \(a_1+...+a_3\) 是以下代码:

for(int i=1;i<=3;i++)ans+=a[i];

再假设数组 \(b\) 有 \(m\) 个数字。你需要求 \(b_x+...+b_y\) 。一般人用以下代码:

for(int i=x;i<=y;i++)ans+=b[i];

你有 \(n\) 次访问(即求 \(n\) 次从 \(b_x+...+b_y\) )。那么你代码应该会是这样:

for(int i=1;i<=n;i++){
	cin>>x>>y;
	for(int j=x;j<=y;j++)ans+=b[j];
}

但这样子太慢了。
但是我们还有一种方法解决。
我们可以令 \(c_i\) 为 \(b_1+b_2+...+b_i\) 。那么求 \(b_x+...+b_y\) 就非常快了。 \(c_y-c_{x-1}\) 。

解释

已知 \(c_y=b_1+...+b_y\) , \(c_x=b_1+...+b_x\) 。所以说(此处化简):
\(c_y-c_{x-1}=b_1+...+b_y-(b_1+...+b_{x-1})=b_x+...+b_y\) 。

代码

建议别抄。这里只是给一个例子。

#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cctype>
namespace FastIo{
    typedef unsigned long long ull;
    typedef __uint128_t L;
    static char buf[100000],*p1=buf,*p2=buf;
    #define gc p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++
    class FastMod{
        public:
            FastMod(ull b):b(b),m(ull((L(1)<<64)/b)){}
            ull reduce(ull a){
                ull q=(ull)((L(m)*a)>>64);
                ull r=a-q*b;
                return r>=b?r-b:r;
            }
        private:
            ull b,m;
    };
    FastMod QM(10);
    class QIO{
    	public:
    		inline void read(int &x){
    			x=0,ch=gc;
    			while(!isdigit(ch))ch=gc;
    			while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=gc;}
			}
			void write(int a){
				if(a>9)write(a/10);
				putchar(QM.reduce(a)^48);
			}
		private:
			char ch;
	};
	QIO qrw;
}
using namespace FastIo;
int a[1000001];
signed main(){
	register int i(1);
	int n,m,x,y;
	qrw.read(n);
	qrw.read(m);
	for(;i<=n;i=-~i){
		qrw.read(x);
		a[i]=a[i-1]+x;
	}
	for(i=1;i<=m;i=-~i){
		qrw.read(x);
		qrw.read(y);
		qrw.write(a[y]-a[x-1]);
		putchar('\n');
	}
    exit(0);
    return 0;
}

后记: \(N\) 年前的东西了,看个乐子就行了。

标签:ch,前缀,中二羊,栋栋,int,p1,ull,+...+,buf
From: https://www.cnblogs.com/SHOJYS/p/17398914.html

相关文章

  • 中二羊专题:栋栋吃糖果
    U163898题目题目背景栋栋参加比赛拿下了一等奖,老师奖励了很多糖果。题目描述一共有\(m\)种糖果,其中第i种糖果的数量为\(m_i\)。栋栋吃糖时会获得快乐值,并且他喜欢换着口味吃糖。当栋栋吃下第一个糖果时快乐值为\(0\),接下来,每吃一个不同口味的糖果(与上一个糖不同),快乐......
  • 前缀和
    一、问题描述输入一个长度为 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]分别表示前缀......