题目地址:https://www.acwing.com/problem/content/247/
题目描述:
给定一个长度为N的数列A,以及M条指令,每条指令可能是以下两种之一:
1、“C l r d”,表示把 A[l],A[l+1],…,A[r] 都加上 d。
2、“Q l r”,表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问,输出一个整数表示答案。
输入格式
第一行两个整数N,M。
第二行N个整数A[i]。
接下来M行表示M条指令,每条指令的格式如题目描述所示。
输出格式
对于每个询问,输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000
题解:这道题是区间修改和区间查询。但是由于最大公约数的特性,我们可以改为单点修改。(x,y,z....)的最大公约数与(x,y-x,z-y....)的最大公约数相同
证明,只要证明前者的最大公约数是后者的公约数,并且后者的最大公约数是前者的公约数就可以了。假设,前者的最大公约数为d1,则x%d1=0,y%d1=0,z%d1=0....,那么显而易见x%d1=0,(y-x)%d1=0,(z-y)%d1=0.那么可以知道d1也是后者的公约数
假设后者的最大公约数是d2,则x%d2=0,(y-x)%d2=0,(z-y)%d2=0.....,可以知道x%d2=0,y%d2=0,z%d2=0,...所以d2也是前者的公约数。
通过上面这个数学知识,我们便可以利用差分数组来进行求解,那么区间加和就可以转换为两个单点修改。至于区间[l,r]的最大公约数,可以求出sum[l]和[l+1,r]的最大公约数,让二者再求公约数。注意线段树中存储的是元数组的差分数组。
AC代码:
#include<iostream> #include<cmath> using namespace std; const int N=5e5+10; #define ll long long int struct node{ int l,r; ll sum,gc; }tr[4*N]; ll last=0,x; ll gcd(ll a,ll b){ if(b==0) return a; return gcd(b,a%b); } struct node pushup(struct node &a,struct node &b,struct node &c){ a.sum=b.sum+c.sum; a.gc=gcd(b.gc,c.gc); return a; } void pushup(int u){ pushup(tr[u],tr[u<<1],tr[u<<1|1]); } void build(int u,int l,int r){ tr[u].l=l,tr[u].r=r; if(l==r){ cin>>x; tr[u].sum=x-last; tr[u].gc=x-last; last=x; return ; } int mid=l+r>>1; build(u<<1,l,mid); build(u<<1|1,mid+1,r); pushup(u); return ; } void modify(int u,int x,ll d){ if(tr[u].l==x&&tr[u].r==x){ tr[u].sum+=d; tr[u].gc+=d; return ; } int mid=tr[u].l+tr[u].r>>1; if(x<=mid) modify(u<<1,x,d); if(x>mid) modify(u<<1|1,x,d); pushup(u); return ; } struct node query(int u,int l,int r){ if(l>r) return node({0}); if(tr[u].l>=l&&tr[u].r<=r){ return tr[u]; } int mid=tr[u].l+tr[u].r>>1; struct node a1,a2,a; if(l<=mid) a1=query(u<<1,l,r); if(r>mid) a2=query(u<<1|1,l,r); if(l<=mid&&r>mid) return pushup(a,a1,a2); else if(l<=mid) return a1; else return a2; } int main(){ int n,m;cin>>n>>m; build(1,1,n); char ch; ll l,r,d; while(m--){ cin>>ch>>l>>r; if(ch=='C'){ cin>>d; modify(1,l,d); if(r<n) modify(1,r+1,-d); } else { struct node left=query(1,1,l),right; if(l+1<=r) right=query(1,l+1,r); else { right.gc=left.sum; } cout<<abs(gcd(left.sum,right.gc))<<endl; } } return 0; }
写于:2020/8/28 9:19