E. Fill the Matrix
题意：给定一个长为a的数组，你需要找到一个子序列使得其b1-b2+b3-b3+-----的值最大，同时有q个询问，每次交换a中两个元素的位置，问交换后如何最大值是多少。
n,q<=3e5,1<=ai<=n.
题解：我们显然是要寻找某种性质，使得转移过程中复杂度低于线性。
我们贪心地想，取每一个局部最大值为奇数位，局部最小值为偶数位，即取遍数组中每座峰到底的长度，容易证明这样做是正确的。那么，当我们改变两个位置时，局部最大/小值的改变只会发生在l-1,l,l+1,r-1,r,r+16个位置上，我们暴力判断这6个位置是否变成了局部最大最小值，若是假如即可（最大最小值成对）。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+10;
int a[N],n;
int check(int i){
if(i<=0||i>n) return 0;
if(a[i]>a[i-1]&&a[i]>a[i+1]){
return 1;
}
else if(a[i]<a[i-1]&&a[i]<a[i+1]) return -1;
else return 0;
}
void solve(){
int q;cin>>n>>q;
int ans=0;
for(int i=1;i<=n;i++) cin>>a[i];
a[0]=-1e9,a[n+1]=-1e9;
for(int i=1;i<=n;i++){
if(a[i]>a[i-1]&&a[i]>a[i+1]){
ans+=a[i];
}
else if(a[i]<a[i-1]&&a[i]<a[i+1]) ans-=a[i];
}
cout<<ans<<endl;
for(int i=1;i<=q;i++){
int l,r;cin>>l>>r;
set<int> st;
for(int j=-1;j<=1;j++){
st.insert(l+j);
st.insert(r+j);
}
for(auto it=st.begin();it!=st.end();it++){
int w=*it;
if(check(w)==1) ans-=a[w];
else if(check(w)==-1) ans+=a[w];
}
swap(a[l],a[r]);
for(auto it=st.begin();it!=st.end();it++){
int w=*it;
if(check(w)==1) ans+=a[w];
else if(check(w)==-1) ans-=a[w];
}
cout<<ans<<endl;
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
solve();
}