线段树+最大最小

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

#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define INF 2e9
using namespace std;

#define endl '\n'
using ll = long long;
using pii = pair<int, int>;
const double PI = acos(-1);
const int N = 1e5 + 10;
const int mod = 1e9 + 7;

struct node{
	int addmax,addmin,submax,submin;
	int ans;
};
vector<node> st;
vector<int> a;
void pushup(int p){
	st[p].addmax=max(st[lc].addmax,st[rc].addmax);
	st[p].addmin=min(st[lc].addmin,st[rc].addmin);
	st[p].submax=max(st[lc].submax,st[rc].submax);
	st[p].submin=min(st[lc].submin,st[rc].submin);
	st[p].ans=max((st[rc].submax-st[lc].submin),(st[lc].addmax-st[rc].addmin));
	st[p].ans=max(st[p].ans,max(st[lc].ans,st[rc].ans));
	
}
void build(int p,int l,int r){
	if(l==r){
		st[p].addmax=a[l]+l;
		st[p].addmin=a[l]+l;
		st[p].submax=a[l]-l;
		st[p].submin=a[l]-l;
		st[p].ans=0;
		return;
	}
	int mid=(l+r)>>1;
	build(lc,l,mid);
	build(rc,mid+1,r);
	pushup(p);
}
void add(int p,int l,int r,int pos,int x){
	if(l==r){
		st[p].addmax=x+pos;
		st[p].addmin=x+pos;
		st[p].submax=x-pos;
		st[p].submin=x-pos;
		st[p].ans=0;
		return;
	}
	int mid=(l+r)>>1;
	if(pos<=mid) add(lc,l,mid,pos,x);
	else add(rc,mid+1,r,pos,x);
	pushup(p);
}
void solve() {
	int n,q;cin>>n>>q;
	st.clear();
	a.clear();
	st.resize(4*n);
	a.resize(n+1);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	build(1,1,n);
	cout<<st[1].ans<<endl;
	while(q--){
		int pos,x;cin>>pos>>x;
		add(1,1,n,pos,x);
		cout<<st[1].ans<<endl;
	}
		
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	
	int T = 1;
	cin>>T;
	while (T--) {
		solve();
	}
	
	return 0;
}