題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的序列，需要執行 $m$ 次操作，每次操作分為下列兩種類型：

C l r d：將區間 $[l,r]$ 位置的數字都加上 $d$

Q l r：詢問區間 $[l,r]$ 的最大公約數

題目分析：首先是推廣一下最大公約數的公式：

• $gcd(a,b)=gcd(a,b?a)$
• $gcd(a,b,c)=gcd(a,b?a,c?b)$
• $gcd(a_1,a_2,...a_n)=gcd(a_1,a_2?a_1,...,a_n?a_{n?1})$

如此一來我們可以同時維護一下原數組以及差分數組，設 $b_i=a_i?a_{i?1}$，對于每次修改而言，差分數組是單點修改，而原數組是區間修改。對于每次查詢而言，差分數組是區間查詢，原數組是單點查詢。

最后說一下改如何查詢，對于 $[l,r]$ 的查詢，我們只需要輸出 $gcd(a[l],b[l+1],...,b[r])$ 就是答案了

代碼：

// Problem: 區間最大公約數 // Contest: AcWing // URL: https://www.acwing.com/problem/content/247/ // Memory Limit: 64 MB // Time Limit: 1000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; LL c[N],a[N]; int n,m; struct Node {int l,r;LL sum; }tree[N<<2]; void pushup(int k) {tree[k].sum=__gcd(tree[k<<1].sum,tree[k<<1|1].sum); } void build(int k,int l,int r) {tree[k]={l,r};if(l==r) {tree[k].sum=a[l]-a[l-1];return;}int mid=(l+r)>>1;build(k<<1,l,mid);build(k<<1|1,mid+1,r);pushup(k); } void update(int k,int pos,LL val) {if(pos>n) {return;}if(tree[k].l==tree[k].r) {tree[k].sum+=val;return;}int mid=(tree[k].l+tree[k].r)>>1;if(pos<=mid) {update(k<<1,pos,val);} else {update(k<<1|1,pos,val);}pushup(k); } LL query(int k,int l,int r) {if(tree[k].l>r||tree[k].r<l) {return 0;}if(tree[k].l>=l&&tree[k].r<=r) {return tree[k].sum;}return __gcd(query(k<<1,l,r),query(k<<1|1,l,r)); } void add(LL x,LL val) {for(int i=x;i<N;i+=lowbit(i)) {c[i]+=val;} } LL ask(LL x) {LL ans=0;for(int i=x;i>0;i-=lowbit(i)) {ans+=c[i];}return ans; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n),read(m);for(int i=1;i<=n;i++) {read(a[i]);}build(1,1,n);while(m--) {char op[5];scanf("%s",op);if(op[0]=='Q') {int l,r;read(l),read(r);printf("%lld\n",__gcd(a[l]+ask(l),abs(query(1,l+1,r))));} else if(op[0]=='C') {int l,r;LL val;read(l),read(r),read(val);add(l,val),add(r+1,-val);update(1,l,val),update(1,r+1,-val);}}return 0; }

總結

以上是生活随笔為你收集整理的AcWing - 246. 区间最大公约数(树状数组+线段树)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。