局部最值性质

E. Fill the Matrix

Problem - E - Codeforces

题意：给定一个长为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();
}