NC 26255 更相减损术 + 线段树

题意

传送门 NC 26255

题解

只考虑后两种操作很容易用线段树维护，但第一种操作需要进行区间修改，复杂度可能退化为 $O(n)$。考虑差分处理。差分的好处在于将区间更新变为单点更新，求单点原值的时候 $O(logn)$ 求前缀和即可。问题在于如何维护区间的最大公约数。

根据更相减损术（类似于减法版的辗转相除法），最大公约数有如下性质 $$gcd(x,y,z\dots )=gcd(x,y-x,z-y,\dots )$$ 容易证明，当差值为负时取绝对值依然满足上式。设 $d[i]=col[i]-col[i-1]$，则区间的最大公约数为 $$gcd(\sum _{i=1}^{l}d[i],d[l+1],\dots ,d[r])$$ 那么线段树维护差分数组的区间和，区间绝对值的最大值与区间的最大公约数即可。

#include <bits/stdc++.h> using namespace std; #define maxn 100005 #define sg_size (1 << 18) - 1 struct node { int gcd, mx, sum; } sg[sg_size]; int n, m, col[maxn]; int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } inline void pushup(int k, int chl, int chr) { sg[k].gcd = gcd(sg[chl].gcd, sg[chr].gcd); sg[k].mx = max(sg[chl].mx, sg[chr].mx); sg[k].sum = sg[chl].sum + sg[chr].sum; } void init(int k, int l, int r) { if (r - l == 1) { int d = col[l] - col[l - 1]; sg[k] = node{abs(d), abs(d), d}; } else { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; init(chl, l, m); init(chr, m, r); pushup(k, chl, chr); } } void update(int a, int b, int x, int k, int l, int r) { if (a <= l && r <= b) { int d = sg[k].sum + x; sg[k] = node{abs(d), abs(d), d}; } else if (l < b && a < r) { int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; update(a, b, x, chl, l, m); update(a, b, x, chr, m, r); pushup(k, chl, chr); } } node query(int a, int b, int k, int l, int r) { if (b <= l || r <= a) { return node{0, 0, 0}; } else if (a <= l && r <= b) { return sg[k]; } int chl = (k << 1) + 1, chr = (k << 1) + 2, m = (l + r) >> 1; node c = query(a, b, chl, l, m); node d = query(a, b, chr, m, r); return node{gcd(c.gcd, d.gcd), max(c.mx, d.mx), c.sum + d.sum}; } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { scanf("%d", col + i); } int ub = n + 1; init(0, 1, ub); while (m--) { int op, l, r; scanf("%d%d%d", &op, &l, &r); if (op == 1) { int x; scanf("%d", &x); update(l, l + 1, x, 0, 1, ub); update(r + 1, r + 2, -x, 0, 1, ub); } else if (op == 2) { printf("%d\n", query(l + 1, r + 1, 0, 1, ub).mx); } else { int a = query(1, l + 1, 0, 1, ub).sum; int b = query(l + 1, r + 1, 0, 1, ub).gcd; printf("%d\n", gcd(a, b)); } } return 0; }