题目描述
给定一个长度为 N 的数列 A, 以及 M 条指令 (N≤5*10^5, M<=10^5), 每条指令可能是以下两种之一:
"C l r d", 表示把 A[l],A[l+1],...,A[r] 都加上 d.
"Q l r", 表示询问 A[l],A[l+1],...,A[r] 的最大公约数 (GCD).
输入
第一行两个整数 N,M, 第二行 N 个整数 Ai, 接下来 M 行每条指令的格式如题目描述所示.
输出
对于每个询问, 输出一个整数表示答案.
样例输入
- 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,M≤2*10^5,l<=r, 数据保证任何时刻序列中的数都是不超过 2^62-1 的正整数.
gcd(x,y)=gcd(x,y-x),gcd(x,y,z)=gcd(x,y-x,z-y)...... 对任意多个整数都成立
将 A 数列进行查分, 线段树维护差分序列的最大公约数, 每次询问就是 gcd(A[l],query(1,1,n,l+1,r);
每次修改 update(1,1,n,l,d),update(1,1,n,r+1,-d)
A 数组也需要维护, 线段树和树状数组都行
- #include<bits/stdc++.h>
- #define ll long long
- using namespace std;
- const int N=5e5+10;
- ll A[N*4],a[N],B[N*4],b[N];
- int n,m;
- char op;
- int lowbit(int x)
- {
- return x&-x;
- }
- void add(int x,ll val)
- {
- for (int i=x;i<=n;i+=lowbit(i))
- A[i]+=val;
- }
- ll sum(int x)
- {
- ll ret=0;
- for (int i=x;i>=1;i-=lowbit(i))
- ret+=A[i];
- return ret;
- }
- void Pushup(int s)
- {
- B[s]=__gcd(B[s<<1],B[s<<1|1]);
- }
- void build(int s,int l,int r)
- {
- if (l==r)
- {
- B[s]=b[l];
- return ;
- }
- int mid=(l+r)>>1;
- build(s<<1,l,mid);
- build(s<<1|1,mid+1,r);
- Pushup(s);
- }
- void update(int s,int l,int r,int pos,ll val)
- {
- if (l==r)
- {
- B[s]+=val;
- return ;
- }
- int mid=(l+r)>>1;
- if (pos<=mid) update(s<<1,l,mid,pos,val);
- else update(s<<1|1,mid+1,r,pos,val);
- Pushup(s);
- }
- ll query(int s,int l,int r,int L,int R)
- {
- // cout<<s<<''<<l<<' '<<r<<' '<<L<<' '<<R<<' '<<B[s]<<endl;
- if (L<=l&&r<=R) return B[s];
- int mid=(l+r)>>1;
- if (R<=mid) return query(s<<1,l,mid,L,R);
- else if (L>mid) return query(s<<1|1,mid+1,r,L,R);
- else return __gcd(query(s<<1,l,mid,L,R),query(s<<1|1,mid+1,r,L,R));
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
- for (int i=1;i<=n;i++) b[i]=a[i]-a[i-1],add(i,b[i]);
- build(1,1,n);
- int l,r; ll d;
- while (m--)
- {
- scanf("%c",&op);
- if (op=='C')
- {
- scanf("%d%d%lld",&l,&r,&d);
- add(l,d);
- add(r+1,-d);
- update(1,1,n,l,d);
- if (r+1<=n) update(1,1,n,r+1,-d);
- }
- else
- {
- scanf("%d%d",&l,&r);
- //cout<<sum(l)<<endl;
- //cout<<query(1,1,n,r,r)<<endl;
- //cout<<query(1,1,n,l+1,r)<<endl;
- ll ans=abs(__gcd(sum(l),query(1,1,n,l+1,r)));
- printf("%lld\n",ans);
- }
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2788602.html