rt，自己想的是将其变成一个差分数组，然后对于一个线段树，维护前缀和/后缀和分别为正/负时的最大答案。WA #2 一千多行不太清楚怎么做求找出代码错误/更好的思路。

欸欸不过代码很凑额啊唉

#include<cmath>
#include<iostream>
#define lc p<<1
#define rc p<<1|1
#define int long long
#define mid (tr[p].l+tr[p].r)/2
using namespace std;
const int N=2e6+5;
struct Tr{
	int l,r,slen,sum,maxn,qzh[2],qlen[2],hzh[2],hlen[2];
}tr[N];
int t,n,q,num[N],dif[N];
void pushup(int p){
	tr[p].sum=tr[lc].sum+tr[rc].sum;
	tr[p].qzh[0]=tr[lc].qzh[0],tr[p].qzh[1]=tr[lc].qzh[1];
	tr[p].qlen[0]=tr[lc].qlen[0],tr[p].qlen[1]=tr[lc].qlen[1];
	tr[p].hzh[0]=tr[rc].hzh[0],tr[p].hzh[1]=tr[rc].hzh[1];
	tr[p].hlen[0]=tr[rc].hlen[0],tr[p].hlen[1]=tr[rc].hlen[1];
	tr[p].maxn=max(tr[lc].maxn,tr[rc].maxn);
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			int x=tr[lc].sum+tr[rc].qzh[j],
				len=tr[lc].slen+tr[rc].qlen[j];
			if(x>0)
				if(x-len>tr[p].qzh[0]-tr[p].qlen[0])
					tr[p].qzh[0]=x,tr[p].qlen[0]=len;
			else
				if(-x-len>-tr[p].qzh[1]-tr[p].qlen[1])
					tr[p].qzh[1]=x,tr[p].qlen[1]=len;
			
			x=tr[lc].hzh[i]+tr[rc].sum,
			len=tr[lc].hlen[i]+tr[rc].slen;
			if(x>0)
				if(x-len>tr[p].hzh[0]-tr[p].hlen[0])
					tr[p].hzh[0]=x,tr[p].hlen[0]=len;
			else
				if(-x-len>-tr[p].hzh[1]-tr[p].hlen[1])
					tr[p].hzh[1]=x,tr[p].hlen[1]=len;
			tr[p].maxn=max(tr[p].maxn,
						abs(tr[lc].hzh[i]+tr[rc].qzh[j])-tr[lc].hlen[i]-tr[rc].qlen[j]);
		}
	}
}
void build(int l,int r,int p){
	tr[p]={l,r,r-l+1};
	if(l==r){
		tr[p].sum=tr[p].maxn=
		tr[p].qzh[0]=tr[p].qzh[1]=
		tr[p].hzh[0]=tr[p].hzh[1]=dif[l];
		tr[p].qlen[0]=tr[p].qlen[1]=
		tr[p].hlen[0]=tr[p].hlen[1]=1;
		if(dif[l]<0)
			tr[p].qzh[0]=tr[p].hzh[0]=0,
			tr[p].qlen[0]=tr[p].hlen[0]=0;
		else
			tr[p].qzh[1]=tr[p].hzh[1]=0,
			tr[p].qlen[1]=tr[p].hlen[1]=0;
		if(tr[p].maxn<0) tr[p].maxn=-tr[p].maxn;
		tr[p].maxn--;
		return;
	}
	build(l,mid,lc);build(mid+1,r,rc);
	pushup(p);
}
void update(int a,int p){
	if(tr[p].l==tr[p].r){
		tr[p].sum=tr[p].maxn=
		tr[p].qzh[0]=tr[p].qzh[1]=
		tr[p].hzh[0]=tr[p].hzh[1]=dif[a];
		tr[p].qlen[0]=tr[p].qlen[1]=
		tr[p].hlen[0]=tr[p].hlen[1]=1;
		if(dif[a]<0)
			tr[p].qzh[0]=tr[p].hzh[0]=0,
			tr[p].qlen[0]=tr[p].hlen[0]=0;
		else
			tr[p].qzh[1]=tr[p].hzh[1]=0,
			tr[p].qlen[1]=tr[p].hlen[1]=0;
		if(tr[p].maxn<0) tr[p].maxn=-tr[p].maxn;
		tr[p].maxn--;
		return;
	}
	if(a<=mid) update(a,lc);
	else update(a,rc);
	pushup(p);
}
void solve(){
	cin>>n>>q;int op,x;
	for(int i=1;i<=n;i++) cin>>num[i];
	if(n==1){
		cout<<"0\n";
		while(q--){cin>>op>>x;cout<<"0\n";}
		return;
	}
	for(int i=2;i<=n;i++) dif[i]=num[i]-num[i-1];
	build(2,n,1);cout<<max(0ll,tr[1].maxn)<<endl;
	while(q--){
		cin>>op>>x;num[op]=x;
		if(op>1){
			dif[op]=num[op]-num[op-1];
			update(op,1);
		}
		if(op+1<=n){
			dif[op+1]=num[op+1]-num[op];
			update(op+1,1);
		}
		cout<<max(0ll,tr[1].maxn)<<endl;
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>t;while(t--) solve();
	return 0;
}