CH 4302 Intervavl(线段树维护区间gcd，区间加)

偏执的太偏执、 2021-12-17 02:49 240阅读 0赞

## 题意：给定一个长度为 N 的序列，M 个操作，支持区间加，区间查询最大公约数。 ##

## 分析：若是单点修改，区间最大公约数，则可以发现，每次修改最多改变 O(logn) 个答案，且 gcd 可以合并，因此可以直接在线段树上维护。但是对于区间加来说，无法在已知区间加了某一个数时快速计算出新的区间最大公约数，因此，最坏情况下复杂度可能退化到 O(n)。考虑辗转相除法的性质，gcd(x,y,z)=gcd(x,y−x,z−y)可以发现，若维护的是原序列的差分序列，则问题会转化成上述子问题。且原问题询问的答案为gcd(a\[l\],query(l+1,r))，即可保证复杂度不退化。另外，要维护原序列的值，可以采用树状数组在差分数组上进行单点修改、区间查询即可。（区间修改单点查询->单点修改区间查询） ##

## LYD代码： ##

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int N = 500006;
    int n, m;
    ll a[N], b[N], c[N];
    struct T {
    	int l, r;
    	ll ans;
    } t[N*4];
    
    ll gcd(ll x, ll y) {
    	return y ? gcd(y, x % y) : x;
    }
    
    void build(int p, int l, int r) {
    	t[p].l = l;
    	t[p].r = r;
    	if (l == r) {
    		t[p].ans = b[l];
    		return;
    	}
    	int mid = (l + r) >> 1;
    	build(p << 1, l, mid);
    	build(p << 1 | 1, mid + 1, r);
    	t[p].ans = gcd(t[p<<1].ans, t[p<<1|1].ans);
    }
    
    void change_add(int p, int x, ll v) {
    	if (t[p].l == t[p].r) {
    		t[p].ans += v;
    		return;
    	}
    	int mid = (t[p].l + t[p].r) >> 1;
    	if (x <= mid) change_add(p << 1, x, v);
    	else change_add(p << 1 | 1, x, v);
    	t[p].ans = gcd(t[p<<1].ans, t[p<<1|1].ans);
    }
    
    ll ask_t(int p, int l, int r) {
    	if (l <= t[p].l && r >= t[p].r) return t[p].ans;
    	int mid = (t[p].l + t[p].r) >> 1;
    	ll ans = 0;
    	if (l <= mid) ans = gcd(ans, ask_t(p << 1, l, r));
    	if (r > mid) ans = gcd(ans, ask_t(p << 1 | 1, l, r));
    	return abs(ans);
    }
    
    void add(int x, ll y) {
    	while (x <= n) {
    		c[x] += y;
    		x += x & -x;
    	}
    }
    
    ll ask_c(int x) {
    	ll ans = 0;
    	while (x) {
    		ans += c[x];
    		x -= x & -x;
    	}
    	return ans;
    }
    
    /// 树状数组 区间修改单点查询->单点修改区间查询
    int main() {
    	cin >> n >> m;
    	b[0] = 0;
    	memset(c, 0, sizeof(c));
    	for (int i = 1; i <= n; i++) {
    		cin >> a[i];
    		b[i] = a[i] - a[i-1];
    	}
    	build(1, 1, n);
    	while (m--) {
    		char ch;
    		cin >> ch;
    		int l, r;
    		cin >> l >> r;
    		if (ch == 'C') {
    			ll d;
    			cin >> d;
    			change_add(1, l, d);
    			add(l, d);
    			if (r + 1 <= n) {
    				change_add(1, r + 1, -d);
    				add(r + 1, -d);
    			}
    		} else cout << gcd(a[l] + ask_c(l), ask_t(1, l + 1, r)) << endl;
    	}
    	return 0;
    }