模仿jiangly封装的线段树单点修改模板

https://codeforces.com/contest/2057/problem/D

#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define int long long
#define endl '\n'
const int N=1e6+10,mod=998244353,INF=1e16;

typedef pair<int,int> PII;

#define ls u<<1
#define rs u<<1|1
//单点修改线段树,初始化时需要逐个单点修改
template<class Info>
struct SegmentTree {
	vector<Info> tr;
	int n;
	SegmentTree(int n_){
		init(n_);
	}
	void init(int n_){
		n=n_;
		tr.resize(4*n+4);
		build(1,1,n);
	}
	void build(int u,int l,int r){
		tr[u]=Info();
		if(l==r) return ;
		int m=l+r>>1;
		build(ls,l,m),build(rs,m+1,r);
		pushup(u);
	}
	void pushup(int u){
		tr[u]=tr[ls]+tr[rs];
	}
	void Modify(int u,int l,int r,int x,const Info &v){
		if(r<x||l>x)return ; 
		if(l==r&&x==l){
			tr[u]=v;
			return ;
		}
		int m=l+r>>1;
		Modify(ls,l,m,x,v);Modify(rs,m+1,r,x,v);
    	pushup(u);
	}
	void modify(int x,const Info &v){
		Modify(1,1,n,x,v);
	}
	Info Query(int u,int l,int r,int x,int y){//x和y是询问范围 
		if(l>x||r<y) return Info();
		if(l>=x&&r<=y) return tr[u];
		int m=l+r>>1;
		return Query(ls,l,m,x,y)+Query(rs,m+1,r,x,y);
	}
	Info query(int l,int r){
		return Query(1,1,n,l,r);
	}
};

struct Info{
	int rmx,lmx,rmi,lmi,ans;
	Info():rmx(-INF),lmx(-INF),rmi(INF),lmi(INF),ans(0){}
	Info(int x,int i):rmx(x-i),lmi(x-i),rmi(x+i),lmx(x+i),ans(0){}
};

Info operator+(const Info &a,const Info &b){
	Info c;
	c.rmx=max(a.rmx,b.rmx);
	c.lmx=max(a.lmx,b.lmx);
	c.rmi=min(a.rmi,b.rmi);
	c.lmi=min(a.lmi,b.lmi);
	c.ans=max(max(a.ans,b.ans),max(b.rmx-a.lmi,a.lmx-b.rmi));
	return c;
}

void slove(){
	int n,q;
	cin>>n>>q;
	SegmentTree<Info> seg(n);
	for(int i=1;i<=n;i++){
		int a;
		cin>>a;
		seg.modify(i,Info(a,i));
	}
	cout<<seg.query(1,n).ans<<endl;
	for(int i=1;i<=q;i++){
		int p,x;
		cin>>p>>x;
		seg.modify(p,Info(x,p));
		cout<<seg.query(1,n).ans<<endl;
	}
}
/*
2 0
1 10
*/
signed main(){
	ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
	int T=1;
	cin>>T;
	while(T--) slove();
}