首页/新闻资讯/正文详情

题解:AcWing 246 区间最大公约数

发布时间:2026/11/19 9:15:24 来源:云帆数科 栏目:资讯中心
题解:AcWing 246 区间最大公约数
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AcWing246. 区间最大公约数 - AcWing题库【题目描述】给定一个长度为N NN的数列A AA以及M MM条指令每条指令可能是以下两种之一C l r d表示把A [ l ] , A [ l 1 ] , … , A [ r ] A[l],A[l1],…,A[r]A[l],A[l1],…,A[r]都加上d dd。Q l r表示询问A [ l ] , A [ l 1 ] , … , A [ r ] A[l],A[l1],…,A[r]A[l],A[l1],…,A[r]的最大公约数G C D GCDGCD)。对于每个询问输出一个整数表示答案。【输入】第一行两个整数N , M N,MN,M。第二行N NN个整数A [ i ] A[i]A[i]。接下来M MM行表示M MM条指令每条指令的格式如题目描述所示。【输出】对于每个询问输出一个整数表示答案。每个答案占一行。【输入样例】5 5 1 3 5 7 9 Q 1 5 C 1 5 1 Q 1 5 C 3 3 6 Q 2 4【输出样例】1 2 4【核心思想】问题分析给定长度为N NN的数列A AA以及M MM条指令支持区间[ l , r ] [l, r][l,r]加d dd和查询区间[ l , r ] [l, r][l,r]的最大公约数。关键在于如何在区间修改的同时高效维护区间 GCD。算法选择差分数组Difference Array将区间加法转化为差分数组的单点修改实现O ( 1 ) O(1)O(1)区间标记线段树Segment Tree维护差分数组的区间 GCD支持单点修改和区间 GCD 查询树状数组Fenwick Tree维护差分数组的前缀和用于快速查询A [ l ] A[l]A[l]的值数学性质利用gcd ⁡ ( a 1 , a 2 , . . . , a n ) gcd ⁡ ( a 1 , a 2 − a 1 , a 3 − a 2 , . . . , a n − a n − 1 ) \gcd(a_1, a_2, ..., a_n) \gcd(a_1, a_2-a_1, a_3-a_2, ..., a_n-a_{n-1})gcd(a1​,a2​,...,an​)gcd(a1​,a2​−a1​,a3​−a2​,...,an​−an−1​)的性质将区间 GCD 转化为差分数组的 GCD关键步骤初始化读取N NN数组长度、M MM指令数、A [ 1.. N ] A[1..N]A[1..N]初始数组构建差分数组b [ i ] A [ i ] − A [ i − 1 ] b[i] A[i] - A[i-1]b[i]A[i]−A[i−1]其中b [ 1 ] A [ 1 ] b[1] A[1]b[1]A[1]树状数组初始化将差分数组b [ i ] b[i]b[i]加入树状数组支持前缀和查询得到A [ i ] A[i]A[i]线段树建立维护差分数组b bb的区间 GCD处理查询指令Q l r通过树状数组前缀和查询A [ l ] ∑ i 1 l b [ i ] A[l] \sum_{i1}^{l} b[i]A[l]∑i1l​b[i]通过线段树查询gcd ⁡ ( b [ l 1 ] , b [ l 2 ] , . . . , b [ r ] ) \gcd(b[l1], b[l2], ..., b[r])gcd(b[l1],b[l2],...,b[r])答案为gcd ⁡ ( A [ l ] , gcd ⁡ ( b [ l 1.. r ] ) ) \gcd(A[l], \gcd(b[l1..r]))gcd(A[l],gcd(b[l1..r]))即gcd ⁡ ( A [ l . . r ] ) \gcd(A[l..r])gcd(A[l..r])若l r l rlr直接输出∣ A [ l ] ∣ |A[l]|∣A[l]∣处理修改指令C l r d树状数组单点修改add(l, d)和add(r1, -d)线段树单点更新update(l, d)和update(r1, -d)若r 1 ≤ n r1 \leq nr1≤n时间/空间复杂度时间复杂度O ( ( N M ) log ⁡ N ) O((N M) \log N)O((NM)logN)线段树和树状数组操作均为O ( log ⁡ N ) O(\log N)O(logN)空间复杂度O ( N ) O(N)O(N)线段树4 N 4N4N 树状数组N NN 原数组线段树维护 GCD 的核心思想差分降维利用gcd ⁡ ( A [ l . . r ] ) gcd ⁡ ( A [ l ] , gcd ⁡ ( b [ l 1.. r ] ) ) \gcd(A[l..r]) \gcd(A[l], \gcd(b[l1..r]))gcd(A[l..r])gcd(A[l],gcd(b[l1..r]))的数学性质将区间修改下的区间 GCD 查询转化为差分数组的区间 GCD 查询区间修改转单点修改对原数组区间[ l , r ] [l, r][l,r]加d dd等价于对差分数组b [ l ] d b[l] db[l]d、b [ r 1 ] − d b[r1] - db[r1]−d仅影响两个端点线段树维护 GCD父节点的 GCD 等于左右子节点 GCD 的 GCD即gcd ⁡ ( l . v , r . v ) \gcd(l.v, r.v)gcd(l.v,r.v)树状数组维护前缀和通过前缀和还原原数组的值A [ l ] A[l]A[l]用于与差分 GCD 合并得到最终答案适用于区间加减与区间 GCD 查询类问题【算法标签】#线段树【代码详解】#includebits/stdc.husingnamespacestd;#defineintlonglong// 将 int 定义为 long long防止数值溢出constintN500005;// 最大数组长度intn,m;// n: 数组长度, m: 指令数intw[N];// 原数组inttr1[N];// 树状数组维护差分数组的前缀和structNode{intl,r,v;// 区间左右端点、区间差分数组的GCD值}tr[N*4];// 线段树数组4倍空间// 树状数组lowbit运算提取x的最低位1对应的2次幂数intlowbit(intx){returnx-x;}// 树状数组单点修改向后修在位置x加上cvoidadd(intx,intc){for(intix;in;ilowbit(i))tr1[i]c;}// 树状数组前缀查询向前查查询[1,x]的和intsum(intx){intres0;for(intix;i;i-lowbit(i))restr1[i];returnres;}// 辗转相除法求GCDintgcd(inta,intb){returnb?gcd(b,a%b):a;}// 线段树向上更新父节点的v 左右子节点v的GCDvoidpushup(intu){autoroottr[u],ltr[u1],rtr[u1|1];tr[u].vgcd(l.v,r.v);}// 线段树建立维护差分数组b[i] w[i] - w[i-1]的GCDvoidbuild(intu,intl,intr){if(lr)// 叶子节点tr[u]{l,r,w[r]-w[r-1]};// 差分数组的值else{tr[u]{l,r};// 初始化当前节点的区间范围intmidlr1;// 取中点等价于 (lr)/2build(u1,l,mid),build(u1|1,mid1,r);// 递归建立左右子树pushup(u);// 向上更新当前节点}}// 线段树区间查询GCDintquery(intu,intl,intr){if(tr[u].lltr[u].rr)// 当前节点区间完全包含在查询区间内returntr[u].v;intmidtr[u].ltr[u].r1;// 取中点intv0;if(lmid)vquery(u1,l,r);// 左子树有贡献if(rmid)vgcd(v,query(u1|1,l,r));// 右子树有贡献与左子树结果取GCDreturnv;}// 线段树单点修改在差分数组位置pos加上dvoidupdate(intu,intpos,intd){if(tr[u].ltr[u].r)// 叶子节点{tr[u].vd;// 差分数组的值增加dreturn;}intmidtr[u].ltr[u].r1;// 取中点if(posmid)update(u1,pos,d);// 在左子树elseupdate(u1|1,pos,d);// 在右子树pushup(u);// 修改后向上更新}signedmain()// 使用 signed 替代 int因为 #define int long long{cinnm;// 读入数组长度和指令数for(inti1;in;i)cinw[i];// 读入原数组// 初始化树状数组将差分数组 b[i] w[i] - w[i-1] 加入树状数组for(inti1;in;i)add(i,w[i]-w[i-1]);build(1,1,n);// 建立线段树维护差分数组区间为[1, n]charop;intl,r,d;while(m--)// 依次处理每条指令{cinop;if(opQ)// 查询指令{cinlr;intleftsum(l);// 树状数组查询A[l]的值差分数组前缀和intrightquery(1,l1,r);// 线段树查询差分数组[l1, r]的GCDif(lr)// 区间长度为1coutabs(left)endl;// 直接输出A[l]的绝对值else// GCD(A[l..r]) GCD(A[l], GCD(b[l1], b[l2], ..., b[r]))// 其中 b[i] A[i] - A[i-1] 为差分数组coutabs(gcd(left,right))endl;}else// 修改指令{cinlrd;// 树状数组区间加d转化为差分数组的两个单点修改add(l,d);add(r1,-d);// 线段树同步更新差分数组的两个端点update(1,l,d);if(r1n)// 注意线段树建到了nupdate(1,r1,-d);}}return0;}【运行结果】5 5 1 3 5 7 9 Q 1 5 1 C 1 5 1 Q 1 5 2 C 3 3 6 Q 2 4 4

