题解 CF1420C2 【Pokémon Army (hard version)】
Karry5307
2020-09-26 07:51:45
### 题意
给定一个长度为 $n$ 的序列 $a$，有 $q$ 次操作，每次操作交换 $a_l$ 和 $a_r$，在操作前和每次操作后求出 $a$ 中所有子序列的交替和的最大值
$\texttt{Data Range:}1\leq n,q\leq 3\times 10^5$
### 题解
考虑先将数组差分一下，所以这个时候选一个系数为 $-1$ 一个系数为 $1$ 的位置出来相当于在差分数组上选一段区间。
所以问题变成在差分数组上选若干不相交区间使得和最大，只需要把那些大于 $0$ 的选出来即可。
对于交换操作的话可以把原来这两个位置的贡献减掉然后把新的贡献加回来，可能需要一些分类讨论。
具体实现可以看代码。
### 代码
```cpp
// This code is written by Karry5307
#include<bits/stdc++.h>
// Definition
#define For(i,x,y) for(register int i=(x);i<(y);i++)
#define Forr(i,x,y) for(register int i=(x);i<=(y);i++)
#define Rep(i,x,y) for(register int i=(x);i>(y);i--)
#define Repp(i,x,y) for(register int i=(x);i>=(y);i--)
#define ve vector
#define iter iterator
#define pb emplace_back
#define popb pop_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define F first
#define S second
#define PY return (void)puts("Yes")
#define PN return (void)puts("Yes")
#define P0 return (void)puts("0")
#define P1 return (void)puts("-1")
using namespace std;
// Typedefs
typedef int ll;
#define ll long long
typedef long long int li;
typedef unsigned int ul;
typedef unsigned long long int ull;
typedef double db;
typedef long double ldb;
typedef pair<ll,ll> pii;
typedef pair<li,li> pll;
const ll MAXN=6e5+51,MOD=998244353,inf=0x3f3f3f3f;
// Structures and variables
ll test,n,qcnt,l,r,res;
ll x[MAXN],f[MAXN],g[MAXN];
// Fast IO
inline ll read()
{
register ll num=0,neg=1;
register char ch=getchar();
while(!isdigit(ch)&&ch!='-') ch=getchar();
if(ch=='-') neg=-1,ch=getchar();
while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch-'0'),ch=getchar();
return neg==1?num:-num;
}
inline li readu()
{
register li num=0;
register char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) num=(num<<3)+(num<<1)+(ch-'0'),ch=getchar();
return num;
}
template<class T>
inline void writep(T x)
{
if(x<0){return (void)putchar('-'),writep(-x);}
if(x<10){return (void)putchar(x|48);}
writep(x/10),putchar((x%10)|48);
}
template<class T>
inline void write(T x,char ch=' '){writep(x),putchar(ch);}
template<class T>
inline void writeln(T x){writep(x),putchar('\n');}
// chkmin and chkmax
template<class T>
inline void chkmax(T &x,const T &y){x=x>y?x:y;}
template<class T>
inline void chkmin(T &x,const T &y){x=x<y?x:y;}
// Functions
template<class T,class Compare>
inline void sort(ve<T>&v,Compare cmp=less<T>()){sort(all(v),cmp);}
template<class T>
inline void reverse(ve<T>&v){reverse(all(v));}
template<class T>
inline void clear(T *arr){memset(arr,0,sizeof(arr));}
template<class T>
inline void setInf(T *arr){memset(arr,0x3f,sizeof(arr));}
// Math funcs
inline ll qpow(ll base,ll exponent)
{
li res=1;
while(exponent)
{
if(exponent&1)
{
res=(li)res*base%MOD;
}
base=(li)base*base%MOD,exponent>>=1;
}
return res;
}
inline ll gcd(ll x,ll y)
{
return !y?x:gcd(y,x%y);
}
inline li lcm(ll x,ll y)
{
return x/gcd(x,y)*y;
}
// Functions
inline void solve()
{
n=read(),qcnt=read(),res=0;
for(register int i=1;i<=n;i++)
{
x[i]=read(),res+=max(0ll,x[i]-x[i-1]);
}
printf("%lld\n",res);
for(register int i=0;i<qcnt;i++)
{
l=read(),r=read(),res-=max(0ll,x[l]-x[l-1])+max(0ll,x[r]-x[r-1]);
l!=n?res-=max(0ll,x[l+1]-x[l]):1,r!=n?res-=max(0ll,x[r+1]-x[r]):1;
l+1==r?res+=max(0ll,x[r]-x[l]):1,swap(x[l],x[r]);
res+=max(0ll,x[l]-x[l-1])+max(0ll,x[r]-x[r-1]);
l!=n?res+=max(0ll,x[l+1]-x[l]):1,r!=n?res+=max(0ll,x[r+1]-x[r]):1;
l+1==r?res-=max(0ll,x[r]-x[l]):1,printf("%lld\n",res);
}
}
int main()
{
test=read();
for(register int i=0;i<test;i++)
{
solve();
}
}
```