Codeforces Round 991 (Div. 3) F. Maximum modulo equality（区间gcd模板）

思路：我们由题意可以知道我们只需要维护区间gcd即可，因为差分一下后，维护的差分数组的区间gcd即为原数组所要求的值

线段树维护

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e5 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e9 + 7;//线段树维护区间gcd模板
ll a[N];
struct node
{int l, r;int gcd;
}tr[N << 2];void push(int u)
{tr[u].gcd = gcd(tr[u << 1].gcd, tr[u << 1 | 1].gcd);
}
void build(int u, int l, int r)
{if(l == r) tr[u] = {l, r, 0};else {tr[u] = {l, r};int mid = tr[u].l + tr[u].r >> 1;build(u << 1, l, mid);build(u << 1 | 1, mid + 1, r);push(u);}
}void modify(int u, int x, int d)
{if(tr[u].l == x && tr[u].r == x) tr[u].gcd = d;else{int mid = tr[u].l + tr[u].r >> 1;if(x <= mid) modify(u << 1, x, d);else modify(u << 1 | 1, x, d);//单点修改push(u);}
}int query(int u, int l, int r)
{if(tr[u].l >= l && tr[u].r <= r) return tr[u].gcd;else {int res = 0;int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) res = gcd(res, query(u << 1, l, r));if(r > mid) res = gcd(res, query(u << 1 | 1, l, r));return res;}
}
int main()
{int t;cin >> t;while(t --){int n, m;cin >> n >> m;for(int i = 1; i <= n; i ++) cin >> a[i];build(1, 1, n);for(int i = 2; i <= n; i ++) modify(1, i, abs(a[i] - a[i - 1]));//维护差分的gcd即可while(m --){int l, r;cin >> l >> r;if(l == r) cout << 0 << endl;else cout << query(1, l + 1, r) << endl;//注意区间gcd的范围，比如（2，4）应为gcd（3， 4）}cout << endl;}  
}

ST表维护：

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 2e5 + 10;
const int MOD = 998244353;
const int INF = 0X3F3F3F3F;
const int dx[] = {-1, 1, 0, 0, -1, -1, +1, +1};
const int dy[] = {0, 0, -1, 1, -1, +1, -1, +1};
const int M = 1e9 + 7;ll dp[N][50];
ll lb[N];
ll a[N];
int n;
void ini()
{lb[0] = -1;//注意预处理的这里是lb[0] = -1;//重要for(int i = 1; i <= N - 1; i ++){lb[i] = (i & (i - 1)) ? lb[i - 1] : lb[i - 1] + 1;}
}
void ST()
{for(int j = 1; j <= lb[n]; j ++){for(int i = 1; i <= n - (1 << j) + 1; i ++){dp[i][j] = gcd(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);//注意加上括号}}
}
int RMQ(int l, int r)
{if(l > r) return 0;int len = lb[r - l + 1];return gcd(dp[l][len], dp[r - (1 << len) + 1][len]);
}
int main()
{ini();int t;cin >> t;while(t --){int q;cin >> n >> q;for(int i = 1; i <= n; i ++) cin >> a[i];for(int i = 1; i <= n; i ++) dp[i][0] = abs(a[i] - a[i - 1]);ST();while(q --){int l, r;cin >> l >> r;cout << RMQ(l + 1, r) << endl;}}
}