相关推荐

局部敏感哈希(LSH)
局部敏感哈希(LSH)

概述 欧式空间中,将高维空间的点映射到低维空间,原本接近的点在低维空间中肯定依然接近,但原本远离的点则有一定概率变成接近的点。 这句话的意思是,在欧氏空间中,使用随机投影等降维映射时,原本距离较近的… · 2026/11/13 6:39:37

Python基础学习-13
Python基础学习-13

一、面向对象编程入门 1、知识点 为什么要面向对象? 面向对象编程(OOP)的核心思想是:把数据和处理数据的方法打包在一起,形成一个"对象"。就像现实世界中,一辆车既有属性(颜色、速度、… · 2026/11/12 16:39:45

C++并发编程:std::lock_guard与std::unique_lock深度解析与应用实战
C++并发编程:std::lock_guard与std::unique_lock深度解析与应用实战

1. 项目概述:为什么C并发编程绕不开锁管理?干了这么多年C后台开发,我敢说,但凡涉及到多线程、高并发,锁就是你永远绕不过去的一道坎。新手一上来,可能觉得std::mutex一锁了事,简单粗暴。但真到了… · 2026/11/15 11:11:47

重庆网上报考电工证最新政策解读 内部消息透露外省证书可转
重庆网上报考电工证最新政策解读 内部消息透露外省证书可转

重庆网上报考电工证最新政策解读 内部消息透露外省证书可转 之前考的证在外省能不能转过来?这是很多在外地打工、想回重庆发展、或者已经在重庆工作的电工最关心的问题。根据 内部消息 ,应急管理部近期在政策上有了新的变化,尤其是关于… · 2026/11/19 9:14:49

电工作业马凳证全国通用吗?官方报名入口在哪?急需特种作业证才能上岗找工作
电工作业马凳证全国通用吗?官方报名入口在哪?急需特种作业证才能上岗找工作

电工作业马凳证全国通用吗?官方报名入口在哪?急需特种作业证才能上岗找工作 你是不是正愁找不到电工相关的工作,因为单位要求必须有特种作业操作证?别急,今天就来聊聊【电工作业马凳】证的相关问题,带你理清报名、考试、复审和就业发展的一条龙流程。关… · 2026/11/19 9:14:49

监利市电工证报考全攻略:学历不高也能考,郑州报考避坑指南
监利市电工证报考全攻略:学历不高也能考,郑州报考避坑指南

监利市电工证报考全攻略:学历不高也能考,郑州报考避坑指南 你是不是也担心自己学历不高,连监利市电工证都报不上?别急,今天我就来给你讲明白,监利市电工证到底怎么考、怎么报、怎么避坑。咱们不绕弯子,直接上干货,看完你就知道怎么操作了。… · 2026/11/19 9:14:49

郑州报考避坑指南:最低级别的电工证怎么考才能上岗找工作
郑州报考避坑指南:最低级别的电工证怎么考才能上岗找工作

郑州报考避坑指南:最低级别的电工证怎么考才能上岗找工作 你正愁找不到工作,却发现没有特种作业证根本进不了门?别急,今天就来聊聊【最低级别的电工证】,这个证件到底值不值得考,怎么考最稳妥,还能让你少走弯路,避免踩郑州本地常见的报考陷阱。… · 2026/11/19 9:14:49

工地太忙根本没时间复习考试 电工证考试先交钱吗良心建议
工地太忙根本没时间复习考试 电工证考试先交钱吗良心建议

工地太忙根本没时间复习考试 电工证考试先交钱吗良心建议 工地太忙根本没时间复习考试,这是很多电工从业者最真实的写照。尤其是刚转岗的漯河学员,既要适应新的工作节奏,又要面对电工证考试的压力,一不小心就错过了考试报名时间,或者连报名流程都不清楚… · 2026/11/19 9:14:49

证书过期了不知道怎么复审延期?急需初级电工证上岗必备全攻略
证书过期了不知道怎么复审延期?急需初级电工证上岗必备全攻略

证书过期了不知道怎么复审延期?急需初级电工证上岗必备全攻略 你是不是正对着手中过期的电工证发愁?证书过期了不知道怎么复审延期,导致工作受阻,收入受损,甚至被单位直接辞退?别急,今天咱们就来聊聊 急需初级电工证… · 2026/11/19 9:13:49

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/18 8:19:55

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/18 8:19:53

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/18 14:38:14

姑苏区哪里考电工证好考前押题怎么找
姑苏区哪里考电工证好考前押题怎么找

姑苏区哪里考电工证好考前押题怎么找 工地太忙根本没时间复习考试,电工证考前还总找不到靠谱的 考前押题 资源,真让人头疼。如果你也是在苏州姑苏区从事建筑或电力行业的,那这些建议你一定要看完。 为什么姑苏区考电工证的人这么多?… · 2026/11/19 0:00:12

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南
罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南

罗定能考电工证吗?外省证转过来流程全解析+郑州报考避坑指南 之前考的证在外省能不能转过来?这几乎是每个特种作业证书持有者都会遇到的问题,特别是像你这样已经在外地工作多年,想回老家罗定发展或者重新规划职业路径的人。别急,今天就给你一条清晰的路… · 2026/11/19 0:00:12

罗定能考电工证吗 电工证含金量到底有多少?
罗定能考电工证吗 电工证含金量到底有多少?

罗定能考电工证吗 电工证含金量到底有多少? 之前考的证在外省能不能转过来,这几乎是每个准备考电工证的朋友最先想到的问题。特别是在罗定这样的地方,很多人的电工证都是在外地考的,现在想在当地继续使用,但不知道怎么办。实际上,电工证的 含金量… · 2026/11/19 0:00:12

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 6:33:25

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 6:33:32

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/19 0:22:38

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码