思路：局部最优解 → \rightarrow →全局最优解。
显然答案数组长度为奇数，因为 a i > 0 a_i>0 ai>0。
考虑小区间 [ i − 1 , 1 + 1 ] [i-1,1+1] [i−1,1+1]，对于数 a i a_i ai，若 a i a_i ai为波峰， a i > a i − 1 & & a i > a i + 1 a_i>a_{i-1}\&\&a_i>a_{i+1} ai>ai−1&&ai>ai+1。
显然这样的 a i a_i ai是最优的，与之对应的波谷 a i a_i ai则减去即可。
这样同时保证了答案数组长度为奇数。
对于交换操作，即考虑 a l , a r a_l,a_r al,ar对于答案的影响。
我们在原来的答案上删去 a l , a l − 1 , a l + 1 , a r , a r − 1 , a r + 1 a_l,a_{l-1},a_{l+1},a_r,a_{r-1},a_{r+1} al,al−1,al+1,ar,ar−1,ar+1的影响。
然后交换 a l , a r a_l,a_r al,ar，再加上 a l , a l − 1 , a l + 1 , a r , a r − 1 , a r + 1 a_l,a_{l-1},a_{l+1},a_r,a_{r-1},a_{r+1} al,al−1,al+1,ar,ar−1,ar+1的影响即可。
时间复杂度： O ( n ) O(n) O(n)
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int N=3e5+5,M=2e4+5,inf=0x3f3f3f3f,mod=1e9+7; #define mst(a,b) memset(a,b,sizeof a) #define lx x<<1 #define rx x<<1|1 #define reg register #define PII pair<int,int> #define fi first #define se second #define pb push_back #define il inline int t,n,q,a[N]; ll ans; void fun(int i,int op){ if(a[i]>a[i-1]&&a[i]>a[i+1]) ans+=op*a[i]; if(a[i]<a[i-1]&&a[i]<a[i+1]) ans-=op*a[i]; } int main(){ scanf("%d",&t); while(t--){ scanf("%d%d",&n,&q);a[0]=a[n+1]=-1;ans=0; for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) fun(i,1); printf("%lld\n",ans); while(q--){ int l,r;scanf("%d%d",&l,&r); fun(l,-1),fun(l-1,-1),fun(l+1,-1); if(l+1<r-1) fun(r-1,-1); if(l+1<r) fun(r,-1); fun(r+1,-1); swap(a[l],a[r]); fun(l,1),fun(l-1,1),fun(l+1,1); if(l+1<r-1) fun(r-1,1); if(l+1<r) fun(r,1); fun(r+1,1); printf("%lld\n",ans); } } return 0; }