本文分享的必刷题目是从蓝桥云课、洛谷、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]∑i1lb[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
本文分享的必刷题目是从蓝桥云课、洛谷、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]∑i1lb[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
