C2. Pokémon Army (hard version)(贪心分治)

C2. Pokémon Army (hard version) (贪心&分治)

思路：局部最优解$\to$全局最优解。

显然答案数组长度为奇数，因为$a_i>0$。

考虑小区间$[i?1,1+1]$，对于数$a_i$，若$a_i$为波峰，$a_i>a_{i?1}\&\&a_i>a_{i+1}$。

显然这样的$a_i$是最优的，与之对应的波谷$a_i$则减去即可。

这样同时保证了答案数组长度为奇数。

对于交换操作，即考虑$a_l,a_r$对于答案的影响。

我们在原来的答案上删去$a_l,a_{l?1},a_{l+1},a_r,a_{r?1},a_{r+1}$的影响。

然后交换$a_l,a_r$，再加上$a_l,a_{l?1},a_{l+1},a_r,a_{r?1},a_{r+1}$的影响即可。

时间复杂度：$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;
}