Codeforces Round #672 (Div. 2) C2 - Pokémon Army (hard version)（贪心，维护变化值）

x数组里选一个子数组y(原数组顺序)，y1-y2+y3-y4+… 的最大值
然后还有q次交换操作，每次修改之后都要输出新的最大值

（1）如果没有修改，单纯对于当前数组考虑，我们最后选出来的点肯定是波峰波谷这样子，然后最后一个点一定是波峰，并且最后选出来的一定是奇数个
（2）那么最后的答案就是max(0 , a[i] - a[i+1] ) 求和，记得让a[n+1]为0方便统计最后一个波峰 （这里真的妙）
（3）这样的话，对于每个操作，维护一下他的变化就行
（4）不关流会T

#define int ll
int a[MX],ans;

void del(int pos)
{
	if(pos!=1) ans-=max(0ll,a[pos-1]-a[pos]);
	ans-=max(0ll,a[pos]-a[pos+1]);
}
void add(int pos)
{
	if(pos!=1) ans+=max(0ll,a[pos-1]-a[pos]);
	ans+=max(0ll,a[pos]-a[pos+1]);
}
void solve()
{
	int n,q; cin>>n>>q;
	rpp(i,n) cin>>a[i];
	a[0]=a[n+1]=0;
	ans=0;
	for(int i=n;i>=1;--i) ans=ans+max(0ll,a[i]-a[i+1]);
	cout<<ans<<endl;
	while(q--)
	{
		int l,r;cin>>l>>r;
		if(l+1==r) del(l),ans-=max(0ll,a[r]-a[r+1]);
		else del(l),del(r);
		swap(a[l],a[r]);
		if(l+1==r) add(l),ans+=max(0ll,a[r]-a[r+1]);
		else add(l),add(r);
		cout<<ans<<endl;
	}
}
signed main()
{
    fast;
    int T = 1;
    cin>>T;
    while (T--)
    {
        solve();
    }
    stop;
    return 0;
}