AcWing. 246区间最大公约数
给定一个长度为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
代码
#include<iostream> #include<cstdio> #include<queue> #include<string> #include<cstring> #include<map> #include<vector> #include<set> #include<stack> #include<cmath> #include<algorithm> #include<vector> #include<utility> #include<deque> #define INF 0x3f3f3f3f #define mod 1000000007 #define fi first #define se second #define pb push_back #define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define endl '\n' #define eps 1e-6 #define mem(n,a) memset(n,a,sizeof(n)) #define rep(i,be,en) for(int i=be;i<=en;++i) #define pre(i,be,en) for(int i=en;i>=be;--i) inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } inline int lowbit(int x) { return x & -x; } using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; const int N = 500010; struct Node { int l, r; LL sum, d; }tr[N * 4]; int n, m; LL w[N]; LL gcd(LL a, LL b) { return b ? gcd(b, a % b) : a; } void pushup(Node& u, Node& l, Node& r) { u.sum = l.sum + r.sum; u.d = gcd(l.d, r.d); } void pushup(int u) { pushup(tr[u], tr[u << 1], tr[u << 1 | 1]); } void build(int u, int l,int r) { if (l == r) { LL b = w[r] - w[r - 1]; tr[u] = { r,r,b,b }; } else { tr[u].l = l, tr[u].r = r; int mid = l + r >> 1; build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); pushup(u); } } void modify(int u, int x, LL v) { if (tr[u].l == x && tr[u].r == x) { LL b = tr[u].sum + v; tr[u] = { x,x,b,b }; } else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid)modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } } Node query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r <= r)return tr[u]; else { int mid = tr[u].l + tr[u].r >> 1; if (r <= mid)return query(u << 1, l, r); else if (l > mid)return query(u << 1 | 1, l, r); else{ auto left = query(u << 1, l, r); auto right = query(u << 1 | 1, l, r); Node res; pushup(res, left, right); return res; } } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n;++i)scanf("%lld", &w[i]); build(1, 1, n); char op[2]; int l, r; LL d; while (m--) { scanf("%s%d%d", op, &l, &r); if (op[0] == 'Q') { auto left = query(1, 1, l); Node right = { 0,0,0,0 }; if (l + 1 <= r)right = query(1,l + 1, r); printf("%lld\n", abs(gcd(left.sum, right.d))); } else { scanf("%lld", &d); modify(1, l, d); if (r + 1 <= n)modify(1, r + 1, -d); } } }
