Description
链接:https://ac.nowcoder.com/acm/problem/26255
来源:牛客网
小阳手中一共有 n 个贝壳,每个贝壳都有颜色,且初始第 i 个贝壳的颜色为 。现在小阳有 3 种操作:
1 l r x:给 [l,r]区间里所有贝壳的颜色值加上 x 。
2 l r:询问 [l,r]区间里所有相邻贝壳颜色值的差(取绝对值) 的最大值(若 l = r 输出 0)。
3 l r :询问 [l,r]区间里所有贝壳颜色值的最大公约数。
Solution
前置知识:差分数组、线段树
差分数组
设原数组为 , 令 , 称 为 的差分数组。
差分数组有什么好处呢?
首先不难得到
另外,对原数组 进行区间加 的操作时只需要令:
,。这样做的目的是为了让我们每次查询 的时候都能保证 的结果都是比原来多 的,从而实现了区间加法操作。
线段树
线段树是一种能够支持 复杂度进行区间查询,区间修改的数据结构。
题目是经典区间修改及查询问题,需要特定的数据结构进行求解。仔细观察每一个操作,不难发现:
- 操作1能够用上述差分数组的区间加操作完成,转换成线段树的单点修改。
- 操作2查询的差分数组区间的最大绝对值,转换为线段树的区间最大值查询,需要维护一个绝对值最大的值。
- 操作3中,因为 值可以通过线段树维护,由定理 得到启发,我们在查询的时候可以转化为 , 是差分数组 在区间的。
于是通过对差分数组建立线段树,维护线段树上的 三个值,就能解决这道题。
注意线段树上查询区间 时间复杂度是 , 本题保证 , 可视为常数
总体时间复杂度
Code
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; struct node { int l, r, maxz, sum, gcd; }t[N << 2]; int a[N], b[N]; void push_up(int rt) { t[rt].maxz = max(t[rt << 1].maxz, t[rt << 1 | 1].maxz); t[rt].sum = t[rt << 1].sum + t[rt << 1 | 1].sum; t[rt].gcd = __gcd(t[rt << 1].gcd, t[rt << 1 | 1].gcd); } void build(int rt, int l, int r) { t[rt].l = l, t[rt].r = r; if(l == r) { t[rt].maxz = abs(b[l]); t[rt].gcd = t[rt].sum = b[l]; return ; } int mid = t[rt].l + t[rt].r >> 1; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); push_up(rt); } void update(int rt, int x, int val) { if(t[rt].l == t[rt].r) { t[rt].sum += val; t[rt].gcd = t[rt].sum; t[rt].maxz = abs(t[rt].sum); return ; } int mid = t[rt].l + t[rt].r >> 1; if(x <= mid) { update(rt << 1, x, val); } else { update(rt << 1 | 1, x, val); } push_up(rt); } int query_max(int rt, int ql, int qr) { if(ql <= t[rt].l && qr >= t[rt].r) { return t[rt].maxz; } int mid = t[rt].l + t[rt].r >> 1; if(qr <= mid) { return abs(query_max(rt << 1, ql, qr)); } else if(ql > mid) { return abs(query_max(rt << 1 | 1, ql, qr)); } else { return abs(max(query_max(rt << 1, ql, mid), query_max(rt << 1 | 1, mid + 1, qr))); } } int query_sum(int rt, int ql, int qr) { if(ql <= t[rt].l && qr >= t[rt].r) { return t[rt].sum; } int mid = t[rt].l + t[rt].r >> 1; if(qr <= mid) { return query_sum(rt << 1, ql, qr); } else if(ql > mid) { return query_sum(rt << 1 | 1, ql, qr); } else { return query_sum(rt << 1, ql, mid) + query_sum(rt << 1 | 1, mid + 1, qr); } } int query_gcd(int rt, int ql, int qr) { if(ql <= t[rt].l && qr >= t[rt].r) { return t[rt].gcd; } int ans = 0; int mid = t[rt].l + t[rt].r >> 1; //if(ql <= mid) ans = __gcd(ans, query_gcd(rt << 1, ql, qr)); //if(qr > mid) ans = __gcd(ans, query_gcd(rt << 1 | 1, ql, qr)); //return ans; if(qr <= mid) { return query_gcd(rt << 1, ql, qr); } else if(ql > mid) { return query_gcd(rt << 1 | 1, ql, qr); } else { return __gcd(query_gcd(rt << 1, ql, mid), query_gcd(rt << 1 | 1, mid + 1, qr)); } } int main() { ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++) { cin >> a[i]; b[i] = a[i] - a[i - 1]; } build(1, 1, n); while(m--) { int op, l, r, x; cin >> op; if(op == 1) { cin >> l >> r >> x; update(1, l, x); if(r < n) { update(1, r + 1, -x); } } else if(op == 2) { cin >> l >> r; if(l == r) { cout << 0 << '\n'; } else { cout << query_max(1, l + 1, r) << '\n'; } } else { cin >> l >> r; if(l == r) { cout << query_sum(1, 1, l) << '\n'; } else { cout << abs(__gcd(query_sum(1, 1, l), query_gcd(1, l + 1, r))) << '\n'; } } } return 0; }