T2 你能回答这些问题吗？

solution

题目要求 2 个操作

1. 求一段区间内的最大子段和
2. 修改一个数

考虑用线段树解决

首先：要怎么在线段树维护区间内的最大子段和呢？联想用分治求最大子段和的过程，不难看出，分治与线段树求最大子段和的思路其实是一样的：

1. 求 mid 左边区间的最大子段和
2. 求 mid 右边区间的最大子段和
3. 求包括 mid 的最大子段和

难点在于第 3 个最大子段和怎么求，可以令：ts 为区间的最大子段和，ls 为区间前缀最大和，rs 为区间后缀最大和，sum 为区间和，显然的，有如下维护方式：

$$p_{ts} = max(lp_{ts},rp_{ts},lp_{rs} + rp_{ls})$$ $$p_{ls} = max(lp_{ls} , lp_{sum} + rp_{ls})$$ $$p_{rs} = max(rp_{rs} , rp_{sum} + lp_{rs})$$ $$p_{sum} = lp_{sum} + rp_{sum}$$

(可以自己画个图想一想，这里就不给图了 qwq)

然后修改的话就是普通的线段树板子，查询过程与线段树维护过程差不多，具体见代码

code

#include<bits/stdc++.h>
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 5e5 + 5;

struct segmentTree{
	int s , t;
	int ts , ls , rs , sum;
}tr[N << 2];

int n , m , a[N];
int op;

void pushup(segmentTree &p , segmentTree &lp , segmentTree &rp){
	p.sum = lp.sum + rp.sum;
	p.ts = max(max(lp.ts , rp.ts) , lp.rs + rp.ls);
	
	p.ls = max(lp.ls , lp.sum + rp.ls);
	p.rs = max(rp.rs , rp.sum + lp.rs);
}

void pushup(int p){
	pushup(tr[p] , tr[p << 1] , tr[p << 1 | 1]);
}

void build(int s , int t , int p){
	if(s == t){
		tr[p] = {s , t , a[s] , a[s] , a[s] , a[s]};
		return;
	}
	tr[p] = {s , t};
	int m = (s + t) >> 1;
	build(s , m , p << 1);
	build(m + 1 , t , p << 1 | 1);
	pushup(p);
}

void modify(int l , int k , int p){
	int s = tr[p].s , t = tr[p].t;
	if(s == t && t == l){
		tr[p] = {s , t , k , k , k , k};
		return;
	}
	int m = (s + t) >> 1;
	if(l <= m) modify(l , k , p << 1);
	if(l > m) modify(l , k , p << 1 | 1);
	pushup(p);
}

segmentTree query(int l , int r , int p){
	int s = tr[p].s , t = tr[p].t;
	if(l <= s && t <= r){
		return tr[p];
	}
	int m = (s + t) >> 1;
	if(r <= m) return query(l , r , p << 1);
	else if(l > m) return query(l , r , p << 1 | 1);
	else{
		segmentTree lp = query(l , r , p << 1) , rp = query(l , r , p << 1 | 1) , res;
		pushup(res , lp , rp);
		return res;
	}
}

int main(){      qwq
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	build(1 , n , 1);
	
	while(m --){
		cin >> op;
		
		if(op == 1){
			int x , y;
			cin >> x >> y;
			if(x > y) swap(x , y);
			cout << query(x , y , 1).ts << '\n';
		}
		else{
			int x , y;
			cin >> x >> y;
			modify(x , y , 1);
		}
	}
	return 0;
}

T3 区间最大公约数

solution

先考虑弱化版本单点加，因为 $\gcd$ 满足结合律，所以可以直接在线段树上维护 $\gcd$ ，修改直接改节点就可以了，但是区间加怎么办呢

首先观察 $\gcd$ 的性质，有 $\gcd(x , y) = \gcd(x , y - x)$，根据此性质有如下推论：

$$\gcd_{i=l}^r{a_i} = \gcd(a_l , a_{l + 1} - a_l,...,a_r - a_{r - 1})$$$$= \gcd(a_l , \gcd_{i=l+1}^r{a_i - a_{i-1}})$$

（这里就不证明了（太懒了 qwq）,证明过程详见这里）

这个推论表明我们可以用差分的形式来维护 $\gcd$，差分刚好可以满足区间加，修改时处理端点即可

注意到我们的式子中有一个 $a_l$，所以要用线段树维护下差分数组的区间和或者用树状数组即可

code

#include<bits/stdc++.h>
#define int long long
#define qwq ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

const int N = 5e5 + 5;

struct segmentTree{
	int s , t , g , sum;
}tr[N << 2];

int n , m , a[N];
string op;

int gcd(int a , int b){
	if(b == 0) return a;
	return gcd(b , a % b);
}

void pushup(segmentTree &p , segmentTree &lp , segmentTree &rp){
	p.sum = lp.sum + rp.sum;
	p.g = abs(gcd(lp.g , rp.g));
}

void pushup(int p){
	pushup(tr[p] , tr[p << 1] , tr[p << 1 | 1]);
}

void build(int s , int t , int p){
	if(s == t){
		int b = a[s] - a[s - 1];
		tr[p] = {s , t , b , b};
		return;
	}
	tr[p] = {s , t};
	int m = (s + t) >> 1;
	build(s , m , p << 1);
	build(m + 1 , t , p << 1 | 1);
	pushup(p);
}

void modify(int l , int k , int p){
	int s = tr[p].s , t = tr[p].t;
	if(s == t && t == l){
		tr[p].sum += k , tr[p].g += k;
		return;
	}
	int m = (s + t) >> 1;
	if(l <= m) modify(l , k , p << 1);
	if(l > m) modify(l , k , p << 1 | 1);
	pushup(p);
}

segmentTree query(int l , int r , int p){
	if(l > r) return {0};
	
	int s = tr[p].s , t = tr[p].t;
	if(l <= s && t <= r){
		return tr[p];
	}
	int m = (s + t) >> 1;
	if(r <= m) return query(l , r , p << 1);
	else if(l > m) return query(l , r , p << 1 | 1);
	else{
		segmentTree lp = query(l , r , p << 1) , rp = query(l , r , p << 1 | 1) , res;
		pushup(res , lp , rp);
		return res;
	}
}

signed main(){                qwq
	cin >> n >> m;
	
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
	}
	
	build(1 , n , 1);
	for(int i = 1 ; i <= m ; i ++){
		cin >> op;
		
		if(op == "C"){
			int l , r , d;
			cin >> l >> r >> d;
			
			modify(l , d , 1);
			if(r < n) modify(r + 1 , -d , 1);
		}
		else{
			int l , r;
			cin >> l >> r;
			cout << gcd(query(1 , l , 1).sum , query(l + 1 , r , 1).g) << '\n';
		}
	}
	return 0;
}